QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#673936 | #5274. IQ Game | IllusionaryDominance# | AC ✓ | 5ms | 4140kb | C++20 | 2.0kb | 2024-10-25 11:57:08 | 2024-10-25 11:57:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(x) (x).begin(), (x).end()
const int p=998244353;
int n, k, s;
int f[205][205];
int pw[205][205];
// int C[205][205];
int fpow(int x, int y)
{
int r=1;
for(;y;y>>=1,x=(ll)x*x%p) if(y&1) r=(ll)r*x%p;
return r;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
cin>>n>>k>>s;
vector<int> a(k);
for(int i=0;i<k;++i) cin>>a[i], a.push_back(a[i]);
if(k==1)
{
cout<<"1\n";
exit(0);
}
int I=lower_bound(a.begin(), a.begin()+k, s)-a.begin();
vector<int> b(k), pre(k);
b[0]=(s+n-a[I+k-1])%n;
for(int i=1;i<k;++i) b[i]=(a[I+i]+n-a[I+i-1])%n;
reverse(b.begin()+1, b.end());
// for(int i=0;i<k;++i) cerr << b[i] << " ";
//1 2
for(int i=0;i<k;++i)
{
pw[i][0]=1;
for(int j=1;j<=k;++j) pw[i][j]=(ll)pw[i][j-1]*b[i]%p;
}
// for(int i=0;i<=200;++i)
// {
// C[i][0]=C[i][i]=1;
// for(int j=1;j<i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
// }
// for(int i=1;i<k;++i) pre[i]=pre[i-1]+b[i];
f[0][0]=1;
vector<int> fac(k+1), inv(k+1);
fac[0]=1; inv[0]=inv[1]=1;
for(int i=1;i<=k;++i) fac[i]=(ll)fac[i-1]*i%p;
for(int i=2;i<=k;++i) inv[i]=(ll)(p-p/i)*inv[p%i]%p;
for(int i=1;i<=k;++i) inv[i]=(ll)inv[i-1]*inv[i]%p;
for(int i=0;i<k-1;++i)
for(int j=0;j<=i;++j)
{
for(int kk=0;kk<=i+1-j;++kk)
{
// cerr<<kk<<" "<<i+1-j<<"?\n";
f[i+1][j+kk]=(f[i+1][j+kk]+(ll)f[i][j]*pw[i+1][kk]%p*inv[kk]%p)%p;
// cerr<<i+1<<" "<<j<<" "<<j+kk<<" "<<f[i+1][j+kk]<<"\n";
}
}
int ans=1;
int invn=fpow(n, p-2);
// cerr<<f[1][1]<<"\n";
for(int i=1;i<k;++i)
{
// cerr << f[k-1][i] << " " << fpow(invn, i) << "\n";
ans=(ans+(ll)f[k-1][i]*fpow(invn, i)%p*fac[i]%p)%p;
}
cout<<ans<<"\n";
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3568kb
input:
3 2 3 2 3
output:
665496237
result:
ok 1 number(s): "665496237"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
6 3 4 1 2 4
output:
582309208
result:
ok 1 number(s): "582309208"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3604kb
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: 0ms
memory: 3532kb
input:
1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
2 1 2 2
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
2 2 1 1 2
output:
499122178
result:
ok 1 number(s): "499122178"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
3 1 2 2
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
3 2 3 1 3
output:
332748119
result:
ok 1 number(s): "332748119"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
3 3 1 1 2 3
output:
2
result:
ok 1 number(s): "2"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
3 3 3 1 2 3
output:
2
result:
ok 1 number(s): "2"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
4 1 4 4
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
4 2 4 2 4
output:
499122178
result:
ok 1 number(s): "499122178"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
4 3 3 2 3 4
output:
935854083
result:
ok 1 number(s): "935854083"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
4 4 1 1 2 3 4
output:
499122179
result:
ok 1 number(s): "499122179"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
4 4 4 1 2 3 4
output:
499122179
result:
ok 1 number(s): "499122179"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
5 1 4 4
output:
1
result:
ok 1 number(s): "1"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
5 3 4 2 3 4
output:
199648873
result:
ok 1 number(s): "199648873"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3548kb
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: 3536kb
input:
10 2 3 3 10
output:
99824437
result:
ok 1 number(s): "99824437"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
10 6 10 2 5 6 7 8 10
output:
146103047
result:
ok 1 number(s): "146103047"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3532kb
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: 0ms
memory: 3604kb
input:
50 3 37 8 37 49
output:
411276675
result:
ok 1 number(s): "411276675"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3548kb
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: 0ms
memory: 3572kb
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: 0ms
memory: 3884kb
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: 3596kb
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: 3536kb
input:
200 1 28 28
output:
1
result:
ok 1 number(s): "1"
Test #28:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
200 2 66 66 143
output:
454201182
result:
ok 1 number(s): "454201182"
Test #29:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
200 2 133 107 133
output:
209631316
result:
ok 1 number(s): "209631316"
Test #30:
score: 0
Accepted
time: 0ms
memory: 3584kb
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: 3852kb
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: 0ms
memory: 3664kb
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: 2ms
memory: 3784kb
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: 5ms
memory: 3928kb
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: 5ms
memory: 3860kb
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: 5ms
memory: 3804kb
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: 2ms
memory: 3972kb
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: 3532kb
input:
1000000000 1 584008146 584008146
output:
1
result:
ok 1 number(s): "1"
Test #39:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
1000000000 2 143634686 143634686 490248799
output:
788008183
result:
ok 1 number(s): "788008183"
Test #40:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
1000000000 2 625148472 130787283 625148472
output:
708092867
result:
ok 1 number(s): "708092867"
Test #41:
score: 0
Accepted
time: 0ms
memory: 3812kb
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: 3824kb
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: 0ms
memory: 3884kb
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: 4016kb
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: 0ms
memory: 3924kb
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: 5ms
memory: 4056kb
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: 5ms
memory: 4140kb
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: 5ms
memory: 3868kb
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"