还未改成记忆化,但是有WA,不知为何,悬赏关注
查看原帖
还未改成记忆化,但是有WA,不知为何,悬赏关注
429491
xin20110426楼主2024/6/27 16:02
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
int n, x, t[1010], inv[1010];
int dfs(int tm, int s) {
	if (tm >= x) return (s == 1);
	int sum = 0;
	for (int i = 1; i <= n; i++) sum = (sum + dfs(tm + t[i], i) * inv[n] % mod) % mod;
	return sum;
}
signed main() {
	cin >> n >> x;
	inv[1] = 1;
	for (int i = 2; i <= n; i++) inv[i] = -inv[mod % i] * (mod / i) % mod;
	//cout << "inv:" << inv[n] << endl;
	for (int i = 1; i <= n; i++) cin >> t[i];
	cout << dfs(t[1] - 1, 1);
	return 0;
}  
2024/6/27 16:02
加载中...