QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#197858	#6408. Classical Counting Problem	ucup-team870	AC ✓	393ms	12732kb	C++14	3.2kb	2023-10-02 20:58:57	2023-10-02 20:58:58

Judging History

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

[2023-10-02 20:58:58]
评测

测评结果：AC
用时：393ms
内存：12732kb

查看

[2023-10-02 20:58:57]
提交

answer

#include<bits/stdc++.h>
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
#define For(i,j,k) for(int i=j;i<=k;++i)
using namespace std;
typedef long long ll;
const int mo=998244353;
int dp[2][105][11005];
int a[105],cnt[105];
void add(int &x,int y){
    x=(x+y)>=mo?x+y-mo:x+y;
}
int main(){
    //IOS
    int _; cin>>_;
    while(_--){
        int n,m,v; cin>>n>>m>>v;
        For(i,1,n) cin>>a[i];
        sort(a+1,a+1+n);
        ll ans=1;
        //>=v
        For(r,1,n){
            int l=1;
            while(a[r]-a[l]>m) ++l;
            //cout<<' '<<l<<' '<<r<<endl;
            memset(cnt,0,sizeof(cnt)); memset(dp,0,sizeof(dp));
            cnt[l-1]=0;
            For(i,l,r-1) cnt[i]=min(v*m,cnt[i-1]+(a[r]-a[i]));
            //dp, <=nv
            int si=max(v+r-n,0);
            dp[(l-1)&1][0][0]=1;
            For(i,l-1,r-2){
                int tmp=r-1-i,lj=max(0,si-tmp),rj=min(si,i-l+1);
                int qw=i&1,er=qw^1;
                For(j,lj,rj){
                    if (j==si){
                        For(k,0,cnt[i]){
                            add(dp[er][j][k+a[r]-a[i+1]],dp[qw][j][k]);
                            add(dp[er][j][k],dp[qw][j][k]);
                            dp[qw][j][k]=0;
                        }
                    }
                    else{
                        For(k,0,cnt[i]){
                            add(dp[er][j+1][k+a[r]-a[i+1]],dp[qw][j][k]);
                            add(dp[er][j][k],dp[qw][j][k]);
                            dp[qw][j][k]=0;
                        }
                    }
                }
            }
            //cal
            int qw=(r-1)&1;
            For(k,0,v*m) ans+=dp[qw][si][k];
            ans%=mo; //cout<<ans<<endl;
        }
        //cout<<"##"<<endl;
        //<v
        //int nv=n-v+1;
        For(l,1,n-1){
            int r=n;
            while(a[r]-m>a[l]) --r;
            //cout<<' '<<l<<' '<<r<<endl;
            memset(cnt,0,sizeof(cnt)); memset(dp,0,sizeof(dp));
            //cal qian
            int nv=0;
            For(i,1,l-1) nv+=min(m,a[l]+m-a[i]);
            cnt[l]=0;
            For(i,l+1,r) cnt[i]=cnt[i-1]+a[l]+m-a[i];
            int si=max(0,(n-v+1)-(l-1)); //cout<<'@'<<si<<endl;
            dp[l&1][0][0]=1;
            //>=nv
            For(i,l,r-1){
                int tmp=r-i,lj=max(0,si-tmp),rj=i-l;
                //cout<<lj<<' '<<rj<<endl;
                int qw=i&1,er=qw^1;
                For(j,lj,rj){
                    For(k,0,cnt[i]){
                        //cout<<"!!"<<dp[qw][j][k]<<endl;
                        //cout<<'#'<<j+1<<' '<<k+a[l]+m-a[i]<<endl;
                        add(dp[er][j+1][k+a[l]+m-a[1+i]],dp[qw][j][k]);
                        add(dp[er][j][k],dp[qw][j][k]);
                        dp[qw][j][k]=0;
                    }
                }
            }
            //cal
            int qw=r&1;
            For(j,si,r-l) For(k,0,cnt[r]){
                int o=n-j-(l-1);
                //cout<<j<<' '<<k<<' '<<dp[qw][j][k]<<endl;
                if (m*v-m*o-nv<=k) ans+=dp[qw][j][k];
            }
            ans%=mo; //cout<<'@'<<ans<<endl;
        }
        if (v>1) ++ans;
        cout<<ans<<'\n';
    }
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 21ms

memory: 12604kb

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: 47ms

memory: 12732kb

input:

output:

result:

ok 50 numbers

Test #3:

score: 0

Accepted

time: 50ms

memory: 12640kb

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: 57ms

memory: 12648kb

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: 60ms

memory: 12580kb

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: 60ms

memory: 12640kb

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: 61ms

memory: 12708kb

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: 70ms

memory: 12600kb

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: 0

Accepted

time: 86ms

memory: 12724kb

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:

923730397
139
230

result:

ok 3 number(s): "923730397 139 230"

Test #10:

score: 0

Accepted

time: 62ms

memory: 12648kb

input:

2
56 3 30
67 80 38 54 30 78 45 29 61 28 97 77 43 38 37 75 54 84 81 32 16 63 2 90 34 95 54 88 2 44 23 37 87 20 78 71 66 4 21 52 99 15 94 4 66 37 41 100 88 26 76 10 16 36 32 63
44 49 2
24 0 0 33 9 3 41 39 91 46 13 12 43 11 68 28 0 31 16 73 21 22 72 53 79 65 92 80 26 62 93 97 48 90 77 11 4 54 19 21 89 ...

output:

267
343867

result:

ok 2 number(s): "267 343867"

Test #11:

score: 0

Accepted

time: 104ms

memory: 12672kb

input:

1
100 97 9
57 74 56 14 12 8 50 94 81 32 50 70 75 66 44 40 51 71 90 59 66 8 81 31 36 7 81 44 53 85 43 45 49 37 63 56 71 20 81 83 71 51 3 78 47 28 13 41 50 32 23 82 52 32 1 83 63 7 97 78 6 71 88 2 98 14 29 83 74 71 81 96 89 30 48 5 64 74 63 74 96 12 2 36 26 75 7 44 66 93 82 31 13 86 5 96 8 10 71 70

output:

421427517

result:

ok 1 number(s): "421427517"

Test #12:

score: 0

Accepted

time: 63ms

memory: 12652kb

input:

1
100 21 58
67 6 11 89 1 59 8 18 80 33 58 27 5 65 73 17 35 15 31 81 18 12 56 9 49 72 74 74 98 25 68 96 10 75 22 48 43 50 9 38 13 38 82 21 37 66 21 86 83 89 0 73 84 39 77 30 66 26 25 89 14 22 71 75 51 70 41 43 12 70 4 25 20 71 62 1 47 79 66 87 87 95 74 63 97 21 83 28 52 90 90 44 34 55 67 69 90 20 62 66

output:

879050745

result:

ok 1 number(s): "879050745"

Test #13:

score: 0

Accepted

time: 69ms

memory: 12656kb

input:

1
100 49 5
41 64 55 30 13 20 100 9 12 45 33 28 25 64 81 71 19 36 83 14 72 16 99 44 95 12 23 3 18 89 49 80 15 23 59 7 16 79 13 61 67 57 60 31 94 3 86 54 80 0 99 74 47 80 64 78 23 56 64 78 55 85 75 59 61 57 53 38 72 70 61 76 7 77 52 30 41 28 1 55 9 77 33 79 56 67 92 46 6 20 29 13 88 47 5 9 83 86 75 19

output:

778551245

result:

ok 1 number(s): "778551245"

Test #14:

score: 0

Accepted

time: 188ms

memory: 12644kb

input:

1
100 73 50
62 54 10 15 91 71 92 68 12 56 77 86 56 74 77 82 71 91 57 48 24 88 41 90 40 8 50 33 96 97 74 30 77 28 52 100 90 98 75 6 53 44 26 75 84 74 94 99 45 80 42 75 10 87 75 93 59 18 24 21 31 47 46 31 70 34 76 33 10 36 51 60 95 51 99 25 25 78 14 57 100 92 72 95 25 81 0 97 94 50 80 48 8 38 77 39 97...

output:

966167597

result:

ok 1 number(s): "966167597"

Test #15:

score: 0

Accepted

time: 95ms

memory: 12652kb

input:

1
100 97 8
72 76 65 90 46 54 39 59 11 35 74 88 76 73 6 35 55 68 99 71 66 93 16 69 54 73 100 31 74 26 66 81 37 9 44 24 95 60 47 29 6 41 4 96 40 44 69 66 78 70 40 99 74 94 51 73 51 37 64 10 72 42 17 71 23 22 88 39 71 24 7 11 83 24 78 21 8 16 50 92 23 74 43 89 85 59 87 3 81 48 87 50 29 7 37 13 21 93 90...

output:

578242220

result:

ok 1 number(s): "578242220"

Test #16:

score: 0

Accepted

time: 67ms

memory: 12652kb

input:

1
100 21 50
24 66 9 30 59 72 31 84 0 36 49 78 96 72 13 45 7 23 39 36 87 75 92 36 100 13 93 61 62 68 47 32 31 48 37 95 35 89 8 86 82 61 83 39 30 49 77 78 76 49 84 67 4 34 27 20 76 0 92 21 80 71 32 22 33 9 10 67 9 24 53 74 13 98 57 50 35 33 52 59 13 23 3 37 44 5 63 20 35 89 27 19 39 31 8 87 2 91 3 44

output:

474759161

result:

ok 1 number(s): "474759161"

Test #17:

score: 0

Accepted

time: 89ms

memory: 12632kb

input:

1
100 49 99
34 100 64 15 47 22 90 75 100 47 25 79 26 3 43 99 2 68 24 70 39 79 34 82 45 10 87 80 6 98 4 15 3 64 63 87 97 40 80 30 35 47 49 17 54 19 85 79 29 60 61 90 24 30 70 67 44 63 30 43 20 66 3 95 43 98 22 62 81 91 9 57 0 3 71 46 18 83 99 72 36 48 42 20 14 18 39 38 22 87 67 21 60 0 70 95 84 0 95 40

output:

result:

ok 1 number(s): "3181458"

Test #18:

score: 0

Accepted

time: 180ms

memory: 12604kb

input:

1
100 73 46
54 89 87 57 92 73 49 33 32 59 33 36 46 2 50 8 87 56 65 60 13 50 77 28 58 40 69 10 95 39 97 66 65 34 56 46 2 70 52 54 89 67 27 60 77 90 49 90 95 6 59 59 88 70 46 14 69 82 58 55 61 17 76 67 53 86 34 57 8 22 99 8 89 45 62 75 1 21 33 6 16 30 13 47 74 98 47 56 88 49 85 56 49 60 41 69 76 66 86...

output:

353900212

result:

ok 1 number(s): "353900212"

Test #19:

score: 0

Accepted

time: 312ms

memory: 12684kb

input:

1
100 98 91
64 11 31 31 37 23 40 57 32 38 8 38 77 12 47 30 38 10 39 94 67 54 63 74 36 15 62 7 72 69 22 50 58 50 48 38 75 99 46 99 64 86 27 71 0 95 57 91 60 29 2 82 51 78 33 95 61 11 63 66 36 80 80 51 6 40 24 52 79 90 22 60 8 51 41 3 96 71 69 75 6 45 74 63 0 11 23 73 75 47 24 25 70 95 12 42 57 42 99 45

output:

991832540

result:

ok 1 number(s): "991832540"

Test #20:

score: 0

Accepted

time: 152ms

memory: 12640kb

input:

1
100 64 65
80 91 56 8 83 44 39 75 86 39 83 29 32 56 6 44 84 43 6 19 97 94 20 48 69 59 15 79 30 89 98 63 87 95 49 50 53 19 70 16 47 93 78 67 100 59 51 81 82 61 5 62 96 89 33 40 38 19 78 8 7 38 77 55 31 78 27 3 53 20 63 95 38 93 72 12 41 59 38 96 68 47 17 81 14 56 54 83 40 75 9 7 96 55 77 51 48 25 1 78

output:

267899508

result:

ok 1 number(s): "267899508"

Test #21:

score: 0

Accepted

time: 253ms

memory: 12636kb

input:

1
100 100 99
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100...

output:

436278057

result:

ok 1 number(s): "436278057"

Test #22:

score: 0

Accepted

time: 68ms

memory: 12644kb

input:

1
100 1 99
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 1...

output:

131961966

result:

ok 1 number(s): "131961966"

Test #23:

score: 0

Accepted

time: 62ms

memory: 12656kb

input:

1
100 100 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

436278057

result:

ok 1 number(s): "436278057"

Test #24:

score: 0

Accepted

time: 63ms

memory: 12604kb

input:

1
100 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 10...

output:

131961966

result:

ok 1 number(s): "131961966"

Test #25:

score: 0

Accepted

time: 393ms

memory: 12704kb

input:

1
100 100 99
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100...

output:

882499717

result:

ok 1 number(s): "882499717"

Test #26:

score: 0

Accepted

time: 67ms

memory: 12656kb

input:

1
100 1 99
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 1...

output:

882499717

result:

ok 1 number(s): "882499717"

Test #27:

score: 0

Accepted

time: 67ms

memory: 12652kb

input:

1
100 100 1
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

882499717

result:

ok 1 number(s): "882499717"

Test #28:

score: 0

Accepted

time: 66ms

memory: 12732kb

input:

1
100 1 1
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 10...

output:

882499717

result:

ok 1 number(s): "882499717"