QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488814#8815. Space Stationzhao_daodaoWA 1ms3764kbC++141.2kb2024-07-24 15:29:522024-07-24 15:29:53

Judging History

你现在查看的是最新测评结果

  • [2024-07-30 16:51:06]
  • hack成功,自动添加数据
  • (/hack/760)
  • [2024-07-24 15:29:53]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3764kb
  • [2024-07-24 15:29:52]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=200+5;
const int mod=998244353;
inline int ksm(int a, int b){
	int cnt = 1;
	while(b) {
		if(b & 1) cnt = cnt * a % mod;
		a = a * a % mod; b >>= 1;
	}return cnt;
}
int n,m,a[MAXN];
int dp[MAXN][MAXN];
int fac[MAXN],inv[MAXN];
signed main(){
	cin.tie(0),cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>m;int all = 0;
	for(int i = 1; i <= n; i++)cin >> a[i], all += a[i];
	fac[0] = 1;
	for(int i = 1; i <= n; i++)
		fac[i] = fac[i - 1] * i % mod;
	inv[n] = ksm(fac[n], mod - 2);
	for(int i = n - 1; i >= 0; i--)
		inv[i] = inv[i + 1] * (i + 1) % mod;
	function <int(int, int)> C = [&](int a, int b) -> int{return fac[a] * inv[b] % mod * inv[a - b] % mod;};
	dp[0][0] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = i; j >= 1; j--)
			for(int k = all; k >= a[i]; k--)
				(dp[j][k] += dp[j - 1][k - a[i]]) %= mod;
	int ans = 0;
	for(int i = 1; i <= n; i++){
		int sum = 0;
		for(int j = 1; j <= all; j++){
			if(i * m > j)(sum += dp[i][j] * j % mod * ksm(i, mod - 2) % mod) %= mod;
			else (sum += dp[i][j] * m % mod) %= mod;
		}
		(ans += sum * ksm( C(n, i), mod - 2) % mod) %= mod;
	}
	cout << ans << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3764kb

input:

3 3
2 3 4

output:

499122185

result:

ok 1 number(s): "499122185"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

5 1
10 20 30 40 50

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

1 9
37

output:

9

result:

ok 1 number(s): "9"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

5 5
24 41 29 6 40

output:

25

result:

ok 1 number(s): "25"

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 3624kb

input:

10 34
91 86 1 14 98 13 85 64 91 20

output:

905306424

result:

wrong answer 1st numbers differ - expected: '707882334', found: '905306424'