QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #123097 | #6408. Classical Counting Problem | chenxinyang2006 | AC ✓ | 134ms | 10324kb | C++14 | 1.7kb | 2023-07-11 18:49:09 | 2023-07-11 18:49:11 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i = (j);i <= (k);i++)
#define per(i,j,k) for(int i = (j);i >= (k);i--)
#define mod 998244353
using namespace std;
inline void add(int &x,int y){
x += y;
if(x >= mod) x -= mod;
}
inline void sub(int &x,int y){
x -= y;
if(x < 0) x += mod;
}
int T,n,m,v;
int a[105];
int dp[105][10005],tmp[105][10005];
void rmv(int val){
rep(i,0,n){
rep(j,0,100 * i) sub(dp[i + 1][j + val],dp[i][j]);
}
}
void ext(int val,int op){//add something size val
if(op == -1){
rmv(val);
return;
}
rep(i,0,n){
rep(j,0,100 * i){
add(tmp[i + 1][j + val],dp[i][j]);
add(tmp[i][j],dp[i][j]);
}
}
rep(i,0,n){
rep(j,0,100 * i){
dp[i][j] = tmp[i][j];
tmp[i][j] = 0;
}
}
}
void solve(){
scanf("%d%d%d",&n,&m,&v);
rep(i,1,n) scanf("%d",&a[i]);
sort(a + 1,a + n + 1);
int pos = 1;
int ans = 1;
rep(i,0,n) fill(dp[i],dp[i] + i * 100 + 1,0);
dp[0][0] = 1;
rep(i,1,n){
while(a[i] - a[pos] > m){
ext(a[pos],-1);
pos++;
}
rep(j,0,n){
if(n - i + j < v) continue;
rep(k,max(0,j * a[i] - v * m),100 * i) add(ans,dp[j][k]);
}
ext(a[i],1);
}
rep(i,0,n) fill(dp[i],dp[i] + i * 100 + 1,0);
// printf("%d\n",ans);
//size >= v,3
pos = n;
dp[0][0] = 1;
per(i,n,1){
while(a[pos] - a[i] > m){
ext(a[pos],-1);
pos--;
}
rep(j,0,n){
int s = n - i + 1 - j;
if(s >= v) continue;
rep(k,0,min((n - i) * 100,j * (a[i] + m) + m * (i + s - v - 1))) add(ans,dp[j][k]);
}
ext(a[i],1);
}
//size < v 2
printf("%d\n",ans);
}
int main(){
// freopen("test.in","r",stdin);
scanf("%d",&T);
while(T--) solve();
return 0;
}
//g++ B.cpp -o B -Wall -Wshadow -O2 -std=c++14 -Wno-unused-result
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5804kb
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:
5 6 1023 23 19 240
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 5752kb
input:
50 2 62 1 67 58 2 23 1 7 39 2 60 1 53 9 2 29 1 3 68 2 52 1 43 76 2 79 1 48 91 2 85 1 18 11 2 34 1 19 24 2 42 1 77 44 2 54 1 80 49 2 90 1 61 55 2 24 1 51 72 2 8 1 9 8 2 83 1 91 0 2 33 1 27 27 2 30 1 8 99 2 52 1 34 87 2 51 1 13 47 2 16 1 0 27 2 63 1 53 76 2 25 1 82 36 2 42 1 53 54 2 12 1 38 70 2 2 1 6...
output:
3 2 3 2 3 3 3 3 3 3 3 3 3 2 3 2 2 3 2 3 2 3 2 2 2 3 3 2 3 3 3 2 2 2 3 3 3 2 3 2 3 3 3 3 3 3 3 3 3 3
result:
ok 50 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 5848kb
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:
2 5 3 2 6 3 3 3 3 2 3 3 7 3 3 6 3 4 4 15 3 7 2 4 5 2 3 3 2 2 7 3 2 3 3 15 3 3 2 7
result:
ok 40 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 5736kb
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:
6 7 2 7 3 12 39 7 2 3 3 6 38 22 3 2 3 5 6 7 7 3 18 2 55 3 4 3 7 7
result:
ok 30 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 5956kb
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:
20 3 3 8 91 7 43 2 2 15 4 9 10 5 117 3 82 15 545 7
result:
ok 20 numbers
Test #6:
score: 0
Accepted
time: 7ms
memory: 8360kb
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:
24 10 85407 5 1426 7 647 2 6 19
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 8ms
memory: 8196kb
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:
26111 2098 2839 2739716 3
result:
ok 5 number(s): "26111 2098 2839 2739716 3"
Test #8:
score: 0
Accepted
time: 9ms
memory: 8192kb
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:
40145 8703 880766959 64
result:
ok 4 number(s): "40145 8703 880766959 64"
Test #9:
score: 0
Accepted
time: 35ms
memory: 9016kb
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: 29ms
memory: 8660kb
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: 116ms
memory: 10092kb
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: 124ms
memory: 10104kb
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: 121ms
memory: 10120kb
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: 134ms
memory: 10080kb
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: 113ms
memory: 10048kb
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: 130ms
memory: 10324kb
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: 111ms
memory: 10064kb
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:
3181458
result:
ok 1 number(s): "3181458"
Test #18:
score: 0
Accepted
time: 134ms
memory: 10076kb
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: 119ms
memory: 10028kb
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: 131ms
memory: 10100kb
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: 94ms
memory: 10084kb
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: 99ms
memory: 10084kb
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: 113ms
memory: 10036kb
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: 116ms
memory: 10064kb
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: 122ms
memory: 10136kb
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: 103ms
memory: 10296kb
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: 103ms
memory: 10036kb
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: 97ms
memory: 10040kb
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"