QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #560983 | #6408. Classical Counting Problem | Y2y7m# | AC ✓ | 20ms | 345332kb | C++14 | 1.2kb | 2024-09-12 19:18:21 | 2024-09-12 19:18:21 |
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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 26188kb
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: 2ms
memory: 7712kb
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: 11880kb
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: 18080kb
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: 32288kb
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: 0ms
memory: 192156kb
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: 163356kb
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: 4ms
memory: 163420kb
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: 3ms
memory: 259100kb
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: 253564kb
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: 4ms
memory: 252276kb
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: 283972kb
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: 0ms
memory: 270592kb
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: 19ms
memory: 345332kb
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: 7ms
memory: 281844kb
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: 8ms
memory: 285552kb
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: 264140kb
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: 20ms
memory: 329240kb
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: 3ms
memory: 275064kb
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: 7ms
memory: 315296kb
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: 267056kb
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: 268932kb
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: 0ms
memory: 269148kb
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: 0ms
memory: 268968kb
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: 271116kb
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: 3ms
memory: 266972kb
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: 269144kb
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: 0ms
memory: 268872kb
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"