[SHOI2016]黑暗前的幻想乡
description
有\(n\)个点，\(m\)条边，\(n-1\)种颜色，每种颜色都有一个能涂的边集。问构成的满足每个边颜色不同的生成树有多少种。
solution
计数题，有两个限制:
1.生成树方案
2.恰好每种颜色都算入（所有边颜色不同）
1显然能用矩阵树定理。2有待商榷
把所有边算入，求矩阵树行列式得到的是至多\(n-1\)种颜色的边。
看到这里就会想到容斥，得到恰好\(n-1\)种颜色的边。
code
点击查看代码
#include
using namespace std;
typedef long long ll;
const int N=18;
const int M=N*N;
const int mod=1e9+7;
struct edge{int x,y;};
vector V[N];
int n;
ll G[N][N];
ll ksm(ll a,ll b) {ll mul=1;for(;b;b>>=1,a=a*a%mod)if(b&1)mul=mul*a%mod;return mul;}
ll _det() {
// printf("!");
ll mul=1;
for(int i=1;i<=n;i++) {
int r=i;
while(r<=n&&!G[r][i]) r++;
if(r==n+1)continue;
if(r!=i) {mul*=-1;for(int j=1;j<=n;j++) swap(G[r][j],G[i][j]);}
for(int j=i+1;j<=n;j++) {
ll tmp=G[j][i]*ksm(G[i][i],mod-2)%mod;
for(int k=1;k<=n;k++) G[j][k]=(G[j][k]-G[i][k]*tmp)%mod;
}
}
for(int i=1;i<=n;i++)mul=mul*G[i][i]%mod;
// printf("%lld\n",(mul+mod)%mod);
return mul;
}
void init() {
scanf("%d",&n);n--;
for(int i=0;i