QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#716998 | #9561. 树数叔术 | thomaswmy | 0 | 566ms | 4104kb | C++14 | 1.1kb | 2024-11-06 16:35:38 | 2024-11-06 16:35:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=160;
typedef long long ll;
int qpow(int x,ll y,int p) {
int z=1;
for(;y;y>>=1) {
if(y&1) z=1ll*z*x%p;
x=1ll*x*x%p;
}
return z;
}
int n,V,Mod;
int fac[N],inv[N];
int f[2][N][N];
int C(int x,int y) {
if(x<y || y<0) return 0;
return 1ll*fac[x]*inv[y]%Mod*inv[x-y]%Mod;
}
int main() {
scanf("%d%d%d",&n,&V,&Mod);
if(V>=n) {
printf("0");
return 0;
}
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%Mod;
inv[n]=qpow(fac[n],Mod-2,Mod);
for(int i=n-1;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%Mod;
int now=0;
f[0][1][1]=n;
for(int i=1;i<=V;i++) {
for(int j=1;j<=n;j++) for(int k=1;k<=j;k++) f[now^1][j][k]=0;
for(int j=1;j<=n;j++) {
for(int k=1;k<=j;k++) {
if(!f[now][j][k]) continue;
for(int p=k+1;p<=j;p++) {
f[now^1][j][p]=(f[now^1][j][p]+1ll*f[now][j][k]*C(j-k,j-p)%Mod)%Mod;
}
for(int p=j+1;p<=n;p++) {
f[now^1][p][k+1]=(f[now^1][p][k+1]+1ll*f[now][j][k]*C(n-j,n-p)%Mod*fac[p-j]%Mod*j%Mod)%Mod;
}
}
}
now^=1;
}
printf("%d",f[now][n][n]);
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 0ms
memory: 3888kb
input:
1 1 624295285
output:
0
result:
ok single line: '0'
Test #2:
score: 5
Accepted
time: 0ms
memory: 3832kb
input:
4 684813415 564954712
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 3824kb
input:
4 2 844826878
output:
410169168
result:
wrong answer 1st lines differ - expected: '24', found: '410169168'
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 0ms
memory: 3960kb
input:
6 4 956647977
output:
618062190
result:
wrong answer 1st lines differ - expected: '238320', found: '618062190'
Subtask #3:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 3ms
memory: 3908kb
input:
48 26 424594716
output:
421956444
result:
wrong answer 1st lines differ - expected: '362283012', found: '421956444'
Subtask #4:
score: 0
Wrong Answer
Test #16:
score: 50
Accepted
time: 0ms
memory: 3840kb
input:
150 526250070 197316869
output:
0
result:
ok single line: '0'
Test #17:
score: 0
Wrong Answer
time: 566ms
memory: 4104kb
input:
149 116 671784452
output:
595286328
result:
wrong answer 1st lines differ - expected: '18945228', found: '595286328'