QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#209172 | #5274. IQ Game | 275307894a | AC ✓ | 7ms | 4568kb | C++14 | 1.3kb | 2023-10-10 11:04:52 | 2023-10-10 11:04:52 |
Judging History
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=200+5,M=N*4,K=600+5,mod=998244353,Mod=mod-1;const db eps=1e-6;const ll INF=1e15+7;mt19937 rnd(263082);
int n,k,s,A[N];ll dp[N][N],C[N][N];
ll mpow(ll x,int y=mod-2){ll ans=1;while(y) y&1&&(ans=ans*x%mod),y>>=1,x=x*x%mod;return ans;}
void Solve(){
int i,j,h;scanf("%d%d%d",&n,&k,&s);ll inv=mpow(n);
for(i=1;i<=k;i++) scanf("%d",&A[i]),A[i]=(A[i]-s+n)%n,A[i]=(n-A[i])%n;
for(i=0;i<=k;i++) for(C[i][0]=j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
sort(A+1,A+k+1);A[k+1]=n;
dp[0][0]=1;
for(i=1;i<=k;i++){
for(j=0;j<i;j++){
ll w=1,pw=(A[i+1]-A[i])*inv%mod;
for(h=0;h<=j;h++) {
dp[i][j]+=dp[i-1][j-h]*w%mod*C[j][h]%mod;
w=w*pw%mod;
}
dp[i][j]%=mod;
}
}
ll ans=0;for(i=0;i<=k;i++) ans+=dp[k][i];printf("%lld\n",ans%mod);
}
int main(){
int t=1;
// scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3748kb
input:
3 2 3 2 3
output:
665496237
result:
ok 1 number(s): "665496237"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3892kb
input:
6 3 4 1 2 4
output:
582309208
result:
ok 1 number(s): "582309208"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
8 8 5 1 2 3 4 5 6 7 8
output:
499122181
result:
ok 1 number(s): "499122181"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3928kb
input:
1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
2 1 2 2
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
2 2 1 1 2
output:
499122178
result:
ok 1 number(s): "499122178"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
3 1 2 2
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
3 2 3 1 3
output:
332748119
result:
ok 1 number(s): "332748119"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
3 3 1 1 2 3
output:
2
result:
ok 1 number(s): "2"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
3 3 3 1 2 3
output:
2
result:
ok 1 number(s): "2"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
4 1 4 4
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
4 2 4 2 4
output:
499122178
result:
ok 1 number(s): "499122178"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
4 3 3 2 3 4
output:
935854083
result:
ok 1 number(s): "935854083"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
4 4 1 1 2 3 4
output:
499122179
result:
ok 1 number(s): "499122179"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
4 4 4 1 2 3 4
output:
499122179
result:
ok 1 number(s): "499122179"
Test #16:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
5 1 4 4
output:
1
result:
ok 1 number(s): "1"
Test #17:
score: 0
Accepted
time: 1ms
memory: 3936kb
input:
5 3 4 2 3 4
output:
199648873
result:
ok 1 number(s): "199648873"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
5 5 3 1 2 3 4 5
output:
3
result:
ok 1 number(s): "3"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
10 2 3 3 10
output:
99824437
result:
ok 1 number(s): "99824437"
Test #20:
score: 0
Accepted
time: 1ms
memory: 3948kb
input:
10 6 10 2 5 6 7 8 10
output:
146103047
result:
ok 1 number(s): "146103047"
Test #21:
score: 0
Accepted
time: 1ms
memory: 3936kb
input:
10 9 4 1 2 3 4 5 7 8 9 10
output:
463868913
result:
ok 1 number(s): "463868913"
Test #22:
score: 0
Accepted
time: 1ms
memory: 3888kb
input:
50 3 37 8 37 49
output:
411276675
result:
ok 1 number(s): "411276675"
Test #23:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
50 10 13 1 13 20 27 28 32 34 35 49 50
output:
221421997
result:
ok 1 number(s): "221421997"
Test #24:
score: 0
Accepted
time: 1ms
memory: 3960kb
input:
50 25 12 1 4 5 10 11 12 14 16 19 21 22 27 28 29 30 31 33 34 37 38 39 45 47 49 50
output:
754768470
result:
ok 1 number(s): "754768470"
Test #25:
score: 0
Accepted
time: 1ms
memory: 3904kb
input:
50 40 22 2 3 4 5 6 7 8 12 13 14 15 17 18 19 20 21 22 23 24 25 26 28 29 30 31 32 33 34 35 36 37 39 40 41 42 43 45 46 47 50
output:
16385632
result:
ok 1 number(s): "16385632"
Test #26:
score: 0
Accepted
time: 1ms
memory: 3968kb
input:
50 49 29 1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
output:
501281691
result:
ok 1 number(s): "501281691"
Test #27:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
200 1 28 28
output:
1
result:
ok 1 number(s): "1"
Test #28:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
200 2 66 66 143
output:
454201182
result:
ok 1 number(s): "454201182"
Test #29:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
200 2 133 107 133
output:
209631316
result:
ok 1 number(s): "209631316"
Test #30:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
200 5 96 60 86 96 121 130
output:
713590253
result:
ok 1 number(s): "713590253"
Test #31:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
200 14 89 3 7 30 42 54 64 80 82 89 105 133 160 176 184
output:
105441194
result:
ok 1 number(s): "105441194"
Test #32:
score: 0
Accepted
time: 1ms
memory: 3932kb
input:
200 42 152 4 9 17 20 35 40 43 49 52 71 74 76 81 83 85 92 93 97 98 104 111 113 124 132 134 139 140 141 144 148 149 151 152 153 157 164 172 181 192 195 199 200
output:
547988971
result:
ok 1 number(s): "547988971"
Test #33:
score: 0
Accepted
time: 0ms
memory: 4232kb
input:
200 132 98 2 3 6 7 8 15 16 17 18 20 22 23 26 27 28 30 31 32 34 35 36 38 39 41 44 45 46 48 50 53 54 55 56 57 58 59 60 61 64 68 69 72 73 76 77 78 79 81 82 83 84 85 86 87 88 89 92 95 96 97 98 100 102 103 104 105 106 107 108 109 110 112 114 115 116 119 120 121 122 123 124 125 127 130 131 133 134 135 136...
output:
697737806
result:
ok 1 number(s): "697737806"
Test #34:
score: 0
Accepted
time: 7ms
memory: 4472kb
input:
200 199 1 1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
544578651
result:
ok 1 number(s): "544578651"
Test #35:
score: 0
Accepted
time: 7ms
memory: 4568kb
input:
200 199 200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 95 96 97 98 99 100...
output:
492091840
result:
ok 1 number(s): "492091840"
Test #36:
score: 0
Accepted
time: 7ms
memory: 4452kb
input:
200 200 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...
output:
499122277
result:
ok 1 number(s): "499122277"
Test #37:
score: 0
Accepted
time: 7ms
memory: 4416kb
input:
200 200 200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...
output:
499122277
result:
ok 1 number(s): "499122277"
Test #38:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
1000000000 1 584008146 584008146
output:
1
result:
ok 1 number(s): "1"
Test #39:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
1000000000 2 143634686 143634686 490248799
output:
788008183
result:
ok 1 number(s): "788008183"
Test #40:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
1000000000 2 625148472 130787283 625148472
output:
708092867
result:
ok 1 number(s): "708092867"
Test #41:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
1000000000 5 151559002 95471916 151559002 583238649 818909076 923651296
output:
775804433
result:
ok 1 number(s): "775804433"
Test #42:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
1000000000 14 205525617 111116916 205525617 243011849 273099893 284288753 314909659 339014539 645710065 731239674 752446721 769648839 789762353 882826624 995895973
output:
450520152
result:
ok 1 number(s): "450520152"
Test #43:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
1000000000 42 865997896 6868421 39816218 63566993 91094555 107013042 108056448 117381010 121861189 126253576 133844271 182455123 218365482 248658016 276646670 300024164 316030537 324539893 348544216 360102712 385863758 404468357 431231451 447180169 494978380 518754701 520854460 567587770 581920139 6...
output:
164406954
result:
ok 1 number(s): "164406954"
Test #44:
score: 0
Accepted
time: 2ms
memory: 4260kb
input:
1000000000 132 818493345 7391593 16222676 16728141 21745953 29333193 31188659 38084625 45401834 45924061 51938800 55381065 58521522 58912656 66911881 68351994 83837784 88530233 91327734 108866516 113286389 118258521 149411552 154259554 172406123 196024798 216432936 222418757 224056724 228826957 2593...
output:
757383914
result:
ok 1 number(s): "757383914"
Test #45:
score: 0
Accepted
time: 7ms
memory: 4424kb
input:
1000000000 199 10681544 10681544 23177378 37659235 49989953 53393710 61018524 62698570 65610111 67123127 68465120 72989626 95514621 97942856 101745615 117638431 126271889 131429697 132191147 133615010 145840977 148017323 161280418 171542888 171760515 174439210 178859787 179544188 192118010 196229683...
output:
295777843
result:
ok 1 number(s): "295777843"
Test #46:
score: 0
Accepted
time: 3ms
memory: 4460kb
input:
1000000000 199 994808313 2707463 12344045 14140946 14857970 22582954 25580417 44389041 50691819 56661919 60680768 72527094 80573726 97445667 98167297 98446378 101716264 108638977 109355441 109691948 110735111 111017207 121934675 124220281 126079617 128591556 136313192 146221552 151218030 156276339 1...
output:
961385715
result:
ok 1 number(s): "961385715"
Test #47:
score: 0
Accepted
time: 7ms
memory: 4396kb
input:
1000000000 200 3890484 3890484 11749010 11906913 16835982 22023496 27364740 28762232 32696137 37856675 39468187 53690489 55784771 63468013 64027836 64213198 65294191 67142061 77567023 79511482 85199271 88155873 97619048 101110467 103270300 110903625 114541922 124852100 125270552 133660962 133815707 ...
output:
702683742
result:
ok 1 number(s): "702683742"
Test #48:
score: 0
Accepted
time: 7ms
memory: 4456kb
input:
1000000000 200 991106656 9679423 13244204 15575122 16413713 28107751 30390226 34027699 39891292 42578120 52517304 66319727 81066860 81486839 82624725 91168249 97765400 99154793 99372988 100307626 102763210 110009725 111808075 119865073 124641551 127902883 144016462 145656730 171445047 172859397 1771...
output:
430656495
result:
ok 1 number(s): "430656495"