QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#563115 | #4007. 树 | Elegia | 100 ✓ | 180ms | 5692kb | C++23 | 1.2kb | 2024-09-14 02:49:19 | 2024-09-14 02:49:19 |
Judging History
answer
/*
飞过天际 走到海角 要拾回快乐
双手摸索 双眼搜索 我尚有感觉
心似刀割 总算醒觉 胜地难闭幕
失去感觉 失去知觉 我尚有躯壳
*/
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
const int _ = 505;
int M;
void add(int &a, int b) { if ((a += b) >= M) a -= M; }
void sub(int &a, int b) { if ((a -= b) < 0) a += M; }
void fam(int &a, int b, int c) { a = (a + b * (ull)c) % M; }
int dp[_][_], tmp[_][_];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int N; cin >> N >> M;
fill(dp[0], dp[0] + N + 1, 1);
for (int i = 1; i != N; ++i) {
memset(tmp, 0, sizeof(tmp));
for (int j = 0; j <= i - 1; ++j)
for (int k = 0; k <= N - i + 1; ++k) {
// T_1 leaf, T_2 notleaf
sub(tmp[j][k], dp[j][k]);
if (k) add(tmp[j][k - 1], dp[j][k]);
// T_1 notleaf, T_2 leaf
sub(tmp[j][k], dp[j][k]);
add(tmp[j + 1][k], dp[j][k]);
}
for (int j = 0; j <= i; ++j) for (int k = 0; k <= N - i; ++k)
dp[j][k] = tmp[j][k] * (ull)j % M * k % M;
int ans = 0; for (int j = 0; j <= i; ++j) add(ans, dp[j][1]);
cout << ans << '\n';
}
return 0;
}
詳細信息
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 0ms
memory: 4664kb
input:
10 577151064
output:
1 2 12 120 1928 44368 1394944 57288704 94480200
result:
ok 9 numbers
Test #2:
score: 10
Accepted
time: 1ms
memory: 4668kb
input:
20 993244853
output:
1 2 12 120 1928 44368 1394944 57288704 500961 765914688 721727386 828519746 578809878 456780398 566346177 528608756 112517275 556697045 568491469
result:
ok 19 numbers
Test #3:
score: 10
Accepted
time: 2ms
memory: 4744kb
input:
48 693389412
output:
1 2 12 120 1928 44368 1394944 57288704 206677872 93448752 311229980 378398080 125171140 600238484 463296372 561311928 329571716 372970120 613153144 269319584 39317988 650402652 168384404 534851656 34323712 215031272 571825440 276426924 452666204 65470204 266586376 160926452 211220340 374251752 67686...
result:
ok 47 numbers
Test #4:
score: 10
Accepted
time: 2ms
memory: 4740kb
input:
50 1000000021
output:
1 2 12 120 1928 44368 1394944 57288704 980235478 468922453 461761187 992820728 222191705 300367066 987453727 296887978 372555015 955448207 763668619 979367361 619326086 386572917 557116733 365169253 648460492 571297313 590441681 957006239 722930829 488988561 87845027 317417171 474978324 228338990 66...
result:
ok 49 numbers
Test #5:
score: 10
Accepted
time: 2ms
memory: 4836kb
input:
97 192608170
output:
1 2 12 120 1928 44368 1394944 57288704 91112970 16405484 80100176 70225008 48127872 176500510 39558398 22009052 21398644 141840316 189415170 192276316 116361256 72578142 52819502 188156950 188410248 176509638 32522564 83818754 28928230 65470204 73978206 122404818 134177072 66078680 21994318 88253492...
result:
ok 96 numbers
Test #6:
score: 10
Accepted
time: 4ms
memory: 4856kb
input:
100 949494599
output:
1 2 12 120 1928 44368 1394944 57288704 131751723 620512065 437266937 358823802 539191611 176844929 543845036 668141281 801642858 243456188 475342903 130532838 725579466 483897130 428695490 554394226 640052996 822143891 597926520 115217926 933551207 829213453 163959314 857759387 609179400 110139502 2...
result:
ok 99 numbers
Test #7:
score: 10
Accepted
time: 176ms
memory: 5632kb
input:
497 1000000008
output:
1 2 12 120 1928 44368 1394944 57288704 980235504 468924936 461954744 10738360 169104280 683889128 729152376 260582112 579791480 979908304 54091792 859511360 218597448 706142496 963545672 872576584 795238216 742370576 97990344 903219288 323919296 630916264 620417560 260644760 296622888 919475496 1351...
result:
ok 496 numbers
Test #8:
score: 10
Accepted
time: 176ms
memory: 5692kb
input:
500 100000007
output:
1 2 12 120 1928 44368 1394944 57288704 80235317 68913066 61031598 25284945 83829366 93302789 23195091 38492081 50524333 45168633 38292434 94285811 38365623 95982662 36801914 61735054 86235593 37972035 84765574 17006323 9043467 77114223 34713566 69229620 79941112 8779017 72345539 90479258 69839002 49...
result:
ok 499 numbers
Test #9:
score: 10
Accepted
time: 175ms
memory: 5564kb
input:
500 996996996
output:
1 2 12 120 1928 44368 1394944 57288704 986241528 45503232 308935592 470590336 414864760 435663620 961356588 861801516 878901872 769566388 645880240 288459596 396098292 38002044 7683212 214317124 691055404 806441252 62125056 689603568 150044048 690550336 767023528 962388620 234709476 688741452 634303...
result:
ok 499 numbers
Test #10:
score: 10
Accepted
time: 180ms
memory: 5576kb
input:
500 1000000009
output:
1 2 12 120 1928 44368 1394944 57288704 980235502 468924745 461939855 9360079 19341771 808233360 364373546 411824196 637521641 722309870 778158561 500366017 204013945 366241252 504956853 971244083 263757822 671356722 954932924 63228980 314686787 611190004 716522667 145587103 747614824 444047280 94915...
result:
ok 499 numbers
Extra Test:
score: 0
Extra Test Passed