QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#121707	#6408. Classical Counting Problem	SolitaryDream^#	WA	218ms	12616kb	C++20	1.6kb	2023-07-08 18:38:37	2023-07-08 18:38:38

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-07-08 18:38:38]
评测

测评结果：WA
用时：218ms
内存：12616kb

查看

[2023-07-08 18:38:37]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
typedef long long ll;
const int N=105;
const int Mod=998244353;
int a[N];
ll f[N][N*N];
ll res=0;
int n,m,v;
void calc(int s) {
    sort(a+1,a+n+1);
    int p=n;
    memset(f,0,sizeof(f));
    f[0][0]=1;
    DOR(i,n,1) {
        while(a[p]>a[i]+m) {
            FOR(j,0,n) FOR(k,0,n*101) {
                f[j][k]=f[j][k+101-a[p]];
                f[j+1][k+m]=(f[j+1][k+m]-f[j][k])%Mod;
                f[j][k+101-a[p]]=(f[j][k+101-a[p]]-f[j][k])%Mod;
            }
            DOR(j,n,0) DOR(k,n*101,0) {
                f[j+1][k+m]=(f[j+1][k+m]+f[j][k])%Mod;
                f[j][k]=0;
            }
            --p;
            // cerr << " --- " << endl;
        }
        // if(i==1) cerr << a[i] << endl;
        FOR(j,0,s-1) FOR(k,0,n*101) {
            if(k+m*i+(n-i-j)*(a[i]+m-101)>=m*v) {
                // if(i==2 && f[j][k]) cerr << j << ' ' << k << ' ' << f[j][k] << endl;
                res=(res+f[j][k])%Mod;
            }
        }
        DOR(j,n,0) DOR(k,n*101,0) {
            f[j+1][k+m]=(f[j+1][k+m]+f[j][k])%Mod;
            f[j][k+101-a[i]]=(f[j][k+101-a[i]]+f[j][k])%Mod;
            f[j][k]=0;
        }
    }
}
void solve() {
    cin >> n >> m >> v;
    FOR(i,1,n) cin >> a[i];
    res=1;
    calc(v);
    FOR(i,1,n) a[i]=100-a[i];
    v=n-v;
    calc(v-1);
    cout << res << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 8ms

memory: 12452kb

input:

6
3 1 2
1 2 3
3 2 1
1 2 3
10 1 1
0 0 0 0 0 0 0 0 0 0
6 1 2
2 1 1 3 0 2
6 1 5
2 1 1 3 0 2
10 4 8
7 2 3 6 1 6 5 4 6 5

output:

result:

ok 6 numbers

Test #2:

score: 0

Accepted

time: 36ms

memory: 12540kb

input:

output:

result:

ok 50 numbers

Test #3:

score: 0

Accepted

time: 29ms

memory: 12616kb

input:

40
2 20 1
36 90
4 4 3
38 52 64 63
2 89 1
46 65
2 2 1
83 1
3 17 2
19 20 10
2 61 1
33 17
2 91 1
92 59
2 98 1
4 35
2 30 1
66 51
2 4 1
44 16
2 46 1
80 99
3 11 2
80 59 29
3 91 1
80 43 81
2 93 1
74 57
2 78 1
30 77
3 84 1
70 12 29
2 74 1
88 78
3 58 1
22 100 13
3 40 2
79 18 84
4 99 1
32 73 81 73
2 57 1
83 3...

output:

result:

ok 40 numbers

Test #4:

score: 0

Accepted

time: 17ms

memory: 12616kb

input:

30
3 82 1
18 19 77
4 22 1
63 42 11 42
2 60 1
25 90
3 87 2
21 47 5
2 50 1
88 81
4 71 1
63 29 19 68
6 69 3
13 4 71 96 73 39
3 83 2
29 88 28
2 56 1
84 20
2 43 1
8 29
2 48 1
43 9
3 88 1
12 88 58
6 42 4
16 33 47 70 66 42
7 71 1
95 96 18 92 9 20 4
3 11 1
64 46 83
2 7 1
72 49
2 35 1
15 24
3 50 2
82 22 48
4...

output:

result:

ok 30 numbers

Test #5:

score: 0

Accepted

time: 16ms

memory: 12560kb

input:

20
7 41 6
9 17 92 61 58 10 96
2 97 1
84 29
2 83 1
52 65
4 28 3
28 81 53 74
9 69 5
10 80 90 1 91 21 81 96 60
3 66 1
21 9 24
7 88 6
34 21 5 100 51 68 88
2 49 1
62 7
2 6 1
10 1
6 21 1
54 0 16 8 61 16
3 22 2
10 13 75
5 20 1
77 4 16 16 38
5 26 4
31 14 85 69 20
3 31 2
36 58 78
11 39 6
47 7 79 15 34 99 29 ...

output:

result:

ok 20 numbers

Test #6:

score: 0

Accepted

time: 106ms

memory: 12424kb

input:

10
6 32 4
3 64 60 50 71 92
5 17 3
34 22 90 94 35
46 34 44
33 32 55 85 54 4 8 56 87 90 86 88 6 76 12 76 31 80 58 70 99 92 13 59 82 20 25 97 29 64 16 39 57 40 19 17 48 86 6 60 89 99 71 83 95 6
3 62 1
60 0 96
11 85 7
79 92 34 24 79 36 75 89 78 60 5
3 91 2
55 18 29
12 41 5
75 4 81 73 71 93 50 10 43 55 6...

output:

result:

ok 10 numbers

Test #7:

score: 0

Accepted

time: 95ms

memory: 12484kb

input:

5
40 23 31
75 10 19 30 90 96 40 84 96 20 44 61 24 46 39 56 1 73 54 83 85 3 13 14 45 46 39 99 91 99 48 89 28 75 62 5 24 51 61 11
16 62 2
96 5 95 8 67 28 36 20 20 48 89 64 11 50 56 38
15 53 7
43 10 69 97 98 99 38 88 78 74 57 69 0 78 61
27 67 6
74 37 76 8 74 42 76 6 68 94 49 55 10 28 35 25 17 41 65 85 ...

output:

result:

ok 5 number(s): "26111 2098 2839 2739716 3"

Test #8:

score: 0

Accepted

time: 76ms

memory: 12432kb

input:

4
17 100 14
65 87 80 62 80 85 47 14 13 23 91 39 5 82 59 28 46
14 83 8
46 14 88 24 70 57 14 6 63 18 98 68 20 10
40 94 16
91 33 82 64 50 16 2 64 39 76 75 35 20 0 53 14 74 2 44 83 51 67 97 93 61 77 56 12 29 95 77 7 78 46 85 76 76 38 22 94
29 3 5
27 14 12 21 45 42 2 41 92 27 54 46 15 73 38 99 68 96 79 1...

output:

result:

ok 4 number(s): "40145 8703 880766959 64"

Test #9:

score: -100

Wrong Answer

time: 218ms

memory: 12448kb

input:

3
64 81 26
6 35 9 39 70 29 91 9 54 21 83 73 10 93 96 40 50 92 88 87 71 70 22 45 4 23 18 10 88 71 73 5 49 67 12 28 8 61 73 19 27 89 64 65 94 93 87 61 40 4 37 66 72 100 54 33 80 40 26 46 85 59 1 50
26 6 12
56 37 5 5 3 67 52 53 77 55 39 89 86 55 78 34 83 78 75 51 9 43 2 18 86 14
10 89 1
10 41 16 63 14 ...

output:

-74513956
139
230

result:

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