题解：P15985 [PA 2026] 骰子 / Kostki
george0929
·
·
题解
这个过程有不可避免的指数状态量，因此考虑先拆贡献，答案是每个玩家在每个数值进行操作的概率之和。
拆贡献首先需要考虑计算某个固定局面出现的概率。
不难发现每个玩家掷骰子的数值独立，即每个玩家第 1,2,\dots 次骰出的值独立。因此，考虑预先确定每个玩家的骰子序列，在骰子序列固定的情况下，一个局面的出现概率是 0 或 1。因此我们只需要记录合法的骰子序列个数。
那么枚举最小值 i，计算玩家经过 i 的概率 f_i 和玩家跳过 i 且没有跨过 m 的概率 g_i，求 f,g 是简单的。
设 i 一步跨过 m 的概率为 p_i，枚举 i 产生的贡献次数，后面就是朴素的推式子了，答案为：
\sum_i \sum_{x=1}^{n} \sum_{j=1}^{x} (1-p_i)^{j} \binom{n}{x} f_{i}^x g_{i}^{n-x}
\\
=\sum_i \sum_{x=1}^{n} \binom{n}{x} f_{i}^x g_{i}^{n-x} \frac{1-(1-p_i)^x}{p_i}
\\
=\sum_i \frac{1}{p_i}\sum_{x=1}^{n} \binom{n}{x} f_{i}^x g_{i}^{n-x} (1-(1-p_i)^x)
\\
=\sum_i \frac{1}{p_i}((f_i+g_i)^n-(g_i+(1-p_i)f_i)^n)
注意特判 p_i=0 的情况，推导过程与上述类似。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
ll ksm(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b/=2;
}
return res;
}
int n,k,m;
ll f[1000005],g[1000005];
ll sumf[1000005],sumfx[1000005];
ll getf(int l,int r){
if(l>r||r<0) return 0;
r=min(r,m);
ll res=sumf[r];
if(l>0) res-=sumf[l-1];
res=(res+mod)%mod;
return res;
}
ll getfx(int l,int r){
if(l>r||r<0) return 0;
r=min(r,m);
ll res=sumfx[r];
if(l>0) res-=sumfx[l-1];
res=(res+mod)%mod;
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k>>m;
f[0]=sumf[0]=1;
ll invk=ksm(k,mod-2);
for(int i=1;i<=m;i++){
f[i]=getf(i-k,i-1)*invk%mod;
sumf[i]=(sumf[i-1]+f[i])%mod;
sumfx[i]=(sumfx[i-1]+f[i]*i%mod)%mod;
}
for(int i=1;i<m;i++){
//j<i
//j+k>i,j>i-k
//j+k<m,j<m-k [m-k,i-1]
if(i-1+k<m){
g[i]=getf(i+1-k,i-1)*(k-i)%mod*invk%mod;
g[i]=(g[i]+getfx(i+1-k,i-1)*invk%mod)%mod;
}else{
g[i]=getf(i+1-k,m-k-1)*(k-i)%mod*invk%mod;
g[i]=(g[i]+getfx(i+1-k,m-k-1)*invk%mod)%mod;
g[i]=(g[i]+getf(m-k,i-1)*(m-i-1)%mod*invk%mod)%mod;
}
}
ll ans=0;
for(int i=0;i<m;i++){
//i+x>=m,x>=m-i,k-(m-i)+1
int t=k-(m-i)+1;
ll p=0;
if(t<=0) p=0;
else p=t*invk%mod;
if(p){
ll res=ksm((f[i]+g[i])%mod,n)-ksm((g[i]+(1-p+mod)*f[i])%mod,n);
ans=(ans+res*ksm(p,mod-2)%mod+mod)%mod;
}else{
ans=(ans+f[i]*n%mod*ksm((f[i]+g[i])%mod,n-1))%mod;
}
}
cout<<ans<<"\n";
return 0;
}
```