【CF908E】New Year and Entity Enumeration 位运算+DP

BitTigerio 2018-01-07

【CF908E】New Year and Entity Enumeration

题意:给定$M=2^m-1$,我们称一个集合S是好的,当且仅当它满足:1.$\forall a\in S,a \mathrm{xor} M \in S$,2.$\forall a,b\in S,a \mathrm{and} b \in S$,3.\forall a\in S,a\le M。

现在给定集合T,求有多少个好的集合S,满足T是S的子集。

m<=1000,|T|<=50。

题解:显然有了与和取反以后,我们还可以实现或和异或。如果给定T以后,我们对T中的数进行运算能得到什么数呢?容易发现如果二进制位a和位b如果在所有数中都是相同的,那么造出来的数也一定满足位a和位b是相同的。所有满足这个条件的数我们都能造出来。

也就是说,我们只需要确定S中哪些位是始终相同的,即把m个物品分到若干个集合的方案数(Bell数),用$m^2$的DP很容易求出。

但是由于要求T是S的子集,相当于认为的将某些物品分到了一起,我们可以对每个位置维护一个|T|位二进制状态,如果两个位置的状态是不同的,则这两个位置不是始终相同的,则S中对应位置也不能始终相同。所以我们可以对所有相同的状态,代入Bell数求出方案,再将不同状态的方案数乘到一起即可。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const ll P=1000000007;
bool ban[1010][1010];
int bel[1010];
int n,m;
ll ans;
ll tag[1010],f[1010][1010],s[1010];
char str[1010];
int main()
{
	scanf("%d%d",&m,&n);
	int i,j,siz;
	for(i=1;i<=n;i++)
	{
		scanf("%s",str+1);
		for(j=1;j<=m;j++)	if(str[j]=='1')	tag[j]|=1ll<<(i-1);
	}
	ans=f[0][0]=1;
	for(i=1;i<=m;i++)	for(j=1;j<=i;j++)	f[i][j]=(f[i-1][j]*j+f[i-1][j-1])%P,s[i]=(s[i]+f[i][j])%P;
	for(i=1;i<=m;i++)	if(!bel[i])
	{
		siz=0;
		for(j=i;j<=m;j++)	if(tag[j]==tag[i])	bel[j]=i,siz++;
		ans=ans*s[siz]%P;
	}
	printf("%lld",ans);
	return 0;
}

相关推荐

OccamsRazor / 0评论 2018-02-05