正题

题目链接:https://www.luogu.com.cn/problem/CF917D

题目大意

给出\(n\)个点的一棵树，对于每个\(k\)求有多少个\(n\)个点的树满足与给出的树恰好有\(k\)条边重合。

解题思路

矩阵树有一个统计所有树边权和的和用法，就是把变量变成一个形如\(wx+1\)的多项式，这样一次项系数的值就表示了固定选择一条边的\(w\)时其他边的方案数之和。

这题我们可以同理，对于在给出数上的边是\(x\)，而其他就是\(1\)。那么最后询问\(x^k\)的系数就是答案了。

如果暴力套\(\text{NTT}\)不仅麻烦，而且跑的很慢过不了本题，考虑另一种求系数的方法。

我们假设答案是一个形如\(F(x)=\sum_{i=0}^{n-1}a_ix^i\)的\(n\)次项式，那么我们如果把\(n\)个\(x\)的值直接带入求出\(F\)，然后用待定系数法的话我们就可以列出\(n\)个方程从而解出这个\(n\)项式的每一个系数。

时间复杂度\(O(n^4)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const ll N=110,P=1e9+7;

ll n,x[N],y[N];

ll power(ll x,ll b){

    ll ans=1;

    while(b){

        if(b&1)ans=ans*x%P;

        x=x*x%P;b>>=1;

    }

    return ans;

}

namespace Guass{

    ll a[N][N],b[N];

    void solve(){

        for(ll i=1;i<=n;i++){

            ll z=i;

            for(ll j=i;j<=n;j++)

                if(a[j][i]){z=j;break;}

            swap(a[i],a[z]);swap(b[i],b[z]);

            ll inv=power(a[i][i],P-2);

            for(ll j=i;j<=n;j++)

                a[i][j]=a[i][j]*inv%P;

            b[i]=b[i]*inv%P;

            for(ll j=i+1;j<=n;j++){

                ll rate=P-a[j][i];

                for(ll k=i;k<=n;k++)

                    (a[j][k]+=rate*a[i][k]%P)%=P;

                (b[j]+=rate*b[i]%P)%=P;

            }

        }

        for(ll i=n;i>=1;i--){

            for(ll j=i+1;j<=n;j++)

                (b[i]+=P-b[j]*a[i][j]%P)%=P;

        }

        return;

    }

}

namespace Matrix{

    ll a[N][N];

    ll det(){

        ll f=1,ans=1;

        for(ll i=1;i<n;i++){

            ll z=i;

            for(ll j=i;j<n;j++)

                if(a[j][i]){

                    if(j!=i)f=-f;

                    z=j; break;

                }

            swap(a[i],a[z]);

            ll inv=power(a[i][i],P-2);

            ans=ans*a[i][i]%P;

            for(ll j=i;j<n;j++)

                a[i][j]=a[i][j]*inv%P;

            for(ll j=i+1;j<n;j++){

                ll rate=P-a[j][i];

                for(ll k=i;k<n;k++)

                    (a[j][k]+=rate*a[i][k]%P)%=P;

            }

        }

        return ans*f;

    }

    void solve(ll w){

        for(ll i=1;i<=n;i++)

            for(ll j=1;j<=n;j++)

                a[i][j]=P-1;

        for(ll i=1;i<=n;i++)a[i][i]=n-1;

        for(ll i=1;i<n;i++){

            a[x[i]][x[i]]+=w-1;

            a[y[i]][y[i]]+=w-1;

            a[x[i]][y[i]]=P-w;

            a[y[i]][x[i]]=P-w;

        }

        Guass::b[w]=det();

        for(ll i=1,p=1;i<=n;i++,p=p*w%P)

            Guass::a[w][i]=p;

        return;

    }

}

signed main(){

    scanf("%lld",&n);

    for(ll i=1;i<n;i++)

        scanf("%lld%lld",&x[i],&y[i]);

    for(ll i=1;i<=n;i++)Matrix::solve(i);

    Guass::solve();

    for(ll i=1;i<=n;i++)

        printf("%lld ",Guass::b[i]);

    return 0;

}

巴特西

CF917D-Stranger Trees【矩阵树定理,高斯消元】

正题

题目大意

解题思路

code

最新文章

热门文章