状压dp 玉米田

· · 个人记录 

1.’&’符号，x&y，会将两个十进制数在二进制下进行与运算(都1为1，其余为0） 
然后返回其十进制下的值。例如3(11)&2(10)=2(10)。

2.’|’符号，x|y，会将两个十进制数在二进制下进行或运算（都0为0，其余为1） 
然后返回其十进制下的值。例如3(11)|2(10)=3(11)。

3.’^’符号，x^y，会将两个十进制数在二进制下进行异或运算（不同为1，其余 
为0）然后返回其十进制下的值。例如3(11)^2(10)=1(01)。

4.’<<’符号，左移操作，x<<2，将x在二进制下的每一位向左移动两位， 
最右边用0填充，也就相当于让x乘以4。

相应的，’>>’是右移操作，x>>1相当于给x/2，去掉x二进制下的最右一位。

这四种运算在状压dp中有着广泛的应用，常见的应用如下：

1.判断一个数字x在二进制下第i位是不是等于1。 
方法：if ( ( ( 1 << ( i - 1 ) ) & x ) >0)

解析:将1左移i-1位，相当于制造了一个只有第i位上是1， 
其他位上都是0的二进制数,然后用该数与x做与运算， 
如果结果>0，说明x第i位上是1，反之则是0。

2.把一个数字x在二进制下的第i位更改成1。

方法：x |= ( 1<<(i-1) )

证明方法与1类似（将1左移i-1位，相当于制造了一个只有第i位上是1， 
其他位上都是0的二进制数,然后用该数与x做或运算，只要存在1就为1， 
所得结果即为新的x值

3.把一个数字二进制下最靠右的第一个1去掉。

方法：x=x&(x-1)

#include<bits/stdc++.h>
using namespace std;

template<class T>
void read(T &x)
{
    T a=0,f=1;char s=getchar();
    while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){a=(a<<3)+(a<<1)+s-'0';s=getchar();}
    x=a*f;
}

const int N=4096;
const int mod=1e9;

int f[15][N];

int cur[N];

int state[N];

int ma[20][20];

int n,m;

int main()
{
    read(m);
    read(n);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            read(ma[i][j]);
        }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            cur[i]=(cur[i] << 1 )+ ma[i][j];
        }   
    int maxstate=1<<n;

    for(int i=0;i<maxstate;i++)
    {
        if(i&(i<<1)||i&(i>>1))continue;
        state[i]=1;
    }
    f[0][0]=1;
    for(int i=1;i<=m;i++)
        for(int j=0;j<maxstate;j++)
        {
            if(state[j]&&(j & cur[i])==j)
                for(int k=0;k<maxstate;k++)
                {
                    if( (k&j) ==0)f[i][j]=(f[i-1][k]+f[i][j])%mod;
                }
        }
    int ans=0;
    for(int j=0;j<maxstate;j++)
    {
        ans=ans+f[m][j];
        if(ans>mod)ans-=mod;
    }
    cout<<ans;
    return 0;
}