首页 > 代码库 > hdu5117(数学推导+dp)

hdu5117(数学推导+dp)

2024-08-05 10:57:04   215人阅读

题意：有n(n<=50)个灯,初始状态都是关闭，有m个开关，每个开关都控制若干个灯，按下一个开关，他所控制的灯就会由闭到开，或是由开到闭。问在m个开关按下与否的2^m的情况中，求每种情况下亮灯数量的立方和。


解法：假设一种情况是开灯数是X， X=（x1+x2+x3...xn)，xi是第i个灯的开闭情况。

则X^3=（x1+x2+x3...xn)*（x1+x2+x3...xn)*（x1+x2+x3...xn)。即求三个灯的三三组合Xi*Xj*Xk，只有Xi，Xj，Xk都为1时候，他们的乘积才是1.

 dp[i][j][k][state]表示三个灯ijk状态为state的方案数，state为0-7，状压表示每个灯的开闭。转移就是枚举每个开关的开闭。然后就是转移计算所有状态了。


代码：
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int Max=51;
int rem[Max][Max];
const long long INF=1000000007;
int dp[Max][Max][Max][8][2];

int n,m;
int main()
{
    int t;
    scanf("%d",&t);
    int kk=1;
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        memset(rem,0,sizeof rem);
        for(int i=0; i<m; i++)
        {
            int a;
            scanf("%d",&a);
            while(a--)
            {
                int k;
                scanf("%d",&k);
                k--;
                rem[i][k]=1;
            }
        }

        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                for(int k=0; k<n; k++)
                {
                    dp[i][j][k][0][1]=1;
                    for(int h=1; h<8; h++)
                        dp[i][j][k][h][1]=0;
                }
        int now=0;
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
                for(int k=0; k<n; k++)
                    for(int h=0; h<n; h++)
                    {
                        int tt=0;
                        if(rem[i][j])tt^=1;
                        if(rem[i][k])tt^=2;
                        if(rem[i][h])tt^=4;
                        for(int x=0; x<8; x++)
                            dp[j][k][h][x][now]=dp[j][k][h][x][now^1];
                        for(int x=0; x<8; x++)
                            dp[j][k][h][x^tt][now]=(dp[j][k][h][x^tt][now]+dp[j][k][h][x][now^1])%INF;
                    }
            now^=1;
        }
        long long ans=0;
        for(int j=0; j<n; j++)
            for(int k=0; k<n; k++)
                for(int h=0; h<n; h++)
                    ans=(ans+dp[j][k][h][7][now^1])%INF;
        printf("Case #%d: %I64d\n",kk++,ans);
    }
    return 0;
}


hdu5117(数学推导+dp)


联系
我们