和为p点游戏

[题目链接](https://www.nowcoder.com/practice/4008dea63cda4087876ddb55feb207a9)

思路

有 $n$ 个骰子，每轮同时投掷所有骰子并记录点数之和。可以投掷任意多轮（ $\ge 1$ ），求所有轮的总点数之和恰好为 $p$ 的概率，答案对 $10^9 + 7$ 取模。

分两步走

第一步：一轮投掷的概率分布

设 $f[s]$ 为一轮投掷 $n$ 个骰子，点数之和恰好为 $s$ 的概率。 $s$ 的范围是 $[n, 6n]$ 。

用经典 DP 求出 $n$ 个骰子投出各种点数之和的方案数 $\text{cnt}[s]$ ，然后 $f[s] = \text{cnt}[s] \cdot (6^n)^{-1} \bmod (10^9+7)$ 。

第二步：多轮累加的概率

设 $g[t]$ 为投掷若干轮（ $\ge 0$ 轮），总点数之和恰好为 $t$ 的概率。令 $g[0] = 1$ （零轮，和为 $0$ ），则递推关系为：

$ $g[t] = \sum_{s=n}^{\min(6n,\, t)} f[s] \cdot g[t - s]$ $

含义：最后一轮得到 $s$ 点，前面若干轮总和为 $t - s$ 。

最终答案即 $g[p]$ （ $p \ge 1$ 时自然排除了零轮的情况）。

为什么这是正确的？

从生成函数角度，设 $F(x) = \sum_{s=n}^{6n} f[s] \, x^s$ 为单轮的概率生成函数。投掷 $k$ 轮对应 $F(x)^k$ ，投掷任意多轮的概率生成函数为：

$ $G(x) = \sum_{k=1}^{\infty} F(x)^k = \frac{F(x)}{1 - F(x)}$ $

而 $\frac{1}{1-F(x)} = \sum_{k=0}^{\infty} F(x)^k$ 恰好对应 $g$ 的生成函数（ $g[0]=1$ 包含了零轮项），所以 $G(x) = F(x) \cdot \frac{1}{1-F(x)}$ 的 $x^p$ 项（ $p \ge 1$ ）就是 $g[p]$ 。

复杂度分析

时间复杂度： $O(n^2 + n \cdot p)$ 。第一步计算 $n$ 个骰子的方案数为 $O(6n \cdot n)$ ，第二步递推 $g$ 数组为 $O(6n \cdot p)$ 。
空间复杂度： $O(n + p)$ 。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

long long qpow(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    int n, p;
    scanf("%d%d", &n, &p);

    int maxS = min(6 * n, p);

    // 第一步：计算 n 个骰子投出各点数和的方案数
    vector<long long> dp(maxS + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        vector<long long> ndp(maxS + 1, 0);
        for (int j = 0; j <= maxS; j++) {
            if (dp[j] == 0) continue;
            for (int face = 1; face <= 6 && j + face <= maxS; face++) {
                ndp[j + face] = (ndp[j + face] + dp[j]) % MOD;
            }
        }
        dp = ndp;
    }

    // 转为概率：f[s] = dp[s] / 6^n
    long long inv6n = qpow(qpow(6, n, MOD), MOD - 2, MOD);
    vector<long long> f(maxS + 1, 0);
    for (int s = n; s <= maxS; s++) {
        f[s] = dp[s] % MOD * inv6n % MOD;
    }

    // 第二步：递推 g[t] = sum f[s] * g[t-s]
    vector<long long> g(p + 1, 0);
    g[0] = 1;
    for (int t = 1; t <= p; t++) {
        for (int s = n; s <= min(maxS, t); s++) {
            g[t] = (g[t] + f[s] % MOD * g[t - s]) % MOD;
        }
    }

    printf("%lld\n", g[p]);
    return 0;
}

import java.util.Scanner;

public class Main {
    static final long MOD = 1_000_000_007;

    static long qpow(long a, long b, long mod) {
        long res = 1;
        a %= mod;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), p = sc.nextInt();

        int maxS = Math.min(6 * n, p);

        // 第一步：计算 n 个骰子投出各点数和的方案数
        long[] dp = new long[maxS + 1];
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            long[] ndp = new long[maxS + 1];
            for (int j = 0; j <= maxS; j++) {
                if (dp[j] == 0) continue;
                for (int face = 1; face <= 6 && j + face <= maxS; face++) {
                    ndp[j + face] = (ndp[j + face] + dp[j]) % MOD;
                }
            }
            dp = ndp;
        }

        // 转为概率：f[s] = dp[s] / 6^n
        long inv6n = qpow(qpow(6, n, MOD), MOD - 2, MOD);
        long[] f = new long[maxS + 1];
        for (int s = n; s <= maxS; s++) {
            f[s] = dp[s] % MOD * inv6n % MOD;
        }

        // 第二步：递推 g[t] = sum f[s] * g[t-s]
        long[] g = new long[p + 1];
        g[0] = 1;
        for (int t = 1; t <= p; t++) {
            for (int s = n; s <= Math.min(maxS, t); s++) {
                g[t] = (g[t] + f[s] % MOD * g[t - s]) % MOD;
            }
        }

        System.out.println(g[p]);
    }
}