题解-Codeforces917D Stranger Trees

Problem

\(\mathrm{Codeforces~917D}\)

题意概要：一棵 \(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 <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;
}

题解-Codeforces917D Stranger Trees

原文：https://www.cnblogs.com/penth/p/10473891.html