ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#190615 | #3383. 排列计数 | Harry27182 | 100 | 582ms | 23892kb | C++11 | 740b | 2023-10-06 15:13:05 | 2023-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