Problem
题意概要：一棵 (n) 个节点的无向树。问在 (n) 个点的完全图中，有多少生成树与原树恰有 (k) 条边相同，对于任意 (kin[0,n)) 输出答案，答案取模。
(2leq nleq 100)
Solution
这题思路新奇啊，智商又能上线了
由于暴力为枚举所有生成树，发现枚举所有生成树的高效算法为矩阵树定理，而且数据范围恰好在矩阵树复杂度接受范围内
由于矩阵树计算的是所有 生成树边权积 之和，考虑给完全图中每一条边边权设为 (1)，若是树边则设为 (x)，最后矩阵树消出来的行列式为一个多项式，这个多项式中 (k) 次项的系数即 与原树重合恰好 (k) 条边的生成树个数
考虑将多项式代入行列式去消不方便，可以采用代入几个数字去算，最后用拉格朗日插值去算系数，由于最后的多项式为 (n) 项系数，所以需要用 (n+1) 个值去代，不妨设为 (1...n+1)
总体时间复杂度 (O(n^4))，比容斥Dp慢多了……
拉格朗日差值
刚好正在复习拉格朗日差值，附上大致流程：
求 (F(x)=sum a_ix^i)，使得 (forall iin[1,n],F(x_i)=y_i)
令 (F(x)=sum_if_i(x))，其中(f_i(x_j)=egin{cases}y_j,& j=i\0,& j ot =iend{cases})
由定义可设 (f_i(x)=c_iprod_{j ot = i}(x-x_j)=y_i)，可以解出 (c_i)，反过来得到 (f_i(x))，最后求和得到 (F(x))
其中求 (prod_{j ot = i}(x-x_j)) 时，可以先预处理出 (prod (x-x_j))，对于每一个 (i) 都将上式除以 ((x-x_i))，这样二项式乘除法都是 (O(n^2)) 的
整个算法复杂度 (O(n^2))
Code
//Codeforces-917D
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline void read(int&x){
char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();
while(isdigit(c11))x=x*10+c11-'0',c11=getchar();
}
const int N = 113, p = 1e9+7;
struct Edge{int l,r;}e[N];
int Y[N],n;
inline int qpow(int A,int B){
int res = 1; while(B){
if(B&1) res = (ll)res * A%p;
A = (ll)A * A%p, B >>= 1;
}return res;
}
namespace Matrix_Tree{
int a[N][N];
int Gauss(){
for(int i=1;i<n;++i){
if(!a[i][i])
for(int j=i+1;j<n;++j)
if(a[j][i]){
for(int k=i;k<n;++k)
swap(a[i][k],a[j][k]);
break;
}
for(int j=i+1;j<n;++j)
if(a[j][i]){
int ki = (ll)a[j][i] * qpow(a[i][i],p-2)%p;
for(int k=i;k<n;++k)
a[j][k] = (a[j][k] - (ll)ki * a[i][k]%p +p)%p;
}
}
int res = 1;
for(int i=1;i<n;++i)
res = (ll)res * a[i][i]%p;
return res;
}
int calc(int x){
for(int i=1;i<n;++i)
for(int j=1;j<n;++j)
a[i][j] = 0;
for(int i=1;i<n;++i)
a[i][i] = n - 1;
for(int i=1,l,r;i<n;++i){
l = e[i].l, r = e[i].r;
a[l][r] = a[r][l] = p - x;
a[l][l] = (a[l][l] + x - 1)%p;
a[r][r] = (a[r][r] + x - 1)%p;
}
for(int i=1;i<n;++i)
for(int j=1;j<n;++j)
if(i!=j and !a[i][j])
a[i][j] = p - 1;
return Gauss();
}
}
namespace Lagrange{
int Ans[N],S[N],a[N],tmp[N];
inline int calc(int n,int x){
int res = 0, pw = 1;
for(int i=0;i<=n;++i){
res = (res + (ll)pw * a[i])%p;
pw = (ll)pw * x %p;
}return res;
}
void work(){
++n, S[0] = 1;
for(int i=1;i<=n;++i){
for(int j=i;j;--j)
S[j] = S[j-1];
S[0] = 0;
for(int j=0;j<i;++j)
S[j] = (S[j] - (ll)S[j+1] * i%p +p)%p;
}
for(int i=1;i<=n;++i){
for(int j=0;j<=n;++j) tmp[j] = S[j];
for(int j=n;j;--j){
a[j-1] = tmp[j];
tmp[j-1] = (tmp[j-1] + (ll)i * tmp[j])%p;
}
int v = calc(n-1,i);
v = (ll)qpow(v,p-2) * Y[i]%p;
for(int j=0;j<n;++j)
Ans[j] = (Ans[j] + (ll)v * a[j])%p;
}
for(int i=0;i<n-1;++i)
printf("%d ",Ans[i]);
putchar(10);
}
}
int main(){
read(n);
for(int i=1,x,y;i<n;++i) read(e[i].l),read(e[i].r);
for(int i=1;i<=n+1;++i) Y[i] = Matrix_Tree::calc(i);
Lagrange::work();
return 0;
}