【tyvj P4879】骰子游戏

时间：2021-10-20 21:14:44

http://www.tyvj.cn/p/4879

首先，投一个骰子，每个数字出现的概率都是一样的。也就是不算小A的话，n个人投出x个骰子需要的次数和点数无关。

计数问题考虑dp，令f(i,j)为前i个人投j个同点数的骰子的方案数，容易得f(i,j)=sum{f(i-1,j-k)*f(1,k) | 0<=k<=m}.

边界是f(1,j)，具体是什么值呢？一个人投m个骰子，会得到6种点数，其中一种有j个，其他的五种有m-j个。也就是把m-j个骰子分成5份的方案数。

用插板法可得f(1,j)=C(m-j+4,4)=(m-j+1)(m-j+2)(m-j+3)(m-j+4)/24.

然后好像说这玩意需要用FFT优化才能A，真成NOI Plus模拟赛了……

#include <iostream>

#include <algorithm>

#define maxn 405

using namespace std;

typedef unsigned long long ullint;

const ullint c = ;

int n, m, x, y;

ullint dp[maxn][maxn * maxn];

int main()

{

    ios::sync_with_stdio(false);

    cin >> n >> m >> x >> y;

    int cnt = , tmp;

    for (int i = ; i <= m; i++)

    {

        cin >> tmp;

        if (tmp == y)

            cnt++;

    }

    for (int j = ; j <= m; j++)

        dp[][j] = (m - j + ) % c * (m - j + ) % c * (m - j + ) % c * (m - j + ) % c *  % c;

    for (int i = ; i <= n; i++)

        for (int j = ; j <= i * m; j++)

            for (int k = ; k <= min(j, m); k++)

                dp[i][j] = (dp[i][j] + dp[i - ][j - k] * dp[][k] % c) % c;

    ullint ans = ;

    for (int j = x - cnt; j <= n * m; j++)

        ans = (ans + dp[n][j]) % c;

    cout << ans;

    return ;

}

相关文章