QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#429684#8746. 排列游戏ieeAC ✓2105ms19984kbC++17988b2024-06-02 19:16:152024-06-02 19:16:18

Judging History

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

  • [2024-06-02 19:16:18]
  • 评测
  • 测评结果:AC
  • 用时:2105ms
  • 内存:19984kb
  • [2024-06-02 19:16:15]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=505,M=5005,mod=1e9+7,NN=5000,P=80;
int f[P][M][2],ans[N][M],g[P][M][2];
void add(int &x,const int y){if((x+=y)>=mod) x-=mod;}
void init(){
	f[0][0][0]=1;
	for(int i=1; i<=500; i++){
		int U=min(i-1,501-i);
		U=min(U,73);
		for(int j=0; j<=U; j++)
			for(int k=0; k<=NN&&k+j-1<=NN; k++) 
				for(int c:{0,1}) if(f[j][k][c]){
					if(j) 
						add(g[j-1][k+j-1][c^1],1ll*f[j][k][c]*j%mod),
						add(g[j-1][k+j-1][c],j*(j-1ll)%mod*f[j][k][c]%mod);
					if(k+j<=NN)
						add(g[j][k+j][c^1],f[j][k][c]),
						add(g[j][k+j][c],2ll*f[j][k][c]*j%mod);
					if(k+j+1<=NN)
						add(g[j+1][k+j+1][c],f[j][k][c]);
				}
		ans[i][0]=g[0][0][0];
		for(int j=1; j<=NN; j++) ans[i][j]=(ans[i][j-1]+g[0][j][0])%mod;
		swap(f,g);
		memset(g,0,sizeof g);
	}
}

int main(){
	init();
//	return 0;
	int T; scanf("%d",&T);
	while(T--){
		int n,m; scanf("%d%d",&n,&m);
		printf("%d\n",ans[n][m]);
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2105ms
memory: 19884kb

input:

6
2 1
3 1
5 2
7 5
10 20
15 24

output:

1
2
7
331
1570446
73880648

result:

ok 6 lines

Test #2:

score: 0
Accepted
time: 2104ms
memory: 19984kb

input:

990
19 16
20 74
15 32
21 22
14 22
13 36
16 58
14 4
19 44
14 46
21 110
22 86
19 32
16 22
19 17
12 28
20 25
20 59
22 65
21 52
13 32
18 48
14 35
19 37
19 23
21 21
22 90
22 72
21 101
17 20
18 46
21 3
7 12
12 36
16 49
14 15
13 17
20 42
13 42
13 11
22 47
15 22
22 32
19 39
19 65
21 98
19 3
16 24
18 6
22 63...

output:

393168729
246435507
711223131
161825104
979987145
971749586
25952856
2012
726099192
449177299
36423651
633817565
948448065
655086320
599308309
200783520
73244890
494204020
502991859
971176215
490633490
493983396
970265909
703034171
617628639
906119212
329471797
918718406
613644638
276565385
62885054...

result:

ok 990 lines

Test #3:

score: 0
Accepted
time: 2096ms
memory: 19984kb

input:

1000
359 358
370 368
428 429
315 312
405 402
455 453
387 384
385 385
339 340
478 475
439 439
301 302
325 322
457 457
394 393
326 324
431 428
338 336
377 376
324 322
412 413
430 430
317 318
361 361
382 381
498 495
353 351
360 361
426 427
455 452
383 382
470 470
332 331
467 466
494 494
490 487
362 362...

output:

45924051
164071423
548365783
659118999
838332377
635378530
846181906
441908095
40677633
401855064
269095899
404527990
415178598
151295576
196186312
881879915
764063734
328303695
316320167
305189158
752842487
128059020
807509283
679892319
891105784
174676386
511431817
725918523
632585428
122380016
38...

result:

ok 1000 lines

Test #4:

score: 0
Accepted
time: 2101ms
memory: 19900kb

input:

1000
414 5000
403 5000
492 5000
426 4997
422 4999
487 4992
433 4992
458 229
463 231
485 4997
445 4995
428 4999
452 4997
500 4994
484 4994
478 4997
451 225
481 4997
409 4993
416 4994
434 4995
485 4995
488 4994
479 4993
415 4996
457 4998
455 5000
484 4997
495 5000
461 5000
440 4994
467 233
478 4992
49...

output:

898775462
391699513
957397551
372004457
171494594
714422938
494882661
316538268
160292807
966868808
973353968
323915672
233988599
488329134
555876530
831872802
975484650
403590785
786688734
764230002
810440283
909509258
449810241
674593949
674793384
569468973
335196435
845894970
413891292
360114865
...

result:

ok 1000 lines

Test #5:

score: 0
Accepted
time: 2101ms
memory: 19828kb

input:

1000
42 4150
38 529
449 3064
148 1194
225 608
395 261
67 2206
330 1412
442 280
323 4577
114 4578
491 2097
353 1908
104 1457
89 1228
224 63
463 569
357 4108
152 712
285 799
78 4320
343 2187
65 2573
276 1142
232 3251
119 4312
16 935
290 4153
200 2781
188 3692
145 1163
130 776
10 2395
234 4243
262 2781...

output:

313427725
736474183
167778171
483921125
249504291
426630218
640470271
236628570
456175617
133833658
195947577
400554114
32836731
558464694
62988677
390084793
364950769
226938354
555295458
717294565
781468876
970963159
768349275
744743281
310944980
647144599
394870773
919388235
730448114
609516618
62...

result:

ok 1000 lines

Test #6:

score: 0
Accepted
time: 2094ms
memory: 19896kb

input:

1000
256 4996
196 4995
492 386
499 222
499 66
494 129
128 4993
270 4994
498 359
496 308
331 4998
492 372
343 4995
493 189
493 195
494 438
486 4994
493 24
284 4994
500 119
110 4994
493 165
154 4999
176 4999
494 363
12 4998
498 275
385 4999
492 4998
177 4991
494 431
240 4999
492 403
496 246
494 201
49...

output:

651622739
399224728
554375882
39626944
455527272
645049492
989512905
801140014
179099678
60034938
215400726
861168462
696989938
137201040
224649754
945947510
790765487
758221383
692666511
551139017
324852642
861917215
645845740
637323638
934514098
239500800
730940831
860972302
354671366
893747329
64...

result:

ok 1000 lines