Problem

题意概要：一棵 \(n\) 个节点的无向树。问在 \(n\) 个点的完全图中，有多少生成树与原树恰有 \(k\) 条边相同，对于任意 \(k\in[0,n)\) 输出答案，答案取模。

\(2\leq n\leq 100\)

Solution

这题思路新奇啊，智商又能上线了

由于暴力为枚举所有生成树，发现枚举所有生成树的高效算法为矩阵树定理，而且数据范围恰好在矩阵树复杂度接受范围内

由于矩阵树计算的是所有 生成树边权积 之和，考虑给完全图中每一条边边权设为 \(1\)，若是树边则设为 \(x\)，最后矩阵树消出来的行列式为一个多项式，这个多项式中 \(k\) 次项的系数即 与原树重合恰好 \(k\) 条边的生成树个数

考虑将多项式代入行列式去消不方便，可以采用代入几个数字去算，最后用拉格朗日插值去算系数，由于最后的多项式为 \(n\) 项系数，所以需要用 \(n+1\) 个值去代，不妨设为 \(1...n+1\)

总体时间复杂度 \(O(n^4)\)，比容斥Dp慢多了……

拉格朗日差值

刚好正在复习拉格朗日差值，附上大致流程：

求 \(F(x)=\sum a_ix^i\)，使得 \(\forall i\in[1,n],F(x_i)=y_i\)

令 \(F(x)=\sum_if_i(x)\)，其中\(f_i(x_j)=\begin{cases}y_j,& j=i\\0,& j\not =i\end{cases}\)

由定义可设 \(f_i(x)=c_i\prod_{j\not = i}(x-x_j)=y_i\)，可以解出 \(c_i\)，反过来得到 \(f_i(x)\)，最后求和得到 \(F(x)\)

其中求 \(\prod_{j\not = i}(x-x_j)\) 时，可以先预处理出 \(\prod (x-x_j)\)，对于每一个 \(i\) 都将上式除以 \((x-x_i)\)，这样二项式乘除法都是 \(O(n^2)\) 的

整个算法复杂度 \(O(n^2)\)

Code

//Codeforces-917D#include 
    
     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