QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #57957 | #4836. Tree | Sorting# | TL | 60ms | 6196kb | C++ | 971b | 2022-10-23 23:09:23 | 2022-10-23 23:09:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
ll mod;
ll n;
ll dp[2][501][501];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin >> n >> mod;
for(int i=0; i<=n ;i++){
dp[0][0][i]=mod-1;
dp[0][1][i]=1;
}
for(int r=1; r<n ;r++){
int c=r%2;
int p=c^1;
for(int i=0; i<=n ;i++){
for(int j=0; j<=n ;j++){
dp[p][i][j]=dp[p][i][j]*i*j%mod;
dp[c][i][j]=0;
}
}
{//use x
for(int i=0; i<=n ;i++){
for(int j=0; j<=n ;j++){
dp[c][i][j]=(dp[c][i][j]+mod-dp[p][i][j])%mod;
if(i<n) dp[c][i+1][j]=(dp[c][i+1][j]+dp[p][i][j])%mod;
}
}
}
{//use y
for(int i=0; i<=n ;i++){
for(int j=0; j<=n ;j++){
dp[c][i][j]=(dp[c][i][j]+mod-dp[p][i][j])%mod;
if(j>0) dp[c][i][j-1]=(dp[c][i][j-1]+dp[p][i][j])%mod;
}
}
}
ll ans=0;
for(int j=0; j<=n ;j++) ans=(ans+dp[c][j][0])%mod;
cout << ans << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5632kb
input:
5 998244353
output:
1 2 12 120
result:
ok 4 number(s): "1 2 12 120"
Test #2:
score: 0
Accepted
time: 7ms
memory: 5752kb
input:
50 10007
output:
1 2 12 120 1928 4340 3971 8636 815 1971 1138 4657 4784 7523 951 6104 2967 9876 5030 4921 4936 8826 5951 3506 1431 7190 8667 655 5143 4548 1416 7845 3569 4220 8273 2745 1650 7824 8477 3716 366 9885 5166 7416 6843 1214 7262 3538 681
result:
ok 49 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
10 577151064
output:
1 2 12 120 1928 44368 1394944 57288704 94480200
result:
ok 9 numbers
Test #4:
score: 0
Accepted
time: 3ms
memory: 5736kb
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 #5:
score: 0
Accepted
time: 6ms
memory: 5852kb
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 #6:
score: 0
Accepted
time: 7ms
memory: 3932kb
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 #7:
score: 0
Accepted
time: 60ms
memory: 6196kb
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 #8:
score: 0
Accepted
time: 41ms
memory: 6040kb
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 #9:
score: -100
Time Limit Exceeded
input:
497 1000000008