New Set

我的思路：因为题目中说是⾄少⼀个 Ai 能分离 (X,Y)，我们容斥枚举⼀个 A 的集合
S，然后计算能被 S 中每⼀个分离的 (X,Y) 的个数
如何计算 (X,Y) 的对数呢，根据题⽬条件，A 能分离 (X,Y)，当且仅当
X,Y 中⼀个是 A 的⼦集，另⼀个跟 A 没有交
我们在枚举 S 中每个 A 是 X 的超集还是 Y 的超集
然后就可以⼤⼒统计了O(3^m*n)，吼啊,20分

正确的：考虑上⾯那个暴⼒最后怎么算答案
假设 S 被分为 U+V，其中 U 中的 A 都是 X 的超集，且与 Y ⽆
交，V 则相反
则可选的 X 是 U 的交的⼦集，且不能与 V 中任何⼀个集合有交
也就是说，如果 a 是 X 的⼀个元素，那么 a 是 U 中所有集合的
元素，且不是 V 中任何⼀个集合的元素
我们可以通过数有⼏个元素满⾜条件来计算 (X,Y)

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define rep2(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define per(i,j,k) for(int i=(int)j;i>=(int)k;i--)
using namespace std;
typedef long long ll;
const int maxn=1e2+5,mod=1e9+7;
int n,m,k,ans;
int binom[maxn][maxn],a[18][maxn],v[maxn],vv[1<<18];
int main()
{
 cin>>n>>m>>k;
 rep(i,0,n)
  rep(j,0,i)
   binom[i][j]=!j?1:(binom[i-1][j-1]+binom[i-1][j])%mod;
 rep2(i,0,m)
 {
  int c;
  cin>>c;
  rep(j,1,c)
  {
   int x;
   cin>>x;
   a[i][x]=1;
  }
 }
 rep2(s,1,1<<m)
 {
  int flag=mod-1;
  rep(i,1,n)
   v[i]=0;
  int cnt=0;
  rep2(i,0,m)
  { 
   if(s>>i&1)
   {
    flag=mod-flag;
    rep(j,1,n)
     if(a[i][j])
      v[j]|=1<<cnt;
    cnt++;
   }
  } 
  sort(v+1,v+n+1);
  rep(i,1,n)
   vv[v[i]]++;
  rep(i,1,n)
  { 
   if((i==1)||(v[i]!=v[i-1]))
   {
    int v1=v[i],v2=((1<<cnt)-1)^v1;
    ans=(ans+1ll*flag*binom[vv[v1]][k]%mod*binom[vv[v2]][k]%mod)%mod;
   }
  } 
  rep(i,1,n)
   vv[v[i]]--;
 }
 cout<<ans<<endl;
 return 0;
}