时间限制 2000ms
空间限制 256MB
题意描述
给定一个整数\(m\)，设\(M=2^m-1\)
给定一个整数\(n\)，和一个包含\(n\)个元素的整数集合\(T\)，每个元素以\(m\)位\(2\)进制串的形式输入。
如果一个集合\(S\)是好集，当且仅当一以下条件同时满足：
\(1.?a∈S,a\,XOR\,M∈S\)
\(2.?a,b∈S,a\,AND\,b∈S\)
\(3.T?S\)
\(4.?a∈S,a≤M\)
\(XOR\)与\(AND\)运算分别表示按位异或，按位与运算。
你需要求出在以上条件下，好集的个数\(mod\,(10^9+7)\)的结果。
第一行包含两个数\(m,n\)（注意输入顺序）
接下来\(n\)行，表示集合\(T\)的所有元素。每行恰有\(m\)个字符，每个字符都为\(0\)或\(1\)。
输出一个整数即好集的个数\(mod\,(10^9+7)\)的结果。
样例1输入
5 3
11010
00101
11000
样例1输出
4
样例2输入
30 2
010101010101010010101010101010
110110110110110011011011011011
样例2输出
860616440
样例1说明
一个合法集合\(S\)的例子是{\(00000,00101,00010,00111,11000,11010,11101,11111\)}
数据范围
对于\(10\%\)的数据，\(n,m≤5\)
对于\(30\%\)的数据，\(n,m≤10\)
对于\(100\%\)的数据，\(1≤m≤1000,1≤n≤min(2^m,50)\)
条件\(?a∈S,a\,XOR\,M∈S\)，本质上就是说如果\(a\)在集合内，那么\(a\)的取反也在集合内。
可以观察到满足前三个条件的前提下，第四个条件一定满足。按位与只会越与越小不会越与越大。
我们先不考虑第三个条件，先考虑满足前两个的情况。
观察到\(S\)中所有第\(i\)位为\(1\)的数，设他们按位与的结果为\(f(i)\)，则\(f(i)\&2^i=1\)，同时\(f(i)=min(\{x|x∈S且x\&2^i=1\})\)
证明\(?f(x)≠f(y),f(x)\&f(y)=0\)：
? 令\(b=f(x)\&f(y)\)，不妨设\(b≠f(x)\)，注意与一般性不冲突因为\(f(x)≠f(y)\)
? 分以下两种情况讨论：
? 1.如果\(b\&2^x=1\)，则\(x<f(x)\)，与\(f\)是第\(i\)位为1的最小元素矛盾。
? 2.如果\(b\&2^x=0\)，则\(f(x)\&(b \wedge M)\)与\(f\)是第\(i\)位为1的最小元素矛盾。
通俗来说，如果\(f(x)≠f(y)\)，那么\(f(x)\)与\(f(y)\)的每一位不可能同为\(1\)。
这个问题就变成了一个\(1\)的分配问题：
比如说对于
存在分配情况\(P\)
如果任意\(f(x)\)改变，不如第\(z\)位变为\(1\)，那么不仅会加入\(f(z)=f(x)\)，对于\(f(y)=f(x)\)，包含\(2^y\)位的最小元素也变大了，说明\(S\)改变了。
于是，每一个分配方案对应一个集合\(S\)，\(S\)的个数就变成了\(1\)的分配方案。
考虑贝尔数\(B\)，\(B_n\)是基数为\(n\)的集合划分数目。
满足
可以用第二类斯特林数证明。
那么求出满足\(T?S\)条件的解也非常简单，对于\(T\)中满足所有数字的第\(i\)位都为\(1\)的集合的\(f_i\)，也满足\(?f(x)≠f(y),f(x)\&f(y)=0\)，定义一个集合的集合\(Q_k\)，满足其元素的\(f\)都相同，将其定义为\(Q_k\)的\(f\)，我们对于每一个\(Q\)分别考虑，计算其\(f\)在二进制在中的分布情况\(P_k\)，即\(B_{|Q_k|}\)，最终答案自然就是\(\prod \limits B_{|Qk|}\)
具体实现，如果一个二进制位\(i\)，其满足\(T\)中第\(i\)位是\(1\)的集合与二进制\(j\)在\(T\)中满足第\(j\)位是\(1\)的集合相同（可以用状压判断），那么都把他们丢进集合\(Q_k\)，答案就乘上\(B_{|Q_k|}\)（用\(map\)保存\(|Q_k|\)即可)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int N=1010;
int m, n;
ll C[N][N], a[N], bell[N];
map<ll,int>ma;
int main() {
scanf("%d%d", &m, &n);
C[0][0]=1;
for(int i=1; i<=m; i++) {
for(int j=0; j<=i; j++) {
C[i][j]=(C[i-1][j]+((j)?C[i-1][j-1]:0))%mod;
}
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
char ch=getchar();
while(ch!=‘0‘&&ch!=‘1‘) ch=getchar();
a[j]|=(1ll*(ch-‘0‘))<<i;
}
}
for(int j=1; j<=m; j++) ma[a[j]]++;
bell[0]=1;
for(int i=1; i<=m; i++) {
for(int j=0; j<i; j++) {
bell[i]+=C[i-1][j]*bell[j]%mod;
bell[i]%=mod;
}
}
ll ans=1;
for(map<ll,int>::iterator i=ma.begin();i!=ma.end();i++)ans=ans*bell[(*i).second]%mod;
printf("%lld\n", ans);
}
CF908E New Year and Entity Enumeration
原文：https://www.cnblogs.com/2017gdgzoi1164/p/15151670.html