2 qq 33312212 qq_33312212 于 2016.03.23 23:24 提问

请问 状态压缩dp 中为什么要取模 而且 取 100000000代码如下
 #include<stdio.h>
#include<string.h>
#include<math.h>

#define mod 100000000
int n,m,a[15];
int dp[13][(1<<12)+10];

int check(int x,int flag)
{
    int i,temp=3;
    if((a[x]&flag)!=flag)//判断下那一行种是否能够找出flag这个状态
     return 0;
    if((flag&(flag<<1))!=0||(flag&(flag>>1))!=0)
     return 0;
    return 1;
}

void solve()
{
    int i,j,k,max,res=0;
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    max=1<<m;
    for(i=1;i<=n;i++)//枚举每一行
    {
        for(j=0;j<max;j++)//每一行的状态
        {
            if(check(i,j)==0)//看这一状态是否合法
             continue;
            for(k=0;k<max;k++)//枚举这一行上面的所有状态
            {
                if((j&k)!=0)
                 continue;
                dp[i][j]=dp[i][j]+dp[i-1][k];
                if(dp[i][j]>=mod)
                 dp[i][j]-=mod;
            }
        }
    }
    for(i=0;i<max;i++)
    {
        res=res+dp[n][i];
        if(res>=mod)
         res=res%mod;
    }
    printf("%d\n",res);
}

int main()
{
    int x;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int i,j;
        for(i=1;i<=n;i++)
        {
            a[i]=0;
            for(j=1;j<=m;j++)
            {
                scanf("%d",&x);
                a[i]=(a[i]<<1)+x;//把二进制压缩成一个十进制数字
            }
        }
        solve();
    }
    return 0;
}

其中

 for(k=0;k<max;k++)//枚举这一行上面的所有状态
            {
                if((j&k)!=0)
                 continue;
                dp[i][j]=dp[i][j]+dp[i-1][k];
                if(dp[i][j]>=mod)
                 dp[i][j]-=mod;
            }
        }
    }
    for(i=0;i<max;i++)
    {
        res=res+dp[n][i];
        if(res>=mod)
         res=res%mod;
    }

为什么 要取 100000000

3个回答

devmiao
devmiao   Ds   Rxr 2016.03.23 23:45
devmiao
devmiao   Ds   Rxr 2016.03.23 23:46

防止结果过大造成问题

CSDNXIAOD
CSDNXIAOD   2016.03.30 11:20

hdu2167 方格取数 状态压缩dp
----------------------biu~biu~biu~~~在下问答机器人小D,这是我依靠自己的聪明才智给出的答案,如果不正确,你来咬我啊!

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!