【2020 Wannafly Camp Day1 D】生成树 题解

题目大意

  给出两幅 $n$ 个点的无向图 $G_1,G_2$，对于 $G_1$ 的每一棵生成树，贡献是有多少条边在 $G_2$ 中出现。求 $G_1$ 的所有生成树的贡献和。

  $n \leq 400$，4s

$$\\$$ $$\\$$ $$\\$$

题解

  您好，请重修线性代数

  题目相当于说 $G_1$ 里的每一条边有一个权值（在 $G_2$ 中出现过则为 $1$，没出现则为 $0$），求所有生成树的权值和。

  这种情况一般用 $1$ 代表 $0$ 权的边，$x$ 代表 $1$ 权的边，那么基尔霍夫矩阵的 $n-1$ 阶主子式是个多项式，$x^k$ 的系数代表权值为 $k$ 的生成树的方案数。
  一些比较传统的方法是，直接用多项式类算行列式，或者 $n$ 次点值再插值。这样都是 $O(n^4)$ 的，就不行。

  因此这里要用到题目的性质，记 $a_i$ 表示 $x^i$ 的系数，$f(x)=\det=\sum_{i=0}^{n-1} a_ix^i$，则所求为

$$ans=\sum_{i=0}^{n-1} i\cdot a_i=f'(1)$$

  这相当于要给 $\det$ 求导。设基尔霍夫矩阵前 $n-1$ 阶主子式为 $J(x)$，每个元素的余子式为 $A_{i,j}(x)$，则

$$ans=f'(1)=\sum_{i=1}^{n-1}\sum_{j=1}^{n-1} J'_{i,j}(1)\cdot A_{i,j}(1)$$

  余子式由 $J^{-1}\cdot \det J$ 算出。

考场上 fail 的想法

  另一种想法是枚举强制选一条边，快速计算修改基尔霍夫矩阵后的行列式。想到这个是因为以前做过这个题。
  但发现这个方法不大行。之前用这个方法的时候题目是求树形图，每次只用修改一行，而到这里无向图则需要修改两行，以前的方法都 fail 了。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const int maxn=405;
const LL mo=998244353;

int n,m,g1[maxn][maxn],w[maxn][maxn],x[maxn];
char s[maxn];

LL Pow(LL x,LL y)
{
    LL re=1;
    for(; y; y>>=1, x=x*x%mo) if (y&1) re=re*x%mo;
    return re;
}

LL D,J[maxn][maxn];
void Det(int n)
{
    D=1;
    fo(i,1,n)
    {
        fo(j,i,n) if (J[j][i]!=0)
        {
            swap(J[i],J[j]);
            if (i!=j) D*=-1;
            break;
        }
        fo(j,i+1,n)
        {
            LL c=J[j][i]*Pow(J[i][i],mo-2)%mo;
            fo(k,i,n) (J[j][k]-=c*J[i][k])%=mo;
        }
    }
    fo(i,1,n) (D*=J[i][i])%=mo;
    D=(D+mo)%mo;
}

LL G[maxn][maxn],inv[maxn][maxn],c[maxn];
void Gauss(int n)
{
    fo(i,1,n)
    {
        fo(j,i,n) if (G[j][i]!=0)
        {
            swap(G[i],G[j]), swap(inv[i],inv[j]);
            break;
        }
        LL c=Pow(G[i][i],mo-2);
        fo(j,1,n) (G[i][j]*=c)%=mo, (inv[i][j]*=c)%=mo;
        fo(j,1,n) if (j!=i)
        {
            LL c=G[j][i];
            fo(k,1,n) (G[j][k]-=c*G[i][k])%=mo, (inv[j][k]-=c*inv[i][k])%=mo;
        }
    }
}
void Inv(int n)
{
    fo(i,1,n)
    {
        inv[i][i]=1;
        fo(j,1,n) G[i][j]=J[j][i];
    }
    Gauss(n);
}

int main()
{
    scanf("%d",&n);
	fo(i,1,n)
	{
		scanf("%s",s+1);
		fo(j,1,n)
		{
			g1[i][j]=s[j]-'0';
			if (i<j && g1[i][j])
			{
				J[i][i]++; J[j][j]++;
				J[i][j]--; J[j][i]--;
			}
		}
	}
	fo(i,1,n)
	{
		scanf("%s",s+1);
		fo(j,1,n)
		{
			w[i][j]=g1[i][j]&(s[j]-'0');
			x[i]+=w[i][j];
		}
	}

    Inv(n-1);
    Det(n-1);

    LL ans=0;
    fo(i,1,n-1)
		fo(j,1,n-1)
		{
			int d=(i==j) ?x[i] :-w[i][j];
			(ans+=inv[j][i]*D%mo*d)%=mo;
		}

    printf("%lld\n",(ans+mo)%mo);
}