QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#489059#8815. Space Stationyz_lyWA 40ms11492kbC++141.5kb2024-07-24 17:12:042024-07-24 17:12:05

Judging History

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

  • [2024-07-30 16:51:06]
  • hack成功,自动添加数据
  • (/hack/760)
  • [2024-07-24 17:12:05]
  • 评测
  • 测评结果:WA
  • 用时:40ms
  • 内存:11492kb
  • [2024-07-24 17:12:04]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}
inline void work(ll k){
	if(k<0){
		putchar('-');
		k=-k;
	}
	if(k>9)
		work(k/10);
	putchar(k%10+'0');
}
/*
首先策略很简单,如果后面的平均值>m就会选择m,否则选择这次攻击
dp[i][j]表示还剩下i个数,和为j的方案数,暴力转移就行了
算期望的话用概率公式算就行了
*/
const ll mod=998244353;
int n,m;
ll dp[105][10005],ans,jc[105],inv[105];
ll power(ll a,ll b){
	ll sum=1,k=a;
	while(b){
		if(b&1ll)
			sum=sum*k%mod;
		k=k*k%mod;
		b>>=1ll;
	}
	return sum;
}
ll C(ll n,ll m){
	if(n<m)
		return 0;
	return jc[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
	n=read();
	m=read();
	dp[0][0]=1;
	jc[0]=inv[0]=inv[1]=1;
	for(int i=1,x;i<=n;i++){
		x=read();
		jc[i]=jc[i-1]*i%mod;
		for(int j=i;j;j--){
			for(int k=x;k<=i*100;k++){
				dp[j][k]=(dp[j][k]+dp[j-1][k-x])%mod;
			}
		}
	}
	for(int i=2;i<=n;i++){
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	}
	for(int i=1;i<=n;i++){
		inv[i]=inv[i-1]*inv[i]%mod;
	}
	for(int i=n;i;i--){
		ll sum=0,num=0;
		for(int j=i;j<=i*100;j++){
			sum=(sum+dp[i][j]*min(j,m*i)%mod)%mod;
			num=(num+dp[i][j])%mod;
		}
		if(num!=C(n,i)){
			cout<<C(n,i)<<" "<<num<<"\n";
			return 0;
		}
		ans=(ans+sum*power(C(n,i)*i%mod,mod-2)%mod)%mod;
	}
	work(ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 3
2 3 4

output:

499122185

result:

ok 1 number(s): "499122185"

Test #2:

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

input:

5 1
10 20 30 40 50

output:

5

result:

ok 1 number(s): "5"

Test #3:

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

input:

1 9
37

output:

9

result:

ok 1 number(s): "9"

Test #4:

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

input:

5 5
24 41 29 6 40

output:

25

result:

ok 1 number(s): "25"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3736kb

input:

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

output:

707882334

result:

ok 1 number(s): "707882334"

Test #6:

score: -100
Wrong Answer
time: 40ms
memory: 11492kb

input:

100 9
83 99 170 80 174 137 1 91 111 35 69 39 148 76 142 90 105 30 114 176 196 85 26 109 162 167 171 148 169 162 159 3 4 6 33 61 163 7 77 63 8 20 13 51 26 11 149 136 134 187 96 95 113 104 128 48 167 74 18 91 200 62 167 32 5 180 189 39 63 111 68 72 81 128 42 13 57 180 111 91 83 177 34 45 158 29 114 33...

output:

1 0

result:

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