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

zhang_kevin · 2026-05-11 09:34:13 · 题解

考察『当前得分最低的人得分恰为 i，且共有 x 人同时处于这个分数』的情况。由于规则要求最低分行动，因此这 x 个人必然依次行动，直到发生以下两种情况之一：

某人得分直接飙升到 \geq m：游戏结束。
所有 x 人均完成操作且分数 < m：最小值将永远 > i。

在这一连串行动中，每次操作前的分数均为 i，因此单次操作直接结束游戏的概率恒为：

p = P(i + \text{点数} \geq m) = \begin{cases} \frac{k - m + i + 1}{k},\quad m - i \leq k\\ 0, \qquad \qquad m - i > k \end{cases}

那么在最小值为 i 时，这 x 人造成的期望行动次数 C(x) 为：

若 p = 0，则无法结束，显然 C(x) = x。
若 p > 0，则相当于进行一个最多 x 次的伯努利试验序列，期望次数为：

C(x) = \frac{1 - (1 - p)^x}{p}

接下来考察『单个玩家的独立操作过程』。显然这个人在操作过程中关于一个分数 i 有以下 3 种情况：

得分恰好为 i：设其概率为 f_i。
得分从 < i 变成 (i, m) 之间：设其概率为 g_i。
得分从 < i 变到 [m, +\infty)：显然这个人得分首次 \geq i 时游戏已经结束，概率为 1 - f_i - g_i。

在真实游戏过程中，如果所有人都 \geq i 且游戏还没结束，则意味着每个玩家都有 f_i 的概率恰好为 i、有 g_i 的概率得分位于 (i, m)，且不会有人直接 \geq m（否则游戏就结束了）。于是在游戏能够进行的前提下，有：

P(\text{恰有 } x \text{ 人在 } i) = \binom{n}{x} f_i^x g_i^{n - x}

将上面所说的相结合，即得分数最小值为 i 处对总行动次数的期望贡献：

E_i = \sum\limits_{x = 0}^n \binom{n}{x} f_i^x g_i^{n - x} \cdot C(x)

带入 C(x) 的表达式，可得：

当 p = 0 时：C(x) = x，故 E_i = \sum\limits_{x = 0}^n \binom{n}{x} x f_i^x g_i^{n - x} = nf_i(f_i + g_i)^{n - 1}。
当 p > 0 时，带入 C(x) = \frac{1 - (1 - p)^x}{p}，于是：

\begin{aligned} E_i &= \frac{1}{p} \sum\limits_{x = 0}^n \binom{n}{x} \left[f_i^x g_i^{n - x} \cdot (1 - (1 - p)^x)\right] \\ &= \frac{1}{p} \sum\limits_{x = 0}^n \binom{n}{x} \left[f_i^x g_i^{n - x} - ((1 - p)f_i)^x \cdot g_i^{n - x}\right] \\ &= \frac{1}{p} \left[(f_i + g_i)^n - \left((1 - p)f_i + g_i\right)^n\right] \end{aligned}

最后总行动次数的期望 E 即：

E = \sum\limits_{i = 0}^{m - 1} E_i

最后考虑如何计算 f_i 和 g_i。

对于 f_i，显然 f_0 = 1，每次从上一个状态恰好跳到 i 的成功概率为 \frac{1}{k}，因此：

f_i = \frac{1}{k} \sum\limits_{j = \max(0, i - k)}^{i - 1} f_j

前缀和或滑动窗口优化即可做到 \mathcal{O}(m)。

对于一个分数 x < i，玩家恰好停留在 x 的概率为 f_x，然后从 x 操作一次，结果 d 应满足：

i + 1 \leq x + d \leq m - 1, \quad 1 \leq d \leq k

稍微推一下，可以得到：

g_i = \frac{1}{k} \sum\limits_{x = \max(0, i - k)}^{i - 1} f_x \cdot \max(0, \min(k, m - 1 - x) - (i + 1 - x) + 1)

用你喜欢的方法优化一下也可以做到 \mathcal{O}(m)。

由于需要快速幂，因此总时间复杂度为 \mathcal{O}(n \log n)。

参考代码：

namespace Solution{
    const int mo = 1e9 + 7;
    int n, k, m, f[1000005], sf[1000005], g[1000005], da[1000005], db[1000005];
    inline int mod(ll x){return (x % mo + mo) % mo;}
    inline int fp(int a, int b){
        int res = 1;
        while(b){
            if(b & 1) res = (ll)res * a % mo;
            a = (ll)a * a % mo;
            b >>= 1;
        }
        return res;
    }
    inline int inv(int x){return fp(x, mo - 2);}
    inline int sumf(int l, int r){return mod((ll)sf[r] - sf[l] + f[l]);}
    inline int P(int i){
        if(m - i <= k) return (ll)(k - m + i + 1) * inv(k) % mo;
        return 0;
    }
    inline void Solve(){
        rd(n, k, m); const int invk = inv(k);
        f[0] = 1; fu(i, 1, m){
            f[i] = (ll)invk * sumf(max(0, i - k), i - 1) % mo;
            sf[i] = (sf[i - 1] + f[i]) % mo;
        }
        fu(x, 0, m - 1){
            int l = x + 1, r = (m - 1 - x >= k) ? (x + k) : (m - 1), c = r;
            if(l <= r){
                int a = (ll)f[x] * c % mo, b = mo - f[x];
                da[l] = (da[l] + a) % mo, da[r + 1] = (da[r + 1] - a + mo) % mo;
                db[l] = (db[l] + b) % mo, db[r + 1] = (db[r + 1] - b + mo) % mo;
            }
        }
        int suma = 0, sumb = 0;
        fu(i, 0, m){
            suma = (suma + da[i]) % mo, sumb = (sumb + db[i]) % mo;
            g[i] = (ll)((ll)sumb * i % mo + suma) % mo * invk % mo;
        }
        // fu(i, 0, m) cerr << f[i] << ' ' << g[i] << '\n';
        int ans = 0;
        fu(i, 0, m){
            int p = P(i), Ei = 0;
            if(p == 0){
                Ei = (ll)n * f[i] % mo * fp((f[i] + g[i]) % mo, n - 1) % mo;
            }else{
                int t1 = fp((f[i] + g[i]) % mo, n);
                int t2 = fp(mod((ll)mod(1 - p) * f[i] % mo + g[i]), n);
                Ei = (ll)inv(p) * mod(t1 - t2) % mo;
            }
            ans = (ans + Ei) % mo;
        }
        wr(ans), pc('\n');
        return;
    }
}