QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#614850#9436. Some Sum of Subsetucup-team3282#WA 1ms9784kbC++201.5kb2024-10-05 17:02:342024-10-05 17:02:34

Judging History

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

  • [2024-10-05 17:02:34]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:9784kb
  • [2024-10-05 17:02:34]
  • 提交

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;
    }
}

Details

Tip: Click on the bar to expand more detailed information

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'