QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #361196 | #8047. DFS Order 4 | yyyyxh | AC ✓ | 649ms | 6768kb | C++14 | 806b | 2024-03-22 21:53:19 | 2024-03-22 21:53:19 |
Judging History
answer
#include <cstdio>
using namespace std;
typedef __int128 lll;
typedef long long ll;
const int N=803;
int n,p;
struct barrett{
ll m;
barrett():m(((lll)1<<64)/p){}
friend ll operator%(ll x,barrett t){
x-=(((lll)x*t.m)>>64)*p;
return x;
}
};
int inv[N];
int f[N][N],g[N][N];
int main(){
scanf("%d%d",&n,&p);
barrett P;
inv[1]=1;
for(int i=2;i<=n;++i) inv[i]=((ll)inv[p%i]*(p-p/i))%P;
f[1][0]=1;
for(int i=1;i<=n;++i)
for(int j=0;i+j<=n;++j){
g[i][j]=(ll)f[i][0]*inv[i+j]%P;
for(int k=2;k<i;++k){
g[i][j]=(g[i][j]-(ll)inv[i+j]*f[k][i+j-k]%P*g[i-k][j])%P;
g[i][j]=(g[i][j]+(ll)inv[i+j]*f[k][0]%P*g[i-k][j])%P;
}
f[i+1][j]=g[i][j];
}
int res=(ll)f[n][0]*inv[n]%P;
for(int i=1;i<=n;++i) res=(ll)res*i%P;
printf("%d\n",res%p);
return 0;
}
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3816kb
input:
4 114514199
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
10 998244353
output:
11033
result:
ok 1 number(s): "11033"
Test #3:
score: 0
Accepted
time: 1ms
memory: 4120kb
input:
100 1000000007
output:
270904395
result:
ok 1 number(s): "270904395"
Test #4:
score: 0
Accepted
time: 547ms
memory: 6568kb
input:
756 1001338769
output:
901942543
result:
ok 1 number(s): "901942543"
Test #5:
score: 0
Accepted
time: 631ms
memory: 6768kb
input:
793 1009036033
output:
301770320
result:
ok 1 number(s): "301770320"
Test #6:
score: 0
Accepted
time: 545ms
memory: 6576kb
input:
759 1005587659
output:
846376219
result:
ok 1 number(s): "846376219"
Test #7:
score: 0
Accepted
time: 583ms
memory: 6700kb
input:
773 1007855479
output:
1398019
result:
ok 1 number(s): "1398019"
Test #8:
score: 0
Accepted
time: 532ms
memory: 6624kb
input:
751 1006730639
output:
321287237
result:
ok 1 number(s): "321287237"
Test #9:
score: 0
Accepted
time: 592ms
memory: 6640kb
input:
778 1007760653
output:
430322899
result:
ok 1 number(s): "430322899"
Test #10:
score: 0
Accepted
time: 641ms
memory: 6668kb
input:
798 1007543827
output:
688720826
result:
ok 1 number(s): "688720826"
Test #11:
score: 0
Accepted
time: 632ms
memory: 6692kb
input:
796 1004841413
output:
258829347
result:
ok 1 number(s): "258829347"
Test #12:
score: 0
Accepted
time: 589ms
memory: 6660kb
input:
775 1005185189
output:
744278608
result:
ok 1 number(s): "744278608"
Test #13:
score: 0
Accepted
time: 649ms
memory: 6708kb
input:
800 1006012831
output:
508549367
result:
ok 1 number(s): "508549367"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
1 1001338769
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
2 1001338769
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
9 1009036033
output:
1780
result:
ok 1 number(s): "1780"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
14 1001338769
output:
43297358
result:
ok 1 number(s): "43297358"
Extra Test:
score: 0
Extra Test Passed