本文主要是介绍hdu5117 Fluorescent DP,期望，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：n盏灯，m个开关，每个开关控制一些灯，用1表示控制，0表示不控制，异或为1时这盏灯亮，每个开关可开可不开，概率相同。现在问E(x^3)*(2^m)，E为期望，x为亮灯数。
分析：如果求的是E[x]*(2^m)，则可以考虑每一盏灯的状态，O(m)求出使这盏灯亮的方案数。
现在求每种方案下，(x1+x2+x3+...+xn)^3，用0表示不亮，1表示亮，展开即为C*xi*xj*xk，当i,j,k两两不同时C=6，一对相同时C=3，全部相同时C=1。
这样就考虑每3盏灯的状态，O(m)求出，累加即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<ostream>
#include<istream>
#include<algorithm>
#include<queue>
#include<string>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<vector>
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define inf (1<<30)
#define eps 1e-8
#define pb push_back
#define debug puts("=====")
using namespace std;
const int maxn=100005;
const ll mod=1000000007;
int n,m;
int f[55][55];
ll dp[2][2][2][2];
int main()
{int cas=1;int t;int k,a;scanf("%d",&t);while(t--) {scanf("%d%d",&n,&m);memset(f,0,sizeof(f));for(int i=1;i<=m;i++) {scanf("%d",&k);while(k--) {scanf("%d",&a);f[i][a]=1;}}ll ans=0;for(int i=1;i<=n;i++) {for(int j=i;j<=n;j++) {for(int k=j;k<=n;k++) {memset(dp,0,sizeof(dp));int now=0;dp[0][0][0][0]=1;for(int e=1;e<=m;e++) {memset(dp[now^1],0,sizeof(dp[now^1]));for(int a=0;a<2;a++) {for(int b=0;b<2;b++) {for(int c=0;c<2;c++) {dp[now^1][a][b][c]+=dp[now][a][b][c];dp[now^1][a][b][c]%=mod;dp[now^1][a^f[e][i]][b^f[e][j]][c^f[e][k]]+=dp[now][a][b][c];dp[now^1][a^f[e][i]][b^f[e][j]][c^f[e][k]]%=mod;}}}now^=1;}if(i!=j && j!=k && i!=k) {ans+=dp[now][1][1][1]*6;ans%=mod;}else if(i==j && j==k) {ans+=dp[now][1][1][1];ans%=mod;}else {ans+=dp[now][1][1][1]*3;ans%=mod;}//cout<<i<<" "<<j<<" "<<k<<" "<<ans<<endl;}}}printf("Case #%d: %I64d\n",cas++,ans);}return 0;
}这篇关于hdu5117 Fluorescent DP,期望的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
