题意
给定 \(N\) 个骰子，每个骰子会随机的出现数字 \(1\) 到 \(A_i\) ， 求能够从 \(N\) 个骰子中选若干个， 使他们的点数之和为 \(10\) 的概率。
\(N \leqslant 100\)
Solution
第一眼思路为设计状态 \(dp(i,j)\) 为前 \(i\) 个骰子，点数之和为 \(j\) 的概率。
稍微加以思考，会发现这个状态非常难以处理，因为点数和为 \(j\) 的局面非常复杂，并且考虑到是先随机后选，该思路极易出现重复计算的情况，并且无法处理不选某个骰子的情况，考虑使用状压更好的表示出当前局面。
记 \(S\) 为当前可以表示出的数字的集合， 设计状态 \(dp(i, S)\) 为前 \(i\) 个骰子可以表示出状态 \(S\)
设计出状态转移方程，
对于骰子的点数 $j \in [ 1, A_i ] $ 记 \(T = \{x+j, x \in S\}\)，
\[dp(i, T) = \sum {dp(i - 1, S) · \frac{1}{A_i}} \]当\(A_i > 10\)时， 则另有
\[dp(i,T) = \sum {dp(i - 1, S) · \frac{1}{A_i}} + dp(i, T) · \frac{A_i - 10}{A_i} \]最后统计所有状态中含有数字 \(10\) 的即可。
Code
点击查看代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 150;
const int mod = 998244353;
inline int read() {
register int w = 0, f = 1;
register char c = getchar();
while (c > '9' || c < '0') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
w = w * 10 + c - '0';
c = getchar();
}
return w * f;
}
int n;
int a[N];
int f[N][5050];
inline int qpow(register int a, register int b) {
register int base = 1;
while (b) {
if (b & 1) base = 1ll * base * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return base;
}
int main() {
n = read();
for (register int i = 1; i <= n; ++i) a[i] = read();
f[0][1] = 1;
register int base = (1 << 11) - 1;
for (register int i = 1; i <= n; ++i) {
for (register int j = 1; j <= min(10, a[i]); ++j)
for (register int S = 0; S < (1 << 11); S++) {
int st = (S | (S << j)) & base;
f[i][st] = (f[i][st] + 1ll * f[i - 1][S] * qpow(a[i], mod - 2) % mod) % mod;
}
if (a[i] > 10) {
for (register int S = 0; S < (1 << 11); S++)
f[i][S] = (f[i][S] + 1ll * f[i - 1][S] * (a[i] - 10) % mod * qpow(a[i], mod - 2) % mod) % mod;
}
}
register int ans = 0;
for (register int S = 0; S < (1 << 10); S++)
ans = (ans + f[n][S + (1 << 10)]) % mod;
printf("%d\n", ans);
return 0;
}