QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#578088#5367. 递增树列Rikku_eq0 1ms4012kbC++143.2kb2024-09-20 16:32:122024-09-20 16:32:12

Judging History

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

  • [2024-09-20 16:32:12]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:4012kb
  • [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;
}

Details

Tip: Click on the bar to expand more detailed information

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%