题意：
有M个开关，控制着N个灯，触碰一下开关，会把他所控制的灯的状态改变。对于M个开关你可以选择碰一次或者不碰，求最后开着多少个灯的三次方的期望值E(X^3)*2^m
题解：原式显然可以分解成X3 X=（x1+x2+x3...+xn),其中xi表示第i个灯的状态，题目就转化为求各个状态下X的立方的和
而X的立方可以看成是（x1+x2+x3...+xn)*（x1+x2+x3...+xn)*（x1+x2+x3...+xn)也就是xi*xj*xk的和，那么我们只要求出对于所有xi*xj*xk在所有状态中能为1的方法数，也就是i,j,k三灯全亮的方法数，加起来就是答案。用dp[i][j][k][ste][2]转移ste表示三个灯的状态，最后一个数组表示从处理前i个开关到处理前i+1个开关的滚动数组转移，注意滚动数组的初始化和DP不合法的判断
//#pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <vector> #include <algorithm> #include <iostream> #include <map> #include <queue> #include <stack> #include <cmath> typedef long long ll; #define CLR(x, v) sizeof (x, v, sizeof(x)) using namespace std; const int INF = 0x5f5f5f5f; const int mod=1e9 + 7; const int maxn = 60; int t,n,m; int dp[maxn][maxn][maxn][10][2]; bool gra[maxn][maxn]; int main() { //freopen("in","r",stdin); cin>>t; int cas = 0; while(t--){ cas++; scanf("%d%d",&n,&m); int k,l; memset(dp,0,sizeof(dp)); memset(gra,false,sizeof(gra)); for(int i = 1;i <= m;i++){ scanf("%d",&k); while(k--){ scanf("%d",&l); gra[i][l] = true; } } int id = 0; memset(dp, 0, sizeof dp); for(int i = 1;i <= n;i++) for(int j = 1 ;j <= n;j++) for(int k = 1;k <= n;k++){ // if(i == j||j == k||i == k) continue; dp[i][j][k][0][0] = 1; } for(int t = 1;t <= m;t++){ for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) for(int k = 1;k <= n;k++) for(int ste = 0;ste < 8;ste++) dp[i][j][k][ste][id^1] = 0; for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) for(int k = 1;k <= n;k++){ // if(i == j||j == k||i == k) continue; for(int ste = 0;ste < 8;ste++){ if (dp[i][j][k][ste][id] == 0) continue; dp[i][j][k][ste][id^1] += dp[i][j][k][ste][id]; dp[i][j][k][ste][id^1] %= mod; int ans = ste; if(gra[t][i]) ans ^= 1; if(gra[t][j]) ans ^= 2; if(gra[t][k]) ans ^= 4; dp[i][j][k][ans][id^1] += dp[i][j][k][ste][id]; dp[i][j][k][ans][id^1] %= mod; // cout<<t<<" "<<i<<" "<<j<<" "<<k<<" "<<ans<<" "<<dp[i][j][k][ans][id^1]<<endl; } } id ^= 1; } // cout<<n<<endl; int sum = 0; for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) for(int k = 1;k <= n;k++){ sum += dp[i][j][k][7][id]; sum %= mod; } printf("Case #%d: %d ",cas,sum); } return 0; }