专业品牌设计网站建设/站长工具免费

传送门

考虑容斥原理,答案计算为

所有二进制为$1$-至少一位二进制不为$1$+至少两位二进制不为$1$…

一遍$sosdp$求出$f[mask]$

那么从$mask$的子集中选出任意组合,$1$的个数最多就是$mask$中$1$的个数

换而言之,至少有$m-one(mask)$位二进制不为$1$

其中$one(mask)$表示$mask$中$1$的个数

容斥即可

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
#define int long long
const int maxn = 1<<20;
int n,m,a[maxn],f[maxn],mx=1<<20,ans;
int quick(int x,int n)
{int ans = 1;for( ; n ; n>>=1,x=x*x%mod )if( n&1 )	ans = ans*x%mod;return ans;
}
signed main()
{cin >> n >> m;mx = 1<<m;for(int i=1;i<=n;i++){int x; cin >> x;for(int j=1;j<=x;j++) { int w; cin >> w; a[i] |= (1<<(w-1)); }f[a[i]]++;}for(int i=0;i<m;i++)for(int j=mx-1;j>=0;j--)if( j&(1<<i) )	f[j]+=f[j^(1<<i)];for(int i=0;i<mx;i++)	f[i] = quick( 2,f[i] )-1;for(int i=0;i<mx;i++){int x = i,temp = m;while( x )	{ temp -= (x&1), x>>=1; } if( temp%2==0 )	ans += f[i];else	ans -= f[i];ans %= mod;}cout << (ans+mod)%mod;
}