Description
Solution
假如将图中所有红边一条拆为x条，蓝边一条拆为y条，可得：
$A_{x,y}=\sum_{r=0}^{n-1}\sum_{b=0}^{n-1-r}*T_{r,b}*x^{r}*y^{b} $
其中$A_{x,y}$是拆完边后，用矩阵树定理求出的生成树个数，$T_{r,b}$是用r条红边，b条蓝边的生成树个数。
然后就是拉格朗日插值了，已知点值$A_{x,y}$，求$T_{r,b}$。
Code
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; typedef long long ll; const int mod=1e9+7; int n,m; int x[10010],y[10010],col[10010]; ll c[60][60]; ll ksm(ll x,int k) {ll re=1;while(k){if (k&1) re=re*x%mod;k>>=1;x=x*x%mod;}return re;} ll gauss() { int op=1,i,j,now;ll js,t,ans=1; for (i=1;i<n;i++) { for (j=i;j<n&&!c[j][i];j++); if (j==n) return 0; now=j; if (now!=i) for (op=-op,j=i;j<n;j++) swap(c[i][j],c[now][j]); js=ksm(c[i][i],mod-2); for (int j=i+1;j<n;j++) { t=js*c[j][i]%mod; for (int k=i;k<n;k++) { c[j][k]-=t*c[i][k]%mod; if (c[j][k]>mod) c[j][k]-=mod;if (c[j][k]<0) c[j][k]+=mod; } } ans=ans*c[i][i]%mod; } return op==1?ans:mod-ans; } ll t; ll f[60][60],fx[60],fy[60],ans[60][60]; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) scanf("%d%d%d",&x[i],&y[i],&col[i]); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { memset(c,0,sizeof(c)); for (int k=1;k<=m;k++) { if (col[k]==1) t=i;else if (col[k]==2) t=j;else t=1; c[x[k]][x[k]]+=t;c[y[k]][y[k]]+=t; c[x[k]][y[k]]-=t;c[y[k]][x[k]]-=t; } f[i][j]=gauss(); } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { t=f[i][j]; memset(fx,0,sizeof(fx));memset(fy,0,sizeof(fy)); fx[0]=fy[0]=1; for (int k=1;k<=n;k++) if (k!=i) { for (int x=n;x;x--) fx[x]=(fx[x-1]-fx[x]*k)%mod; (fx[0]*=-k)%=mod; (t*=ksm(i-k,mod-2))%=mod; } for (int k=1;k<=n;k++) if (k!=j) { for (int x=n;x;x--) fy[x]=(fy[x-1]-fy[x]*k)%mod; (fy[0]*=-k)%=mod; (t*=ksm(j-k,mod-2))%=mod; } for (int x=0;x<=n;x++) for (int y=0;y<=n-x;y++) (ans[x][y]+=t*fx[x]%mod*fy[y])%=mod; } for (int x=0;x<n;x++) for (int y=0;y<n-x;y++) printf("%lld\n",(ans[x][y]+mod)%mod); }