QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#637179#9436. Some Sum of Subsetucup-team4992#WA 1ms3840kbC++201.1kb2024-10-13 10:41:122024-10-13 10:41:13

Judging History

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

  • [2024-10-13 10:41:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3840kb
  • [2024-10-13 10:41:12]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const int P=998244353;
int main(){
    int n,m;cin>>n>>m;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a.begin()+1,a.end(),greater<int>());
    vector<vector<ll>>f(n+1,vector<ll>(n+1));
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        f[i][0]=f[i-1][0]*2;
        for(int j=1;j<=n;j++){
            f[i][j]=(f[i-1][j]+f[i-1][j-1])%P;
        }
    }
    vector<ll>dp[2];
    dp[0].resize(m+10);
    dp[1].resize(m+10);
    dp[0][0]=1;
    int cur=1;
    vector<ll>ans(n+1);
    vector<ll>tag(n+1);
    for(int i=1;i<=n;i++){
        dp[cur]=dp[cur^1];
        for(int j=0;j<=m;j++){
            int k=min(m,j+a[i]);
            if(j<m&&k>=m){
                tag[i]+=dp[cur^1][j];
                tag[i]%=P;
            }
            dp[cur][k]+=dp[cur^1][j];
            dp[cur][k]%=P;
        }
        // cout<<tag[i]<<'\n';
        for(int j=0;j<=n-i;j++){
            ans[j]+=tag[i]*f[n-i][j]%P;
            ans[j]%=P;
        }
        cur^=1;
    }
    for(int i=0;i<=n;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3644kb

input:

1 5
7

output:

1
0

result:

ok 2 tokens

Test #3:

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

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: 0ms
memory: 3568kb

input:

1 1467
556

output:

0
0

result:

ok 2 tokens

Test #5:

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

input:

1 1753
2514

output:

1
0

result:

ok 2 tokens

Test #6:

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

input:

1 1182
1182

output:

1
0

result:

ok 2 tokens

Test #7:

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

input:

2 1741
955 835

output:

1
0
0

result:

ok 3 tokens

Test #8:

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

input:

2 1481
2004 1570

output:

3
1
0

result:

ok 3 tokens

Test #9:

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

input:

2 1336
1336 1336

output:

3
1
0

result:

ok 3 tokens

Test #10:

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

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: 0
Accepted
time: 1ms
memory: 3816kb

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:

780135870
780135476
780133126
780115746
779984839
779086101
773744618
746617208
628409426
182368401
707355349
419830171
342550392
778349940
825220795
979080057
177969332
68371210
748001250
187917550
492152134
287983982
592218358
32133349
711757614
602140473
799225822
952989153
1466429
437088327
3596...

result:

ok 43 tokens

Test #12:

score: -100
Wrong Answer
time: 0ms
memory: 3656kb

input:

93 24
1687 2324 1216 2696 2884 1678 1301 1957 1247 526 2519 2252 2141 960 1505 175 315 388 440 892 837 1942 256 1667 641 1629 2565 2837 1200 2427 418 1072 427 1589 969 886 2991 2249 539 1132 949 2425 2616 2107 1259 582 1979 386 177 1860 2825 316 2004 956 1218 2332 1498 2939 1126 1706 404 1604 505 11...

output:

998244352
932051816
10711044
89046951
792318273
838489272
566955198
43888865
483255440
722291523
548143131
339190488
54504286
5405952
64572361
260981990
941743303
658428786
121409046
926769678
140973200
23183677
637382443
890437280
170355920
243899281
940323263
506126351
392145551
3285648
474096654
...

result:

wrong answer 1st words differ - expected: '958346177', found: '998244352'