QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#578150 | #5367. 递增树列 | Rikku_eq | 20 | 1ms | 4148kb | C++14 | 2.7kb | 2024-09-20 17:00:15 | 2024-09-20 17:00:15 |
Judging History
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 ? mod-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 ? mod-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--) {
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;
}
}
}
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;
}
}
}
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-1][j-1])%mod;
}
pre[i]=pre[i-1]*(ll)i%mod;
}
dfs(1, 0);
printf("%lld\n", f[1][n]);
return 0;
}
详细
Subtask #1:
score: 9
Accepted
Test #1:
score: 9
Accepted
time: 0ms
memory: 4004kb
input:
7 1 2 2 3 2 4 1 5 5 6 3 7
output:
712
result:
ok single line: '712'
Test #2:
score: 9
Accepted
time: 0ms
memory: 4004kb
input:
5 1 2 1 3 3 4 4 5
output:
44
result:
ok single line: '44'
Test #3:
score: 9
Accepted
time: 0ms
memory: 4036kb
input:
7 1 2 2 3 1 4 3 5 3 6 2 7
output:
576
result:
ok single line: '576'
Test #4:
score: 9
Accepted
time: 0ms
memory: 3968kb
input:
8 1 2 1 3 3 4 2 5 2 6 1 7 2 8
output:
6912
result:
ok single line: '6912'
Test #5:
score: 9
Accepted
time: 0ms
memory: 3932kb
input:
8 1 2 2 3 2 4 1 5 2 6 3 7 5 8
output:
3360
result:
ok single line: '3360'
Subtask #2:
score: 11
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 11
Accepted
time: 0ms
memory: 3952kb
input:
14 1 2 1 3 1 4 1 5 1 6 4 7 2 8 1 9 4 10 7 11 9 12 2 13 11 14
output:
389151297
result:
ok single line: '389151297'
Test #7:
score: 11
Accepted
time: 0ms
memory: 3968kb
input:
13 1 2 2 3 2 4 2 5 4 6 4 7 3 8 4 9 6 10 4 11 11 12 6 13
output:
17381952
result:
ok single line: '17381952'
Test #8:
score: 11
Accepted
time: 0ms
memory: 3916kb
input:
12 1 2 2 3 2 4 1 5 5 6 4 7 7 8 5 9 4 10 1 11 7 12
output:
4993920
result:
ok single line: '4993920'
Test #9:
score: 11
Accepted
time: 0ms
memory: 4052kb
input:
15 1 2 1 3 2 4 4 5 2 6 6 7 2 8 8 9 2 10 4 11 8 12 4 13 5 14 9 15
output:
818474475
result:
ok single line: '818474475'
Test #10:
score: 11
Accepted
time: 0ms
memory: 4128kb
input:
15 1 2 1 3 2 4 3 5 2 6 5 7 4 8 4 9 1 10 10 11 8 12 10 13 13 14 7 15
output:
16041048
result:
ok single line: '16041048'
Subtask #3:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #11:
score: 15
Accepted
time: 1ms
memory: 4064kb
input:
25 1 2 1 3 3 4 4 5 2 6 2 7 5 8 5 9 1 10 10 11 9 12 5 13 4 14 12 15 1 16 14 17 2 18 2 19 16 20 18 21 18 22 20 23 17 24 19 25
output:
179142361
result:
ok single line: '179142361'
Test #12:
score: 15
Accepted
time: 1ms
memory: 4148kb
input:
24 1 2 1 3 2 4 1 5 2 6 2 7 6 8 1 9 1 10 1 11 8 12 6 13 13 14 12 15 2 16 5 17 12 18 8 19 11 20 17 21 21 22 19 23 18 24
output:
680835791
result:
ok single line: '680835791'
Test #13:
score: 15
Accepted
time: 1ms
memory: 4084kb
input:
23 1 2 1 3 3 4 2 5 2 6 5 7 4 8 7 9 4 10 8 11 2 12 8 13 1 14 14 15 9 16 7 17 9 18 5 19 16 20 15 21 10 22 17 23
output:
613299173
result:
ok single line: '613299173'
Test #14:
score: 15
Accepted
time: 1ms
memory: 4140kb
input:
24 1 2 1 3 1 4 1 5 2 6 3 7 1 8 6 9 6 10 10 11 6 12 10 13 6 14 4 15 5 16 1 17 8 18 1 19 17 20 2 21 19 22 20 23 15 24
output:
990332459
result:
ok single line: '990332459'
Test #15:
score: 15
Accepted
time: 0ms
memory: 3956kb
input:
27 1 2 1 3 2 4 1 5 3 6 1 7 4 8 5 9 5 10 9 11 10 12 11 13 6 14 3 15 6 16 5 17 4 18 14 19 3 20 13 21 1 22 8 23 6 24 4 25 12 26 25 27
output:
254905851
result:
ok single line: '254905851'
Test #16:
score: 0
Wrong Answer
time: 1ms
memory: 4096kb
input:
28 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28
output:
910162860
result:
wrong answer 1st lines differ - expected: '245512165', found: '910162860'
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%