算法一
分析
设树边的权值为 $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;
}