QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#614850 | #9436. Some Sum of Subset | ucup-team3282# | WA | 1ms | 9784kb | C++20 | 1.5kb | 2024-10-05 17:02:34 | 2024-10-05 17:02:34 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
const long long mod=998244353;
long long ans[5050];
long long dp[5050][5050];
long long x[5050];
long long cnt[5050][5050];
long long n,m;
long long pow(long long a,long long b=mod-2){
if(b==1)return a;
long long ret=pow(a,b>>1);
if(b&1)return ret*ret%mod*a%mod;
else return ret*ret%mod;
}
bool cmp(long long a,long long b){
return a>b;
}
int main(){
// cout<<30ll*pow(6)%mod;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>x[i];
}
sort(x+1,x+n+1,cmp);
for(int i=1;i<=n;i++){
for(int j=1;j<=3000;j++)dp[i][j]=dp[i-1][j];
if(x[i]<m)dp[i][x[i]]++;
else ans[n-i]++;
for(int j=1;j<=3000;j++){
if(j+x[i]>=m)ans[n-i]+=dp[i-1][j];
else{
dp[i][j+x[i]]+=dp[i-1][j];
}
}
}
cnt[0][0]=1;
for(int i=0;i<=n;i++){
cnt[i][0]=1;
for(int k=1;k<=n;k++){
cnt[i][k]=cnt[i][k-1]*pow(k)%mod*(i-k+1);
}
for(int k=n;k>=0;k--){
cnt[i][k]=(cnt[i][k]+cnt[i][k+1])%mod;
}
}
// for(int i=0;i<=n;i++){
// cout<<ans[i]<<endl;
// }
// cout<<endl;
for(int k=0;k<=n;k++){
long long anser=0;
for(int i=k;i<=n;i++){
anser=(anser+(ans[i]*cnt[i][k]))%mod;
// cout<<anser<<'/';
}
cout<<anser<<endl;
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5724kb
input:
4 7 3 1 5 2
output:
6 4 1 0 0
result:
ok 5 tokens
Test #2:
score: 0
Accepted
time: 0ms
memory: 7736kb
input:
1 5 7
output:
1 0
result:
ok 2 tokens
Test #3:
score: 0
Accepted
time: 1ms
memory: 7768kb
input:
9 18 1 9 5 6 2 7 1 4 8
output:
346 309 230 126 46 10 1 0 0 0
result:
ok 10 tokens
Test #4:
score: 0
Accepted
time: 1ms
memory: 5660kb
input:
1 1467 556
output:
0 0
result:
ok 2 tokens
Test #5:
score: 0
Accepted
time: 1ms
memory: 5688kb
input:
1 1753 2514
output:
1 0
result:
ok 2 tokens
Test #6:
score: 0
Accepted
time: 0ms
memory: 5616kb
input:
1 1182 1182
output:
1 0
result:
ok 2 tokens
Test #7:
score: 0
Accepted
time: 1ms
memory: 5660kb
input:
2 1741 955 835
output:
1 0 0
result:
ok 3 tokens
Test #8:
score: 0
Accepted
time: 1ms
memory: 5660kb
input:
2 1481 2004 1570
output:
3 1 0
result:
ok 3 tokens
Test #9:
score: 0
Accepted
time: 1ms
memory: 5668kb
input:
2 1336 1336 1336
output:
3 1 0
result:
ok 3 tokens
Test #10:
score: 0
Accepted
time: 0ms
memory: 5664kb
input:
12 400 2163 2729 1322 2787 2404 1068 1502 746 898 2057 1771 502
output:
4095 4083 4017 3797 3302 2510 1586 794 299 79 13 1 0
result:
ok 13 tokens
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 9784kb
input:
42 1609 532 722 2650 2889 2260 659 1831 401 2779 1262 2185 1479 515 552 1627 637 1080 580 1589 2154 2650 219 2924 1712 311 2609 1062 968 1357 1310 1942 2419 2465 300 2546 2537 2967 1197 2271 1551 999 2531
output:
813001720 813001326 812998976 812981596 -185393664 293127823 -472370498 336347729 140301405 -858131363 269814215 153718176 97299367 -208776004 -277387466 -316835673 -161038567 192034439 835850756 48363470 698967262 -357284798 -834947273 -7165993 -714194954 -181737506 -915474635 -426456601 -51656242 ...
result:
wrong answer 1st words differ - expected: '780135870', found: '813001720'