QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#673933 | #5274. IQ Game | IllusionaryDominance# | ML | 5ms | 4140kb | C++20 | 2.0kb | 2024-10-25 11:55:43 | 2024-10-25 11:55:44 |
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(n+1), inv(n+1);
fac[0]=1; inv[0]=inv[1]=1;
for(int i=1;i<=n;++i) fac[i]=(ll)fac[i-1]*i%p;
for(int i=2;i<=n;++i) inv[i]=(ll)(p-p/i)*inv[p%i]%p;
for(int i=1;i<=n;++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";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3540kb
input:
3 2 3 2 3
output:
665496237
result:
ok 1 number(s): "665496237"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
6 3 4 1 2 4
output:
582309208
result:
ok 1 number(s): "582309208"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3536kb
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: 3620kb
input:
1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
2 1 2 2
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
2 2 1 1 2
output:
499122178
result:
ok 1 number(s): "499122178"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
3 1 2 2
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3548kb
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: 3524kb
input:
3 3 3 1 2 3
output:
2
result:
ok 1 number(s): "2"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
4 1 4 4
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
4 2 4 2 4
output:
499122178
result:
ok 1 number(s): "499122178"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3540kb
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: 3788kb
input:
4 4 4 1 2 3 4
output:
499122179
result:
ok 1 number(s): "499122179"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
5 1 4 4
output:
1
result:
ok 1 number(s): "1"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
5 3 4 2 3 4
output:
199648873
result:
ok 1 number(s): "199648873"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3560kb
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: 3628kb
input:
10 2 3 3 10
output:
99824437
result:
ok 1 number(s): "99824437"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3552kb
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: 3628kb
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: 3628kb
input:
50 3 37 8 37 49
output:
411276675
result:
ok 1 number(s): "411276675"
Test #23:
score: 0
Accepted
time: 0ms
memory: 3560kb
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: 3660kb
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: 3820kb
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: 3692kb
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: 3784kb
input:
200 1 28 28
output:
1
result:
ok 1 number(s): "1"
Test #28:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
200 2 66 66 143
output:
454201182
result:
ok 1 number(s): "454201182"
Test #29:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
200 2 133 107 133
output:
209631316
result:
ok 1 number(s): "209631316"
Test #30:
score: 0
Accepted
time: 0ms
memory: 3608kb
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: 3568kb
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: 3624kb
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: 3832kb
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: 4136kb
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: 4140kb
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: 4112kb
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: 5ms
memory: 4140kb
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: 3600kb
input:
1000000000 1 584008146 584008146
output:
1
result:
ok 1 number(s): "1"
Test #39:
score: -100
Memory Limit Exceeded
input:
1000000000 2 143634686 143634686 490248799