Codeforces

Luogu

算法一

分析

设树边的权值为 $x$，非树边的权值为 $1$，然后矩阵树定理。设得到的多项式为 $F(x)$，那么显然 $k=i$ 时的答案即为 $[x^i]F(x)$。

然而直接 MTT + 高斯消元显然是过不去的。但是 $F(x)$ 是一个 $n-1$ 次多项式，所以我们可以把 $x=[1,n]$ 代进去求出 $F(1..n)$，然后解方程组解出系数即可。

时间复杂度 $\mathcal{O}(n^4)$，被下面那个做法吊打。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10;
const int mod=1e9+7;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,G[N][N],c[N][N],a[N][N];

int det(int n) {
    int ans=1;
    for (int i=1;i<=n;++i) {
        if (!c[i][i]) {
            for (int j=i+1;j<=n;++j)
                if (c[j][i]) { swap(c[i],c[j]),ans=mod-ans; break; }
        }
        ans=1ll*ans*c[i][i]%mod;
        int inv=qpow(c[i][i],mod-2);
        for (int j=i+1;j<=n;++j) {
            int t=1ll*c[j][i]*inv%mod;
            for (int k=i;k<=n;++k)
                c[j][k]=(c[j][k]-1ll*c[i][k]*t%mod+mod)%mod;
        }
    }
    return ans;
}
void Gauss(int n) {
    for (int i=1;i<=n;++i) {
        if (!a[i][i]) {
            for (int j=i+1;j<=n;++j)
                if (a[j][i]) { swap(a[i],a[j]); break; }
        }
        int inv=qpow(a[i][i],mod-2);
        for (int j=1;j<=n;++j) {
            if (i==j) continue;
            int t=1ll*a[j][i]*inv%mod;
            for (int k=1;k<=n+1;++k)
                a[j][k]=(a[j][k]-1ll*a[i][k]*t%mod+mod)%mod;
        }
    }
    for (int i=1;i<=n;++i)
        a[i][n+1]=1ll*a[i][n+1]*qpow(a[i][i],mod-2)%mod;
}

int main() {
    n=read();
    for (int i=1,u,v;i<n;++i) u=read(),v=read(),G[u][v]=G[v][u]=1;
    for (int x=1;x<=n;++x) {
        memset(c,0,sizeof(c));
        for (int i=1;i<=n;++i)
            for (int j=i+1;j<=n;++j) {
                if (G[i][j]) {
                    c[i][j]=mod-x,c[i][i]=(c[i][i]+x)%mod;
                    c[j][i]=mod-x,c[j][j]=(c[j][j]+x)%mod;
                } else {
                    c[i][j]=mod-1,++c[i][i];
                    c[j][i]=mod-1,++c[j][j];
                }
            }
        a[x][n+1]=det(n-1);
    }
    for (int x=1;x<=n;++x) {
        a[x][1]=1;
        for (int i=2;i<=n;++i) a[x][i]=1ll*a[x][i-1]*x%mod;
    }
    Gauss(n);
    for (int i=1;i<=n;++i) printf("%d ",a[i][n+1]); puts("");
    return 0;
}

算法二

分析

考虑容斥，算至少 $k$ 条边重合的方案数。我们可以先选 $k$ 条边出来形成 $n-k$ 个连通块，然后连通块间任意连边，方案数即为 $n^{n-k-2}\prod s_i$。这个可以用 Prufer 序列证，证明可以看这里。

考虑把 $\prod s_i$ 转化为每个连通块内选一个点放上一个东西的方案数，于是可以考虑 DP：设 $dp_{i,j,0/1}$ 表示以 $i$ 为根的子树，选了 $j$ 个连通块，$i$ 所在的连通块没放 / 放了东西的方案数，转移讨论儿子是否和父亲连起来即可，和树形背包类似。

那么至少 $k$ 条边重合的方案数即为 $dp_{1,n-k,1}$，再二项式反演一下就可以得到恰好 $k$ 条边重合的方案数了。

时间复杂度 $\mathcal{O}(n^2)$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10;
const int mod=1e9+7;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n; vector<int> E[N];
int f[N],g[N],C[N][N];
int dp[N][N][2],t[N][2],sz[N];

void dfs(int u,int fa) {
    dp[u][1][0]=dp[u][1][1]=1,sz[u]=1;
    for (int v:E[u]) {
        if (v==fa) continue;
        dfs(v,u);
        for (int i=0;i<=sz[u]+sz[v];++i) t[i][0]=t[i][1]=0;
        for (int i=0;i<=sz[u];++i)
            for (int j=0;j<=sz[v];++j) {
                t[i+j][0]=(t[i+j][0]+1ll*dp[u][i][0]*dp[v][j][1])%mod;
                t[i+j][1]=(t[i+j][1]+1ll*dp[u][i][1]*dp[v][j][1])%mod;
                if (i+j) {
                    t[i+j-1][0]=(t[i+j-1][0]+1ll*dp[u][i][0]*dp[v][j][0])%mod;
                    t[i+j-1][1]=(t[i+j-1][1]+1ll*dp[u][i][1]*dp[v][j][0])%mod;
                    t[i+j-1][1]=(t[i+j-1][1]+1ll*dp[u][i][0]*dp[v][j][1])%mod;
                }
            }
        for (int i=0;i<=sz[u]+sz[v];++i)
            dp[u][i][0]=t[i][0],dp[u][i][1]=t[i][1];
        sz[u]+=sz[v];
    }
}

int main() {
    n=read();
    for (int i=1;i<n;++i) {
        int u=read(),v=read();
        E[u].emplace_back(v),E[v].emplace_back(u);
    }
    dfs(1,0);
    for (int i=0;i<n-1;++i) g[i]=1ll*dp[1][n-i][1]*qpow(n,n-i-2)%mod;
    g[n-1]=1;
    for (int i=C[0][0]=1;i<=n;++i)
        for (int j=C[i][0]=1;j<=n;++j)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    for (int i=0;i<n;++i)
        for (int j=i;j<n;++j) {
            if ((j-i)&1) f[i]=(f[i]-1ll*g[j]*C[j][i]%mod+mod)%mod;
            else f[i]=(f[i]+1ll*g[j]*C[j][i])%mod;
        }
    for (int i=0;i<n;++i) printf("%d ",f[i]); puts("");
    return 0;
}