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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
状态压缩与动态规划(DP)---编程之美---瓷砖覆盖地板---POJ2411
一、状态压缩 从状态压缩的特点来看,这个算法适用的题目符合以下的条件: 1.解法需要保存一定的状态数据(表示一种状态的一个数据值) ,每个状态数据通常情况下是可以通过 2 进制来表示的。这就要求状态数据的每个单元只有两种状态,比如说棋盘上的格子,放棋子或者不放,或者是硬币的正反两面。这样用 0 或者 1 来表示状态数据的每个单元,而整个状态数据就是一个一串 0 和 1 组成的二进制数。
状态压缩DP 小结
好久没更新博客了~ 最近学了一下状压DP的内容,感觉对状态压缩有一点了解,不过有时候做题的时候总感觉有些吃力。今天做了2道TSP的题,虽然知道套路,但是对细节处理做的还是很不好,主要原因就是因为我对算法的认识还不够深刻吧,有时候碰到没有遇到过的题型的时候,总想着去查资料,没有深入思考过。其实费老强调过这一点。不要题海战术,要以一挡十。以后要改掉这个坏习惯。 言归正传。下面来总结一下,最近学状压D
铺砖问题(状态压缩DP)
给定n*m的格子,每个格子被染成了黑色或者白色。现在要用1*2的砖块覆盖这些格子,要求块与块之间互相不重叠,且覆盖了所有白色的格子,但不覆盖任意一个黑色格子。求一共有多少种覆盖方法,输出方案数对M取余后的结果。 限制条件: 1 1 2 思路:用图论的语言来说就是一个完美匹配;首先考虑枚举所有的解这一方法(即暴力搜索),为了不重复统计,我们每次从最左上方的空格处开始放置,对于哪些格
POJ3311(TSP问题,状态压缩DP)
题目链接:http://poj.org/problem?id=3311 分析:由于题中明确说了两个城市间的直接可达路径(即不经过其它城市结点)不一定是最短路径,所以需要借助邻接矩阵首先求出任意两个城市间的最短距离。这一步骤使用Floyd最短路径算法即可。然后,在此基础上来求出遍历各个城市后回到出发点的最短路径的距离,即求解TSP问题。 考虑搜索算法:这种解法其实就是计算排列子集树的过程。从0点
动态规划之状态压缩dp入门
状态压缩动态规划(简称状压dp)是另一类非常典型的动态规划,通常使用在NP问题的小规模求解中,虽然是指数级别的复杂度,但速度比搜索快,其思想非常值得借鉴。 为了更好的理解状压dp,首先介绍位运算相关的知识。 1.’&’符号,x&y,会将两个十进制数在二进制下进行与运算,然后返回其十进制下的值。例如3(11)&2(10)=2(10)。 2.’|’符号,x|y,会将两个十进制数在二进制下进行或运
位运算在状态压缩DP的运用技巧
位运算是既基础又好用的运算方法,它的实用性主要体现在状态压缩DP上,这也是状态压缩DP的难度所在, 如果不了解位运算,状态压缩DP会觉得很难理解。。。 接下来是位运算的实现技巧: 如果要获得 n 的第 i 位的数据(0还是1),判断(n&(1 如果要设置 n 的第 i 位为1,n=(n |(1 如果要设置 n 的第 i 位为0,n=(n &(~
TSP问题之状态压缩dp法
动态规划的状态有时候比较难,不容易表示出来,需要用一些编码技术,把状态压缩,用简单的方式表示出来。典型方式就是当需要表示一个集合有哪些元素时,往往利用2进制用一个整数表示。一般数据n
N皇后问题(状态压缩实现)
题目链接~~> 这题用 dfs()N范围一大了过不了,需要打表,用状态压缩可以状态压缩真是太强大了。 状态压缩 1:        在状态压缩中,通常用 ( 1 一、DFS函数参数Col,MainDiag,ContDiag的表示意义:        当整形数Col,MainDiag,ContDiag的第X位为1时,表示因为之前摆放的皇后的纵向攻击,主对角线斜向攻
HDU1565:方格取数(1) (状态压缩DP)
Problem Description 给你一个n*n的格子的棋盘,每个格子里面有一个非负数。 从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取的数所在的2个格子不能相邻,并且取出的数的和最大。   Input 包括多个测试实例,每个测试实例包括一个整数n 和n*n个非负数(n   Output 对于每个测试实例,输出可能取得的最大的和   Sample In
树型DP和状态压缩DP acm
树型DP和状态压缩DP acm 树型DP和状态压缩DP acm 树型DP和状态压缩DP acm