看到这题面,应该是生成树计数了。
再容斥一下就好了。
可是我不会生成树计数啊!
回顾了一下矩阵树定理,发现有点不一样(可能以前学错了。
矩阵树定理只能背啊。。。
和普通的高斯消元有点不同,这是行列式。
所以互换时要反号(答案要取反)。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int M=570707,N=(1<<18)-1,mod=1e9+7;
const double pi=acos(-1);
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>
void qw(o x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
int u[20][400],v[20][400],siz[N],G[20][20],m[N];
inline int add(int x,int y){x+=y;if(x>=mod)x-=mod;return x;}
inline int del(int x,int y){x-=y;if(x<0)x+=mod;return x;}
inline int mul(int x,int y){x=1ll*x*y%mod;return x;}
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;}
inline int gauss(int n)
{
int f=1,ans=1;
for(int i=1;i<=n;i++)
{
int x=i;for(int j=i+1;j<=n;j++)if(G[j][i]>G[x][i])x=j;
if(x!=i){f=-f;for(int j=i;j<=n;j++)swap(G[x][j],G[i][j]);}
if(!G[i][i])return 0;
for(int k=1;k<=n;k++)
if(k!=i)
{
int sum=mul(G[k][i],fpow(G[i][i],mod-2));
for(int j=i;j<=n;j++)G[k][j]=del(G[k][j],mul(G[i][j],sum));
}
}
ans=mul(ans,f+mod);
for(int i=1;i<=n;i++)ans=mul(ans,G[i][i]);
return ans;
}
int main()
{
int n;qr(n);int s=(1<<(n-1))-1;
for(int i=1;i<n;i++){qr(m[i]);for(int j=1;j<=m[i];j++)qr(u[i][j]),qr(v[i][j]);}
siz[1]=1;for(int i=2;i<=s;i++)siz[i]=siz[i>>1]+(i&1);int ans=0;
for(int i=s;i>=1;i--)
{
memset(G,0,sizeof(G));
for(int p=i,j=1;p;p>>=1,++j)
if(p&1)for(int k=1;k<=m[j];k++)
{
int x=u[j][k],y=v[j][k];
++G[x][x];++G[y][y];
--G[x][y];--G[y][x];
}
if((n-siz[i])&1)ans=add(ans,gauss(n-1));
else ans=del(ans,gauss(n-1));
}
qw(ans);puts("");
return 0;
}
最后一次更新于2020-03-21
0 条评论