题目
F - Make 10 Again
思路
参考
- 动态规划,
dp[i][j]表示前i个骰子,可组合出的点数集合为j的概率为dp[i][j];
- 预处理
nxt[i][j], 表示点数集合状态为i,在得到一个新的骰子的点数j后, 可转移到的点数集合nxt[i][j];
- 注意: 如何处理
a[i]>10的情况, 见代码;
总结
- bitmask 枚举状态, 尤其是集合状态;
- 如何处理概率取模, 这份代码就很简洁;
- 预处理bitmask的状态转移;
代码
Code
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL mod = 998244353;
LL qpow(LL x, LL k)
{
LL res = 1;
while (k)
{
if (k & 1) res = res * x % mod;
k >>= 1;
x = x * x % mod;
}
return res;
}
long long n, a[110], dp[110][2100], nxt[2100][20];
int main()
{
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
dp[0][1] = 1;
// nxt[i][j] 在状态i的基础上, 得到一个新的骰子的点数为j, 则可组合得出的骰子的点数集合的状态为 nxt[i][j]
for (int i = 0; i < 2048; ++i) // 0 ~ (1<<11)
for (int j = 1; j <= 10; ++j) // 当前骰子点数
{
int ii = i; // 从状态i, 得到新的骰子点数j, 可转移到的所有状态ii
for (int k = 0; k < 11; ++k) // 与状态i中哪种组合k相加, 得到新的骰子点数和
if ((i & (1 << k)) && k + j <= 10)
ii |= (1 << (k + j));
nxt[i][j] = ii;
}
for (int i = 0; i < n; ++i) // 已掷出i个骰子, 考虑第i+1个骰子
for (int j = 0; j < 2048; ++j) //
if (dp[i][j])
{
long long po = qpow(a[i], mod - 2);
// den, 注意, 这里的分布是第i个骰子的可能数, 而不是当前循环正在枚举的第i+1个骰子
for (int k = 1; k <= min(10LL, a[i]); ++k)
{
dp[i + 1][nxt[j][k]] = (dp[i + 1][nxt[j][k]] + dp[i][j] * po) % mod;
// 前i个骰子可组成的状态集合为j, 当得到新的骰子点数为k, 则前i+1个骰子可组成的状态集合为nxt[j][k]
// 因而, 状态从dp[i][j] 转移而来
}
if (a[i] > 10)
{
dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * (a[i] - 10) % mod * po) % mod;
// 投出超过10的数, 则本轮骰子的点数并不能帮助得出新的状态;
// 但是这也产生了新的骰子投掷结果组合, 因而需要计数
}
}
LL ans = 0;
for (int i = 0; i < 2048; ++i) // 状态集合i中, 包含点数和为10的组合可能
if (i & (1 << 10))
ans = (ans + dp[n][i]) % mod;
cout << ans << endl;
return 0;
}