P5296 [北京省选集训2019]生成树计数

题意

求一个带权无向图所有生成树边权和的 \(k\) 次方的和。

思路

首先有一个结论：\(a^i\) 的 EGF 卷 \(b^i\) 的 EGF 等于 \((a+b)^i\) 的 EGF。即：

\[F(a)=\sum_{i=0}\frac{a^ix^i}{i!}\\
F(a+b)=F(a)*F(b)
\]

证明如下：

\[(a+b)^k=\sum_{i=0}^k{k\choose i}a^ib^{k-i}=\sum_{i=0}^k\frac{k!}{i!(k-i)!} a^ib^{k-i}\\
\Rightarrow \sum_{i=0}^k\frac{a^i}{i!}\frac{b^{k-i}}{(k-i)!}k!=(a+b)^k \\
\Rightarrow \sum_{i=0}^k\frac{a^i}{i!}\frac{b^{k-i}}{(k-i)!}=\frac{(a+b)^k}{k!}\\
\]

然后又有一个结论：度数矩阵减去邻接矩阵的余子式的行列式的值是图所有生成树边权积的和。其中，度数矩阵表示与其相连的边权的和，邻接矩阵为边权。这是矩阵树定理。

于是，我们将边权化为生成函数，然后利用矩阵树定理算出来答案的生成函数即可。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cctype>

#include<cstring>

#include<cmath>

using namespace std;

inline int read(){

	int w=0,x=0;char c=getchar();

	while(!isdigit(c))w|=c=='-',c=getchar();

	while(isdigit(c))x=x*10+(c^48),c=getchar();

	return w?-x:x;

}

namespace star

{

	const int maxn=35,mod=998244353;

	int n,k,mul[maxn],inv[maxn];

	inline int fpow(int a,int b){int ans=1;for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ans=1ll*ans*a%mod;return ans;}

	struct poly{

		int a[maxn];

		poly():a(){}

		poly(int x):a(){for(int i=0,d=1;i<=k;i++,d=1ll*d*x%mod) a[i]=1ll*star::inv[i]*d%mod;}

		int& operator [](const int &x){return a[x];}

		const int &operator [](const int &x) const {return a[x];}

		friend poly operator + (const poly& a,const poly& b) {

			poly ans;

			for(int i=0;i<=k;i++) ans[i]=(a[i]+b[i])%mod;

			return ans;

		}

		friend poly operator - (const poly& a,const poly& b) {

			poly ans;

			for(int i=0;i<=k;i++) ans[i]=(a[i]-b[i]+mod)%mod;

			return ans;

		}

		friend poly operator * (const poly& a,const poly& b) {

			poly ans;

			for(int i=0;i<=k;i++) for(int j=0;j<=i;j++) ans[i]=(ans[i]+1ll*a[j]*b[i-j])%mod;

			return ans;

		}

		inline poly operator - () const {

			poly ans;

			for(int i=0;i<=k;i++) ans[i]=(mod-a[i])%mod;

			return ans;

		}

		inline poly inv() const {

			poly ans,res;

			ans[0]=fpow(a[0],mod-2);

			for(int i=1;i<=k;i++) res[i]=1ll*a[i]*ans[0]%mod;

			for(int i=1;i<=k;i++) for(int j=1;j<=i;j++) ans[i]=(ans[i]+1ll*(mod-res[j])*ans[i-j])%mod;

			return ans;

		}

	}a[maxn][maxn],ans;

	inline void work(){

		n=read()-1,k=read();

		mul[0]=inv[0]=1;

		for(int i=1;i<=k;i++) mul[i]=1ll*mul[i-1]*i%mod;

		inv[k]=fpow(mul[k],mod-2);for(int i=k-1;i>0;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;

		for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) if(i!=j) a[i][j]=-poly(read()),a[i][i]=a[i][i]-a[i][j];else read();

		ans[0]=1;

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

			poly x=a[i][i].inv();

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

			for(int j=i;j<=n;j++) a[i][j]=a[i][j]*x;

			for(int j=1;j<=n;j++) if(j!=i){

				poly res=a[j][i];

				for(int k=i;k<=n;k++) a[j][k]=a[j][k]-a[i][k]*res;

			}

		}

		printf("%lld\n",1ll*ans[k]*mul[k]%mod);

	}

}

signed main(){

	star::work();

	return 0;

}

巴特西

P5296 [北京省选集训2019]生成树计数

P5296 [北京省选集训2019]生成树计数

题意

思路

最新文章

热门文章