QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #560978 | #6408. Classical Counting Problem | Y2y7m# | AC ✓ | 35ms | 344804kb | C++14 | 1.2kb | 2024-09-12 19:17:13 | 2024-09-12 19:17:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=110,mod=998244353;
int n,m,v;
int a[maxn];
int f[maxn][maxn][maxn*maxn];
void chkmod(int &x,int y)
{
x=(x+y)%mod;
}
void sol()
{
cin>>n>>m>>v;
for(int i=1;i<=n;i++) cin>>a[i];
if(v>n/2)
{
v=n-v;
sort(a+1,a+1+n);
int ans=0;
for(int i=1;i<=n;i++)
{
f[i][i][0]=1;
for(int j=i+1;j<=n;j++)
{
for(int k=0;k<=m*v;k++)
{
f[i][j][k]=0;
if(k>=a[j]-a[i]&&a[j]-a[i]<=m) f[i][j][k]=f[i][j-1][k-(a[j]-a[i])];
f[i][j][k]+=f[i][j-1][k];
f[i][j][k]%=mod;
}
}
for(int k=0;k<=m*v;k++) ans=(ans+f[i][n][k])%mod;
}
cout<<ans<<endl;
return ;
}
sort(a+1,a+1+n,greater<int>());
int ans=0;
for(int i=1;i<=n;i++)
{
f[i][i][0]=1;
for(int j=i+1;j<=n;j++)
{
for(int k=0;k<=m*v;k++)
{
f[i][j][k]=0;
if(k>=a[i]-a[j]&&a[i]-a[j]<=m) f[i][j][k]=f[i][j-1][k-(a[i]-a[j])];
f[i][j][k]+=f[i][j-1][k];
f[i][j][k]%=mod;
}
}
for(int k=0;k<=m*v;k++) ans=(ans+f[i][n][k])%mod;
}
cout<<ans<<endl;
}
signed main()
{
//freopen("test.in","r",stdin);
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
sol();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 30368kb
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: 0ms
memory: 7840kb
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: 3ms
memory: 13972kb
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: 0ms
memory: 20060kb
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: 30244kb
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: 4ms
memory: 155764kb
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: 0ms
memory: 157336kb
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: 0ms
memory: 141268kb
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: 15ms
memory: 220180kb
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: 0ms
memory: 213260kb
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: 11ms
memory: 265244kb
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: 11ms
memory: 272912kb
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: 4ms
memory: 258664kb
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: 20ms
memory: 338400kb
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: 11ms
memory: 270772kb
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: 12ms
memory: 276576kb
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: 0ms
memory: 270128kb
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: 35ms
memory: 344804kb
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: 4ms
memory: 291412kb
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: 19ms
memory: 313752kb
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: 0ms
memory: 269164kb
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: 0ms
memory: 261036kb
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: 8ms
memory: 271180kb
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: 3ms
memory: 268892kb
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: 3ms
memory: 273052kb
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: 0ms
memory: 268992kb
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: 0ms
memory: 271088kb
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: 4ms
memory: 266972kb
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"