【XSY2701】异或图 线性基 容斥原理

2018/03/06 15:29
阅读数 16

题目描述

  定义两个图$G_1$与$G_2$的异或图为一个图$G$,其中图$G$的每条边在$G_1$与$G_2$中出现次数和为$1$。

  给你$m$个图,问你这$m$个图组成的集合有多少个子集的异或图为一个连通图。

  $n\leq 10,m\leq 60$

题解

  考虑枚举图的子集划分,让被划分到不同子集的点之间没有连边,而在同一个子集里面的点可以连通,可以不连通。

  可以用高斯消元(线性基)得到满足条件的图的个数。设枚举的子集划分有$k$个集合,那么容斥系数就是${(-1)}^{k-1}(k-1)!$。并把当前的方案数乘以容斥系数计入答案。

  那么容斥系数是怎么来的呢?

  记$c_i$为$i$个集合的容斥系数。对于每一个联通块个数为$j$的图,对枚举到的联通块个数为$i$的方案有$S(j,i)$的贡献。

  我们只需要让$\sum_{i=m}^nc(i)S(i,m)=[m=1]$就可以了。

  可以打表消元消除容斥系数。

  时间复杂度:$O(B_nn^2m)$,其中$B_n$是Bell数的第$n$项。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
char s[1010];
int n,m;
ull a[20][20];
int d[20];
ull ans=0;
ull pw[70];
ull fac[70];
ull c[70];
void dfs(int x,int y)
{
	if(x>n)
	{
		int i,j,k;
		for(i=0;i<m;i++)
			c[i]=0;
		for(i=1;i<=n;i++)
			for(j=i+1;j<=n;j++)
				if(d[i]!=d[j])
				{
					ll s=a[i][j];
					for(k=m-1;k>=0;k--)
						if(s&(1ll<<k))
						{
							if(!c[k])
							{
								c[k]=s;
								break;
							}
							s^=c[k];
						}
				}
		int num=0;
		for(i=0;i<m;i++)
			if(!c[i])
				num++;
		ans+=pw[num]*fac[y-1]*(y&1?1:-1);
		return;
	}
	int i;
	for(i=1;i<=y;i++)
	{
		d[x]=i;
		dfs(x+1,y);
	}
	d[x]=y+1;
	dfs(x+1,y+1);
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	scanf("%d",&m);
	int i,j,k;
	int len;
	fac[0]=1;
	pw[0]=1;
	for(i=1;i<=m;i++)
		pw[i]=pw[i-1]<<1;
	for(i=1;i<=m;i++)
	{
		scanf("%s",s+1);
		if(i==1)
		{
			len=strlen(s+1);
			for(j=2;j<=10;j++)
				if(j*(j-1)/2==len)
					break;
			n=j;
		}
		int t=0;
		for(j=1;j<=n;j++)
			for(k=j+1;k<=n;k++)
				if(s[++t]=='1')
					a[j][k]|=1ll<<(i-1);
	}
	for(i=1;i<=n;i++)
		fac[i]=fac[i-1]*i;
	dfs(1,0);
	printf("%llu\n",ans);
	return 0;
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部