QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#209172#5274. IQ Game275307894aAC ✓7ms4568kbC++141.3kb2023-10-10 11:04:522023-10-10 11:04:52

Judging History

你现在查看的是最新测评结果

  • [2023-10-10 11:04:52]
  • 评测
  • 测评结果:AC
  • 用时:7ms
  • 内存:4568kb
  • [2023-10-10 11:04:52]
  • 提交

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';
}

Details

Tip: Click on the bar to expand more detailed information

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"