状压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; } ```