题意
有N个灯和M个开关，每个开关控制着一些灯，如果按下某个开关，就会让对应的灯切换状态；问在每个开关按下与否的一共2^m情况下，每种状态下亮灯的个数的立方的和。
思路
1、首先注意到N<=50,M<=50，因此很容易想到状压；
2、考虑X^3，其中X就是每种状况下亮着的灯的数量；
3、如何解这个X^3？我们把它展开——
X=x1+x2+x3+...+xn，其中xi是第i个灯的亮或暗状况；
因此X^3=(x1+x2+x3+...+xn)*(x1+x2+x3+...+xn)*(x1+x2+x3+...+xn)=Σxi*xj*xk (1<=i<=j<=k<=n);
4、dp[m][state]代表前m个开关，达成状态为state的方案数，其中state从(000)2~(111)2，代表三个灯的亮或灭；在其基础上dp就行了；遍历i,j,k，同时将开关的控制状态压缩。
5、答案每次加上dp[m][7]，因为只有xi=xj=xk=1时，才对X^3有贡献，总复杂度O(n^3*m)；
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
#define ull unsigned long long
#define LOCAL using namespace std;
const int maxn=1e5+;
const int inf=0x3f3f3f3f;
const int mod=1e9+; ll d[][];
ll s[]; int main(){
int t,n,m,num;
cin>>t;
for(int kase=;kase<=t;kase++){
memset(s,,sizeof(s));
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d",&num);
for(int j=;j<=num;j++){
int t;
scanf("%d",&t);
s[i]|=(1LL<<t);///状压
}
}
ll ans=;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
for(int k=;k<=n;k++){
memset(d,,sizeof(d));
d[][]=;
for(int x=;x<=m;x++){
for(int y=;y<;y++){
int t=y;
if(s[x]&(1LL<<i)) t^=;
if(s[x]&(1LL<<j)) t^=;
if(s[x]&(1LL<<k)) t^=;
d[x][y]+=d[x-][y];
d[x][t]+=d[x-][y];
}
}
ans=(ans+d[m][])%mod;
}
}
}
printf("Case #%d: %lld\n",kase,ans);
}
return ;
}