UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#190615#3383. 排列计数Harry27182100582ms23892kbC++11740b2023-10-06 15:13:052023-10-06 18:35:04

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2000,mod=1000000007;
int f[2005][2005][2],T,n,k;
void Add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    f[1][0][0]=1;
    for(int i=2;i<=N;i++)
    {
    	for(int j=0;j<i-1;j++)
    	{
    		Add(f[i][j+1][1],2ll*f[i-1][j][0]%mod);
    		Add(f[i][j-1][0],1ll*j*f[i-1][j][0]%mod);
    		Add(f[i][j][0],1ll*(i-2-j)*f[i-1][j][0]%mod);
			Add(f[i][j+1][1],f[i-1][j][1]);
			Add(f[i][j][1],f[i-1][j][1]);
			Add(f[i][j-1][0],1ll*(j-1)*f[i-1][j][1]%mod);
			Add(f[i][j][0],1ll*(i-2-(j-1))*f[i-1][j][1]%mod); 
		}
	}
	cin>>T;
	while(T--)
	{
		cin>>n>>k;
		cout<<(f[n][k][0]+f[n][k][1])%mod<<'\n';
	}
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 24ms
memory: 23884kb

input:

10
2 0
5 1
6 3
3 0
7 5
4 2
1 0
8 7
5 0
5 2

output:

0
40
120
0
28
10
1
2
14
48

result:

ok 10 numbers

Test #2:

score: 10
Accepted
time: 29ms
memory: 23888kb

input:

5000
7 1
6 0
6 4
10 5
5 2
5 2
1 0
9 4
3 0
4 0
1 0
1 0
5 3
9 5
6 0
10 5
2 0
1 0
10 6
7 4
6 1
7 0
4 2
...

output:

1580
90
22
54304
48
48
1
22120
0
2
1
1
16
4448
90
54304
0
1
7900
226
230
646
10
5242
2
1
256
120
256...

result:

ok 5000 numbers

Test #3:

score: 10
Accepted
time: 26ms
memory: 23884kb

input:

10
16 4
15 2
16 12
16 13
15 10
16 6
15 9
16 7
16 12
16 12

output:

581566967
460233251
68526
2710
928874
17532712
12781476
855005425
68526
68526

result:

ok 10 numbers

Test #4:

score: 10
Accepted
time: 30ms
memory: 23888kb

input:

5000
17 8
16 14
9 4
11 7
17 11
16 2
17 16
12 5
17 2
13 2
8 0
11 0
17 2
9 6
12 11
16 8
14 6
16 11
11 ...

output:

138966533
82
22120
12816
35340456
318111669
2
9086628
199486786
840969777
5242
5296790
199486786
540...

result:

ok 5000 numbers

Test #5:

score: 10
Accepted
time: 21ms
memory: 23888kb

input:

5000
1456 1455
1129 1128
1740 1739
1993 1991
13 12
1666 1665
1624 1622
324 323
1343 1341
517 515
764...

output:

2
2
2
11944
2
2
9730
2
8044
3088
2
2
2
2
2
2062
2
2
11194
2872
2
10906
8602
5014
9394
10276
2746
727...

result:

ok 5000 numbers

Test #6:

score: 10
Accepted
time: 27ms
memory: 23888kb

input:

5000
1512 1511
576 574
1001 999
17 15
62 60
321 319
1074 1073
679 678
1349 1346
479 478
1357 1354
46...

output:

2
3442
5992
88
358
1912
2
2
30781680
2
31148776
3622548
19814766
2
4654
3591226
9304
2
2
2
2
5870010...

result:

ok 5000 numbers

Test #7:

score: 10
Accepted
time: 26ms
memory: 23888kb

input:

5000
21 5
536 92
1923 1468
228 34
669 473
1877 191
1590 1240
595 283
1592 455
1431 143
412 394
1854 ...

output:

54209947
315711882
882079680
796859827
485176182
390915536
687425576
912171587
682756769
305725812
7...

result:

ok 5000 numbers

Test #8:

score: 10
Accepted
time: 21ms
memory: 23888kb

input:

5000
1289 510
1643 1246
1972 433
1980 1339
1882 1658
1748 948
1806 846
1944 1005
1941 134
1903 1216
...

output:

962754391
439704646
245586907
147985120
588126189
365471651
611789713
636487942
288153152
837841585
...

result:

ok 5000 numbers

Test #9:

score: 10
Accepted
time: 208ms
memory: 23888kb

input:

500000
425 285
1647 880
164 116
1369 1116
1448 1096
1619 744
507 247
1446 612
1111 882
1522 202
1574...

output:

872154174
396303714
583079896
887549697
727232216
329089713
362175302
526719073
427715444
511414460
...

result:

ok 500000 numbers

Test #10:

score: 10
Accepted
time: 170ms
memory: 23892kb

input:

500000
1497 392
1808 47
1786 254
1987 1279
1473 312
1723 662
1830 594
1456 319
2000 1392
1561 412
18...

output:

383156697
721088138
292394234
159045024
685313232
643610915
477741929
257583674
732843624
78339813
2...

result:

ok 500000 numbers