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

题目链接：洛谷

题目大意：给定一个$n$个节点的树$T$，令$ans_k=\sum_{T'}[|T\cap T'|=k]$，即有$k$条边重合。输出$ans_0,ans_1,\ldots,ans_{n-1}$.

数据范围：$1\leq n\leq 100$

这题的思路挺巧妙的，非常不错。

我们将$T$上的边的边权作为$x$，不在$T$上的边的边权设为$1$（一个完全图），然后用矩阵树定理算出所有生成树的边权之积之和，也就是$x^k$的系数就是$ans_k$，现在我们要求这个多项式。

但是运算一个多项式的行列式复杂度会高到爆炸，所以我们考虑插值，只需要$n$个点值就可以，这里我们取$x=1,2,\ldots n$，然后用高斯消元算出这个多项式的系数就可以。（具体实现看代码）

时间复杂度$O(n^4)$。

 #include<bits/stdc++.h>

 #define Rint register int

 using namespace std;

 typedef long long LL;

 const int N = , mod = 1e9 + ;

 int n, a[N][N], b[N][N];

 bool tree[N][N];

 inline int kasumi(int a, int b){

     int res = ;

     while(b){

         if(b & ) res = (LL) res * a % mod;

         a = (LL) a * a % mod;

         b >>= ;

     }

     return res;

 }

 inline int Gauss(){

     int res = ;

     for(Rint i = ;i < n;i ++){

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

             while(a[j][i]){

                 int d = a[i][i] / a[j][i];

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

                     a[i][k] = (a[i][k] - (LL) d * a[j][k] + mod) % mod;

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

                 res = mod - res;

             }

         res = (LL) res * a[i][i] % mod;

         if(!a[i][i]) return ;

     }

     return res;

 }

 int main(){

     scanf("%d", &n);

     for(Rint i = ;i < n;i ++){

         int a, b;

         scanf("%d%d", &a, &b);

         tree[a][b] = tree[b][a] = true;

     }

     for(Rint k = ;k <= n;k ++){

         for(Rint i = ;i <= n;i ++){

             a[i][i] = ;

             for(Rint j = ;j <= n;j ++){

                 if(i != j){

                     if(tree[i][j]){

                         a[i][j] = mod - k;

                         a[i][i] = (a[i][i] + k) % mod;

                     } else {

                         a[i][j] = mod - ;

                         a[i][i] = (a[i][i] + ) % mod;

                     }

                 }

             }

         }

         b[k][] = ;

         for(Rint i = ;i <= n;i ++) b[k][i] = (LL) b[k][i - ] * k % mod;

         b[k][n + ] = Gauss();

     }

     for(Rint i = ;i <= n;i ++){

         int inv = kasumi(b[i][i], mod - );

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

             b[i][j] = (LL) b[i][j] * inv % mod;

         for(Rint j = ;j <= n;j ++)

             if(i != j)

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

                     b[j][k] = (b[j][k] - (LL) b[j][i] * b[i][k] % mod + mod) % mod;

     }

     for(Rint i = ;i <= n;i ++) printf("%d ", b[i][n + ]);

 }

CF917D

巴特西

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

最新文章

热门文章