幻想乡三连A：五颜六色的幻想乡

 

非常直接地构造

由于答案与生成树计数有关，所以一定要使用矩阵树定理，但这样就不能限制每种颜色的便使用的数量

我们构造$N^2$个关于$Ans_{x,y}$的方程，枚举将红色的边拆成$x$条，将蓝色的边拆成$y$条，跑一遍矩阵树定理，就得到$$G_{x,y}=sumlimits_{i=0}^{n-1} sumlimits_{j=0}^{n-i-1} Ans_{i,j}cdot x^icdot y^j$$然后会发现$Ans_{i,j}$可以看做这个二维多项式的系数，直接用拉格朗日插值构造得解。

 

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define mod 1000000007
#define M 60
using namespace std;
int read(){
	int nm=0,fh=1; char cw=getchar();
	for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;
	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
	return nm*fh;
}
int n,m,u[M*M],v[M*M],kd[M*M],mat[M][M],T[M][M],ans[M][M];
int X[M],Y[M],tmp,V[M][M];
int add(int x,int y){return (x+y)>=mod?x+y-mod:x+y;}
int mus(int x,int y){return (x-y)<0?x-y+mod:x-y;}
int mul(int x,int y){return (LL)x*(LL)y%mod;}
void upd(int &x,int y){x=add(x,y);}
int qpow(int x,int sq){
	int res=1;
	while(sq){if(sq&1) res=mul(res,x);x=mul(x,x),sq>>=1;}
	return res;
}
int init(int x,int y){
	const int w[4]={0,x,y,1};
	int dt,inv,now=1,ot;
	memset(mat,0,sizeof(mat));
	for(int i=1;i<=m;i++){
	    upd(mat[u[i]][v[i]],mod-w[kd[i]]),upd(mat[u[i]][u[i]],w[kd[i]]);
		upd(mat[v[i]][u[i]],mod-w[kd[i]]),upd(mat[v[i]][v[i]],w[kd[i]]);
	}
	for(int i=1;i<n;i++){
		for(ot=i;ot<n&&mat[ot][i]==0;ot++);
		if(ot>=n) return 0;
		if(ot!=i){now=mod-now;for(int j=i;j<n;j++) swap(mat[i][j],mat[ot][j]);}
		now=mul(now,mat[i][i]),inv=qpow(mat[i][i],mod-2);
		for(int j=i+1;j<n;j++){
			if(!mat[j][i]) continue; dt=mul(mat[j][i],inv);
			for(int k=i;k<n;k++) mat[j][k]=mus(mat[j][k],mul(dt,mat[i][k]));
		}
	}
	return now;
}
void solve(int x,int y){
	memset(X,0,sizeof(X)),X[0]=1;
	memset(Y,0,sizeof(Y)),Y[0]=1;
	tmp=T[x][y];
	for(int i=1;i<=n;i++){
		if(i!=x){
		    for(int j=i;j;j--) X[j]=mus(X[j-1],mul(X[j],i));
		    X[0]=mul(X[0],mod-i),tmp=mul(tmp,V[x][i]);
		}
		if(i!=y){
		    for(int j=i;j;j--) Y[j]=mus(Y[j-1],mul(Y[j],i));
		    Y[0]=mul(Y[0],mod-i),tmp=mul(tmp,V[y][i]);
		}
	}
	for(int i=0;i<n;i++) for(int j=0;j+i<n;j++) upd(ans[i][j],mul(tmp,mul(X[i],Y[j])));
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++) u[i]=read(),v[i]=read(),kd[i]=read();
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) T[i][j]=init(i,j);
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) V[i][j]=qpow(mus(i,j),mod-2);
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) solve(i,j);
	for(int i=0;i<n;i++) for(int j=0;i+j<n;j++) printf("%d
",ans[i][j]);
	return 0;
}