题解
前置芝士 :矩阵树定理
本题是一道计数题，有两个要求：
-
建造的公路构成一颗生成树
-
每条公路由不同的公司建造，每条公路与一个公司一一映射
那么看到这两个要求后，我们很容易想到第一个条件用矩阵树定理，那么对于第二个条件，我们就很容易想到容斥原理。
先不考虑第二个条件，把所有边都加进去（没有自环），这是我们用矩阵树原理算出来的结果不仅有 (n-1) 个公司建造的方案，也包括了 ((n-2)...1) 个公司建造的方案。
此时，我们需要减去 (n-2) 个公司建造的方案，那么这里我们就把其中一个公司去掉，再进行计算，注意这里去掉一个公司有 (n-1) 种方案。
但是我们会发现 (n-3) 个公司建造的方案被重复减去了，所以我们需要加回来，至此，就是一个纯的容斥了。
对于删去不同的公司，计算不同的方案，我们可以用二进制压一下 (n-1) ，二进制每一位 (1) 代表选取这一位代表的公司。
而在求解行列式的过程中，我们可以直接利用逆元进行求解，也可以辗转相除。
所以最后前一种复杂度为 (mathcal O(2^{n-1}((n-1)^3+(n-1)log(1e9+7)))) 后一种的复杂度为 (mathcal O(2^{n-1}(n-1)^3logn)) 。
Code
逆元 (AC kern 0.4em CODE:)
#include<bits/stdc++.h>
#define ri register signed
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++
inline int read() {
ri x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
return x*f;
}
}
using IO::read;
namespace nanfeng{
#define lm(x) (1<<x)
#define lowbit(x) (x&-(x))
#define cmax(x,y) ((x)>(y)?(x):(y))
#define cmin(x,y) ((x)>(y)?(y):(x))
#define FI FILE *IN
#define FO FILE *OUT
typedef long long ll;
static const int N=20,MOD=1e9+7;
int num[N],u[N][N*N],v[N][N*N],G[N][N],siz[lm(16)+7],lg[lm(16)+7]={-1},n,cnt,st,ans;
inline void add(int u,int v) {p(G[u][v]),p(G[v][u]);}
inline int fpow(int x,int y) {
int res=1;
while(y) {
if (y&1) res=1ll*res*x%MOD;
x=1ll*x*x%MOD;y>>=1;
}
return res;
}
inline int Gauss() {
int res=1,tr=0;
for (ri i(1);i<=cnt;p(i)) {
for (ri j(i+1);j<=cnt;p(j)) if (G[j][i]) {swap(G[i],G[j]);tr^=1;break;}
int inv=fpow(G[i][i],MOD-2);
for (ri j(i+1);j<=cnt;p(j)) {
int tmp=1ll*inv*G[j][i]%MOD;
for (ri k(i+1);k<=cnt;p(k)) G[j][k]=(G[j][k]-1ll*G[i][k]*tmp%MOD+MOD)%MOD;
}
if (!G[i][i]) return 0;
res=1ll*res*G[i][i]%MOD;
}
return tr?-res:res;
}
inline int main() {
// FI=freopen("nanfeng.in","r",stdin);
// FO=freopen("nanfeng.out","w",stdout);
n=read(),cnt=n-1;st=(1<<n-1)-1;
for (ri i(1);i<=st;p(i)) siz[i]=siz[i>>1]+(i&1),lg[i]=lg[i>>1]+1;
for (ri i(1);i<n;p(i)) {
num[i]=read();
for (ri j(1);j<=num[i];p(j)) u[i][j]=read(),v[i][j]=read();
}
for (ri i(1);i<=st;p(i)) {
int low=i;
memset(G,0,sizeof(G));
while(low) {
int id=lg[lowbit(low)]+1;
for (ri j(1);j<=num[id];p(j)) add(u[id][j],v[id][j]);
low-=lowbit(low);
}
for (ri j(1);j<=n;p(j)) {
for (ri k(1);k<=n;p(k)) if (j^k) G[j][j]+=G[j][k],G[j][k]=-G[j][k];
}
// for (ri j(1);j<=n;p(j)) {
// for (ri k(1);k<=n;p(k)) printf("%d ",G[j][k]);
// puts("");
// }
int tmp=(Gauss()+MOD)%MOD;
// printf("state=%d tmp=%d
",i,tmp);
ans=((ll)ans+MOD+((n-siz[i])&1?tmp:-tmp))%MOD;
}
printf("%d
",ans);
return 0;
}
}
int main() {return nanfeng::main();}
Code
辗转相除法 (AC kern 0.4em CODE:)
#include<bits/stdc++.h>
#define ri register signed
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++
inline int read() {
ri x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
return x*f;
}
}
using IO::read;
namespace nanfeng{
#define lm(x) (1<<x)
#define lowbit(x) (x&-(x))
#define cmax(x,y) ((x)>(y)?(x):(y))
#define cmin(x,y) ((x)>(y)?(y):(x))
#define FI FILE *IN
#define FO FILE *OUT
typedef long long ll;
static const int N=20,MOD=1e9+7;
int num[N],u[N][N*N],v[N][N*N],G[N][N],siz[lm(16)+7],lg[lm(16)+7]={-1},n,cnt,st,ans;
inline void add(int u,int v) {p(G[u][v]),p(G[v][u]);}
inline int Gauss() {
int res=1,tr=0;
for (ri i(1);i<=cnt;p(i)) {
for (ri j(i+1);j<=cnt;p(j)) {
while(G[j][i]) {
int k=G[i][i]/G[j][i];
for (ri l(i);l<=cnt;p(l)) G[i][l]=(G[i][l]-(ll)G[j][l]*k%MOD)%MOD;
swap(G[i],G[j]);tr^=1;
}
}
if (!G[i][i]) return 0;
res=(ll)res*G[i][i]%MOD;
}
return tr?-res:res;
}
inline int main() {
// FI=freopen("nanfeng.in","r",stdin);
// FO=freopen("nanfeng.out","w",stdout);
n=read(),cnt=n-1;st=(1<<n-1)-1;
for (ri i(1);i<=st;p(i)) siz[i]=siz[i>>1]+(i&1),lg[i]=lg[i>>1]+1;
for (ri i(1);i<n;p(i)) {
num[i]=read();
for (ri j(1);j<=num[i];p(j)) u[i][j]=read(),v[i][j]=read();
}
for (ri i(1);i<=st;p(i)) {
int low=i;
memset(G,0,sizeof(G));
while(low) {
int id=lg[lowbit(low)]+1;
for (ri j(1);j<=num[id];p(j)) add(u[id][j],v[id][j]);
low-=lowbit(low);
}
for (ri j(1);j<=n;p(j)) {
for (ri k(1);k<=n;p(k)) if (j^k) G[j][j]+=G[j][k],G[j][k]=-G[j][k];
}
// for (ri j(1);j<=n;p(j)) {
// for (ri k(1);k<=n;p(k)) printf("%d ",G[j][k]);
// puts("");
// }
int tmp=(Gauss()+MOD)%MOD;
// printf("state=%d tmp=%d
",i,tmp);
ans=((ll)ans+MOD+((n-siz[i])&1?tmp:-tmp))%MOD;
}
printf("%d
",ans);
return 0;
}
}
int main() {return nanfeng::main();}