QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #339529 | #8047. DFS Order 4 | yyandy | AC ✓ | 310ms | 6316kb | C++14 | 849b | 2024-02-27 15:20:58 | 2024-02-27 15:20:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
int F[805][805],fac[805],inv[805];
struct Kasumul{
int p; ll m;
Kasumul(int tp=998244353):p(tp),m(ll((lll(1)<<63)/tp)){}
ll calc(ll x){
ll q=((lll(x)*m)>>63);
return x-q*p;
}
};
int main(){
// freopen("tree.in","r",stdin);
// freopen("tree.out","w",stdout);
int n,P;
cin>>n>>P;
Kasumul modint=Kasumul(P);
fac[0]=inv[1]=1;
for(int i=1;i<=n;++i)
fac[i]=1ll*fac[i-1]*i%P;
for(int i=2;i<=n;++i)
inv[i]=P-1ll*(P/i)*inv[P%i]%P;
F[1][0]=1;
for(int i=2;i<=n;++i)
for(int j=0;j<=n-i;++j){
F[i][j]=F[i-1][0];
for(int k=2;k+1<i;++k)
F[i][j]=modint.calc(F[i][j]+1ll*(F[k][0]-F[k][i-k-1+j])*F[i-k][j]);
F[i][j]=1ll*F[i][j]*inv[i+j-1]%P;
}
cout<<(1ll*F[n][0]*fac[n-1]%P+P)%P;
}
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
4 114514199
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
10 998244353
output:
11033
result:
ok 1 number(s): "11033"
Test #3:
score: 0
Accepted
time: 1ms
memory: 4092kb
input:
100 1000000007
output:
270904395
result:
ok 1 number(s): "270904395"
Test #4:
score: 0
Accepted
time: 261ms
memory: 5964kb
input:
756 1001338769
output:
901942543
result:
ok 1 number(s): "901942543"
Test #5:
score: 0
Accepted
time: 303ms
memory: 6272kb
input:
793 1009036033
output:
301770320
result:
ok 1 number(s): "301770320"
Test #6:
score: 0
Accepted
time: 265ms
memory: 5960kb
input:
759 1005587659
output:
846376219
result:
ok 1 number(s): "846376219"
Test #7:
score: 0
Accepted
time: 281ms
memory: 6232kb
input:
773 1007855479
output:
1398019
result:
ok 1 number(s): "1398019"
Test #8:
score: 0
Accepted
time: 257ms
memory: 5904kb
input:
751 1006730639
output:
321287237
result:
ok 1 number(s): "321287237"
Test #9:
score: 0
Accepted
time: 286ms
memory: 6020kb
input:
778 1007760653
output:
430322899
result:
ok 1 number(s): "430322899"
Test #10:
score: 0
Accepted
time: 308ms
memory: 6104kb
input:
798 1007543827
output:
688720826
result:
ok 1 number(s): "688720826"
Test #11:
score: 0
Accepted
time: 303ms
memory: 6016kb
input:
796 1004841413
output:
258829347
result:
ok 1 number(s): "258829347"
Test #12:
score: 0
Accepted
time: 283ms
memory: 6024kb
input:
775 1005185189
output:
744278608
result:
ok 1 number(s): "744278608"
Test #13:
score: 0
Accepted
time: 310ms
memory: 6316kb
input:
800 1006012831
output:
508549367
result:
ok 1 number(s): "508549367"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
1 1001338769
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
2 1001338769
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
9 1009036033
output:
1780
result:
ok 1 number(s): "1780"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
14 1001338769
output:
43297358
result:
ok 1 number(s): "43297358"
Extra Test:
score: 0
Extra Test Passed