QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#578088 | #5367. 递增树列 | Rikku_eq | 0 | 1ms | 4012kb | C++14 | 3.2kb | 2024-09-20 16:32:12 | 2024-09-20 16:32:12 |
answer
#include <bits/stdc++.h>
#define mod 1000000007
#define N 83
using namespace std;
typedef long long ll;
int n, sz[N];
ll C[N][N], F[2][N][N], G[N][N], g[N][N], gp[N][N], f[N][N], pre[N];
vector <int> to[N];
void dfs (int u, int fa)
{
for (int ii=0; ii<(int)to[u].size(); ii++) {
int v=to[u][ii];
if (v==fa) { continue; }
dfs(v, u);
}
memset(F, 0, sizeof(F));
F[0][0][0]=1;
for (int ii=0; ii<(int)to[u].size(); ii++) {
int v=to[u][ii];
if (v==fa) { continue; }
G[0][0]=1;
for (int i=1; i<=sz[v]; i++) {
for (int j=1; j<=i; j++) {
G[i][j]=0;
for (int x=1; x<=i; x++) {
G[i][j]+=f[v][x]*C[sz[v]-x][i-x] %mod *gp[i-x+1][j] %mod *((i-x+1-j)&1 ? -1 : 1);
G[i][j]%=mod;
}
}
}
sz[u]+=sz[v];
for (int tg=1; tg>=0; tg--) {
for (int iu=sz[u]; iu>=1; iu--) {
for (int ju=iu; ju>=1; ju--) {
for (int i=min(iu, sz[v]); i>=max(1, iu-sz[u]+sz[v]); i--) {
for (int j=min(ju, i); j>=1; j--) {
F[tg][iu][ju]+=F[tg][iu-i][ju-j]*g[i][j] %mod *((i-j)&1 ? -1 : 1) * C[sz[v]][i] %mod;
if (tg) F[tg][iu][ju]+=F[tg^1][iu-i][ju-j]*G[i][j] %mod;
F[tg][iu][ju]%=mod;
}
}
}
}
}
}
sz[u]++;
// for (int tg=1; tg>=0; tg--) {
// for (int iu=sz[u]; iu>=1; iu--) {
// for (int ju=iu; ju>=1; ju--) {
// cout<<tg<<" "<<iu<<" "<<ju<<" "<<F[tg][iu][ju]<<endl;
// }
// }
// }
for (int tg=1; tg>=0; tg--) {
for (int iu=sz[u]; iu>=1; iu--) {
for (int ju=iu; ju>=1; ju--) {
F[tg][iu][ju]+=F[tg][iu-1][ju-1];
if (tg) F[tg][iu][ju]+=F[tg^1][iu-1][ju-1];
F[tg][iu][ju]%=mod;
// cout<<tg<<" "<<iu<<" "<<ju<<" "<<F[tg][iu][ju]<<endl;
}
}
}
f[u][0]=1;
for (int i=1; i<=sz[u]; i++) {
for (int j=1; j<=i; j++) {
f[u][i]+=F[1][i][j]*pre[j-1] %mod;
f[u][i]%=mod;
// cout<<F[1][i][j]<<endl;
}
// cout<<u<<" "<<i<<" "<<f[u][i]<<endl;
}
}
int main ()
{
// freopen("0test.in", "r", stdin);
// freopen("0test.out", "w", stdout);
scanf("%d", &n);
for (int i=1; i<n; i++) {
int u, v; scanf("%d %d", &u, &v);
to[u].push_back(v);
to[v].push_back(u);
}
g[0][0]=1; gp[0][0]=1; C[0][0]=1; pre[0]=1;
for (int i=1; i<=n; i++) {
C[i][0]=1;
for (int j=1; j<=i; j++) {
g[i][j]=g[i-1][j-1] + g[i-1][j]*(i-1+j) %mod;
g[i][j]%=mod;
gp[i][j]=gp[i-1][j-1] + gp[i-1][j]*(i-2+j) %mod;
gp[i][j]%=mod;
C[i][j]=(C[i-1][j]+C[i][j-1])%mod;
}
pre[i]=pre[i-1]*(ll)i%mod;
}
dfs(1, 0);
ll ans=(f[1][n]+mod)%mod;
printf("%lld\n", ans);
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4012kb
input:
7 1 2 2 3 2 4 1 5 5 6 3 7
output:
3264
result:
wrong answer 1st lines differ - expected: '712', found: '3264'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%