蒟蒻求助,为什么不能用线性DP?
查看原帖
蒟蒻求助,为什么不能用线性DP?
463956
incra楼主2023/7/16 14:42

fi,j,kf_{i,j,k} 表示从前 ii 个色子中选 jj 个所得到的和为 kk 的概率膜上 998244353998244353。

自己认为没有问题啊。

代码:

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair <int,int> PII;
const int N = 110,MOD = 998244353;
int n;
int a[N];
LL f[N][20][20];
LL power (LL a,LL b,LL p) {
	LL ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return ans;
}
int main () {
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> a[i];
	f[0][0][0] = 1;
	for (int i = 1;i <= n;i++) {
		f[i][0][0] = 1;
		for (int j = 1;j <= 10;j++) {
			for (int k = 1;k <= 10;k++) {
				f[i][j][k] = f[i - 1][j][k];
				for (int u = 1;u <= min (k,a[i]);u++) {
					f[i][j][k] = (f[i][j][k] + f[i - 1][j - 1][k - u] * power (a[i],MOD - 2,MOD) % MOD) % MOD;
				}
			}
		}
	}
	LL ans = 0;
	for (int i = 1;i <= 10;i++) ans = (ans + f[n][i][10]) % MOD;
	cout << ans << endl;
	return 0;
}
2023/7/16 14:42
加载中...