「SHOI2016」黑暗前的幻想乡 解题报告

「SHOI2016」黑暗前的幻想乡

sb题想不出来，应该去思考原因，而不是自暴自弃

一开始总是想着对子树做dp，但是状态压不起去，考虑用容斥消减一些条件变得好统计，结果越想越乱。

期间想过矩阵树定理，但没想清楚又被我忽略了。

其实非常简单

你对着所有的东西跑一遍生成树计数，然后你发现统计了同一个施工队的方案，然后发现可以枚举子集，就是个sb容斥了

---

Code:

#include <cstdio>

#include <cctype>

#include <algorithm>

const int mod=1e9+7;

const int N=20;

inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}

#define mul(a,b) (1ll*(a)*(b)%mod)

int qp(int d,int k){int f=1;while(k){if(k&1)f=mul(f,d);d=mul(d,d),k>>=1;}return f;}

template <class T>

void read(T &x)

{

	x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

}

struct node{int u,v;}E[N][N*N];

int n,ans,g[N][N],cnt[N];

int Gauss()

{

	int f=0,ret=1;

	for(int i=1;i<=n;i++)

	{

		int id=i;

		for(int j=i;j<=n;j++)

			if(g[j][i])

			{

				id=j;

				break;

			}

		if(g[id][i]==0) return 0;

		if(id!=i) std::swap(g[i],g[id]),f^=1;

		for(int j=i+1;j<=n;j++)

		{

			int inv=mul(g[j][i],qp(g[i][i],mod-2));

			for(int k=i;k<=n;k++)

				g[j][k]=add(g[j][k],mod-mul(g[i][k],inv));

		}

		ret=mul(ret,g[i][i]);

	}

	return f?add(mod,-ret):ret;

}

int main()

{

	read(n);

	--n;

	for(int i=1;i<=n;i++)

	{

		read(cnt[i]);

		for(int j=1;j<=cnt[i];j++)

			read(E[i][j].u),read(E[i][j].v);

	}

	for(int s=0;s<1<<n;s++)

	{

		int ct=0;

		for(int i=1;i<=n;i++)

			for(int j=1;j<=n;j++)

				g[i][j]=0;

		for(int i=1;i<=n;i++)

			if(s>>i-1&1)

			{

				for(int j=1;j<=cnt[i];j++)

				{

					int u=E[i][j].u,v=E[i][j].v;

					g[u][v]=add(g[u][v],mod-1),g[v][u]=add(g[v][u],mod-1);

					++g[u][u],++g[v][v];

				}

				++ct;

			}

		ct=(n-ct&1)?mod-1:1;

		ans=add(ans,mul(ct,Gauss()));

	}

	printf("%d\n",ans);

	return 0;

}

---

2019.3.12