题解：P15985 [PA 2026] 骰子 / Kostki

· · 题解

太难了，不会做。

你首先要了解这个。

好像 g_i 的求法不太一样。

思路

为了转移，我们设 f_i 表示得分恰好为 i 的概率，g_i 表示第一次达到 \ge i 的位置是在 [i+1,m) 之间的概率。

$g_i$ 的转移从 $g_{i-1}$ 转移过来，再减掉之前的点到达 $i$ 的概率，加上 $i-1$ 到达 $[i+1,m)$ 的概率。 考虑如何计算答案。 设当前位置 $i$ 达到 $m$ 的概率是 $p$（$i$ 是最小位置）。 ### 情况 $p=0

期望跳过 i 的步数为 x（x 是当前位置有多少人）。

此时答案为：

\begin{aligned} \sum_{x=0}^n x\binom{n}{x}f_i^x g_i^{n-x} &= \sum_{x=1}^n n\binom{n-1}{x-1}f_i^x g_i^{n-x} \\ &= nf_i\sum_{x=0}^{n-1} \binom{n-1}{x}f_i^{x}g_i^{n-x-1} \\ &= nf_i(f_i+g_i)^{n-1}. \end{aligned}

情况 p=1

跳过去的期望步数为 \sum_{j=1}^x (1-p)^j（x 是停在 i 的人数）。

利用等比数列求和公式，可得 \tfrac{1-(1-p)^x}{p}。

此时答案为：

\begin{aligned} \sum_{x=0}^n \binom{n}{x} f_i^x g_i^{n-x}\tfrac{1-(1-p)^x}{p} &= \frac{1}{p}\left[\sum_{x=0}^n \binom{n}{x} f_i^x g_i^{n-x} - \binom{n}{x} (f_i(1-p))^x g_i^{n-x}\right] \\ &= \frac{1}{p} \left[(f_i+g_i)^n - (f_i(1-p)+g_i)^n\right]. \end{aligned}

然后就没了。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
#define N 1000005
#define int long long
inline int read(){
    int a=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        a=a*10+c-'0';
        c=getchar();
    }
    return a*f;
}
int ksm(int a,int b){
    int s=1;
    while(b){
        if(b&1)s=s*1ll*a%mod;
        a=a*1ll*a%mod,b/=2;
    }
    return s;
}
int n,m,k,pwk;
int s[N],f[N],g[N];
signed main(){
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    n=read(),k=read(),m=read();
    pwk=ksm(k,mod-2);
    int s1=0;
    f[0]=s1=1;       
    for(int i=1;i<m;i++){
        f[i]=s1*1ll*pwk%mod;
        (s1+=f[i])%=mod;
        if(i-k>=0)(s1+=mod-f[i-k])%=mod;
    }
    s1=1;
    for(int i=1;i<m;i++){
        int l=i+1,r=min(m-1,i+k-1);
        g[i]=(g[i-1]+mod-(s1-f[i-1]+mod)%mod*1ll*pwk%mod+f[i-1]*1ll*pwk%mod*max(0ll,r-l+1)%mod)%mod;
        (s1+=f[i])%=mod;
        if(i-k>=0)(s1+=mod-f[i-k])%=mod;
    }
    int ans=0;
    for(int i=0;i<m;i++){
        int kk=(f[i]+g[i])%mod;
        if(i+k<m)
            (ans+=n*1ll*f[i]%mod*ksm(kk,n-1)%mod)%=mod;
        else{
            int kkk=(i+k-m+1)*1ll*pwk%mod;
            (ans+=(ksm(kk,n)+mod-ksm((f[i]*1ll*(mod+1-kkk)%mod+g[i])%mod,n))%mod*1ll*ksm(kkk,mod-2)%mod)%=mod;
        }
    }
    printf("%lld\n",ans);
    return 0;
}