QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#578150#5367. 递增树列Rikku_eq20 1ms4148kbC++142.7kb2024-09-20 17:00:152024-09-20 17:00:15

Judging History

你现在查看的是最新测评结果

  • [2024-09-20 17:00:15]
  • 评测
  • 测评结果:20
  • 用时:1ms
  • 内存:4148kb
  • [2024-09-20 17:00:15]
  • 提交

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%