ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#199368 | #2969. Permutation | tkswls | 100 | 5847ms | 3248kb | C++11 | 1.3kb | 2023-12-12 11:39:50 | 2023-12-12 12:27:01 |
answer
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int n, f[2][505][505];
int mod;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> mod;
f[1][1][0] = 1;
for (int i = 1; i < n; i++) {
memset(f[!(i & 1)], 0, sizeof(f[!(i & 1)]));
for (int j = 1; j <= i; j++) {
for (int k = 0; k <= i; k++) {
f[!(i & 1)][j + 1][k] = (1ll * f[!(i & 1)][j + 1][k] + f[i & 1][j][k]) % mod;
f[!(i & 1)][j][k] = (1ll * f[!(i & 1)][j ][k] + 1ll * (k) * f[i & 1][j][k]) % mod;
f[!(i & 1)][j][k + 1] = (1ll * f[!(i & 1)][j][k + 1] + 1ll * (i - k) * f[i & 1][j][k]) % mod;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << f[n & 1][i][j] << ' ';
}
cout << "\n";
}
}
//状态定义为 i 点 j 联通 k 上升
//然后就枚举最新点放哪一个点后面,如果放在上升的后面就不变,否则加1
//也可以自成一家就是了
//bukachangbukachangbukachangbukachangbukachangbukachang
//bukachangbukachangbukachangbukachangbukachangbukachang
//bukachangbukachangbukachangbukachangbukachangbukachang
//bukachangbukachangbukachangbukachangbukachangbukachang
//bukachangbukachangbukachangbukachangbukachangbukachang
//bukachangbukachangbukachangbukachangbukachangbukachang
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 3240kb
input:
7 1003742329
output:
1 57 302 302 57 1 0 7 238 868 588 63 0 0 21 406 896 301 0 0 0 35 350 350 0 0 0 0 35 140 0 0 0 0 ...
result:
ok 49 tokens
Test #2:
score: 0
Accepted
time: 0ms
memory: 3244kb
input:
7 1005908347
output:
1 57 302 302 57 1 0 7 238 868 588 63 0 0 21 406 896 301 0 0 0 35 350 350 0 0 0 0 35 140 0 0 0 0 ...
result:
ok 49 tokens
Test #3:
score: 0
Accepted
time: 2ms
memory: 3244kb
input:
8 1003158697
output:
1 120 1191 2416 1191 120 1 0 8 575 4096 6126 2136 127 0 0 28 1176 5586 5376 966 0 0 0 56 1316 369...
result:
ok 64 tokens
Subtask #2:
score: 20
Accepted
Test #4:
score: 20
Accepted
time: 0ms
memory: 3244kb
input:
14 1008272327
output:
1 8178 1479726 45533450 423281535 497349181 258627350 497349181 423281535 45533450 1479726 8178 1 0 ...
result:
ok 196 tokens
Test #5:
score: 0
Accepted
time: 0ms
memory: 3240kb
input:
14 1000175003
output:
1 8178 1479726 45533450 423281535 505446505 274821998 505446505 423281535 45533450 1479726 8178 1 0 ...
result:
ok 196 tokens
Test #6:
score: 0
Accepted
time: 0ms
memory: 3240kb
input:
16 1008354383
output:
1 32752 13824739 848090912 924268159 933206245 814448447 837825803 814448447 933206245 924268159 848...
result:
ok 256 tokens
Subtask #3:
score: 20
Accepted
Test #7:
score: 20
Accepted
time: 3ms
memory: 3248kb
input:
29 1000305707
output:
1 268435427 18753709 982119157 1754789 83409396 823775228 163102026 204069248 776895321 821365717 20...
result:
ok 841 tokens
Test #8:
score: 0
Accepted
time: 3ms
memory: 3244kb
input:
29 1007208353
output:
1 268435427 342172278 20320177 110903685 560053254 862279061 722606366 652510430 948628879 102326883...
result:
ok 841 tokens
Test #9:
score: 0
Accepted
time: 0ms
memory: 3244kb
input:
27 1007480321
output:
1 67108837 196000111 960911729 475500391 510816755 503351388 608513392 214452744 915563150 747212033...
result:
ok 729 tokens
Test #10:
score: 0
Accepted
time: 3ms
memory: 3248kb
input:
30 1005380879
output:
1 536870882 42388845 519054078 873863934 747396596 322567141 486653201 191656597 884861927 83191863 ...
result:
ok 900 tokens
Subtask #4:
score: 20
Accepted
Test #11:
score: 20
Accepted
time: 12ms
memory: 3244kb
input:
96 1000639819
output:
1 311421004 310585473 724707282 533777400 554571191 302145920 251161066 486895743 908562607 65311733...
result:
ok 9216 tokens
Test #12:
score: 0
Accepted
time: 16ms
memory: 3248kb
input:
100 1003802131
output:
1 994609193 632942510 371240043 812497201 294840329 556171992 333601715 359103085 931099416 60224570...
result:
ok 10000 tokens
Test #13:
score: 0
Accepted
time: 15ms
memory: 3248kb
input:
97 1002483127
output:
1 336331945 961633661 113825366 688959771 501241618 228604130 181131083 829937475 450082320 27051807...
result:
ok 9409 tokens
Test #14:
score: 0
Accepted
time: 13ms
memory: 3248kb
input:
98 1000416419
output:
1 229455444 143734239 779359341 456276337 551210048 498400150 363198812 927715928 626953750 52666663...
result:
ok 9604 tokens
Test #15:
score: 0
Accepted
time: 18ms
memory: 3248kb
input:
100 1001867441
output:
1 208099198 698623853 767738665 908864362 302494813 483054394 954365291 754724365 255613018 79550422...
result:
ok 10000 tokens
Subtask #5:
score: 30
Accepted
Test #16:
score: 30
Accepted
time: 1071ms
memory: 3244kb
input:
474 1005071167
output:
1 225626748 586604333 281795030 306731364 635290380 280462188 257576838 136612850 877208749 64548184...
result:
ok 224676 tokens
Test #17:
score: 0
Accepted
time: 1235ms
memory: 3248kb
input:
496 1006762327
output:
1 97954907 885702359 713212070 828107089 456791814 299010647 979852690 784449672 261894137 250182811...
result:
ok 246016 tokens
Test #18:
score: 0
Accepted
time: 1065ms
memory: 3248kb
input:
473 1007938927
output:
1 946026175 134533924 705623969 645335048 302379660 564001154 903259940 302405006 956547682 47349298...
result:
ok 223729 tokens
Test #19:
score: 0
Accepted
time: 1123ms
memory: 3244kb
input:
482 1003717003
output:
1 238788490 702039841 966078319 820428933 954623688 246482786 448118467 729584515 897533618 16346905...
result:
ok 232324 tokens
Test #20:
score: 0
Accepted
time: 1268ms
memory: 3248kb
input:
500 1005063623
output:
1 241345232 440316626 345875340 761840557 480022589 966162523 75907203 659275436 965074746 56569168 ...
result:
ok 250000 tokens
Extra Test:
score: 0
Extra Test Passed