求助abc323d题
  • 板块学术版
  • 楼主ZnPdCo
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/10/8 19:52
  • 上次更新2023/11/2 14:53:55
查看原帖
求助abc323d题
560700
ZnPdCo楼主2023/10/8 19:52
#include <cstdio>
#define P 998244353
#define ll long long
ll n, q;
ll t[10010];
ll f[10010];
ll x, y;
ll ans;
void exgcd(ll a, ll b) {
	if(b == 0) {
		x = 1, y = 0;
		return;
	}
	exgcd(b, a % b);
	ll t = x;
	x = y;
	y = t - a / b * y;
}
int main() {
	scanf("%lld %lld", &n, &q);
	exgcd(n, P);
	ll ninv = (x % P + P) % P;
	for(ll i = 1; i <= n; i++) {
		scanf("%lld", &t[i]);
	}
	f[0] = 1;
	if(t[1] > q) ans += ninv;
	for(ll i = 1; i <= q; i++) {
		for(ll j = 1; j <= n; j++) {
			if(t[j] <= i) f[i] += f[i - t[j]];
		}
		(f[i] *= ninv) %= P;
		if(i + t[1] > q) (ans += f[i] * ninv) %= P;
	}
	printf("%lld", ans);
}

20wa,但是找不到问题qwq

2023/10/8 19:52
加载中...