自动搬运

查看原文

来自洛谷，原作者为

	Owen_codeisking 前OIer/ACMer/柚子厨/酒姬民

搬运于2025-08-24 21:31:24，当前版本为作者最后更新于2018-07-18 13:44:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前排警告

这是写给刚学的我看的，大佬请自动忽略

人生第一道状压$dp$ 互不侵犯是学术交流过的

本蒟蒻今天在机房听到状压$dp$，感觉很高大上……其实就是位运算高大上一点

解释一下位运算：

& 给个例子

$0110101+1010011=0010001$，返回值为$17$

$n<<k$ 将$n$左移$k$位，相当于给$n$乘上$2^k$

$n>>k$ 将$n$右移$k$位，相当于给$n$除以$2^k$后向下取整

解释一下状压$dp$：

它的基本思想就是用二进制来优美地暴力枚举出现的方案，

若二进制下第$i$位有赋值$1$，则一行的第$i$列有放牛

那么$f[i][j]$表示在前$i$行中（包括$i$）在$j$个状态下的最大方案数

易得$f[i][j]=(f[i][j]+f[i-1][k])\ mod\ p$（$p=10^9$，$j$是第$i$行的状态，$k$是第$i-1$行的状态）

所以我们还要再预处理一下，$g[i]$表示第$i$个状态是否存在，判断条件是

$g[i]=$ $!(i$&$(i>>1))!(i$&$(i<<1))$

目标状态：$f[n][i]$全部相加

$Code \ Below:$

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int p=100000000;
ll f[13][1<<12],n,m;
ll g[1<<12],h[1<<12],a[13][13];
ll F[13];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			F[i]=(F[i]<<1)+a[i][j];
	for(int i=0;i<(1<<m);i++){
		if(!(i&(i>>1))&&!(i&(i<<1))){
			g[i]=1;
			if((i&F[1])==i) f[1][i]=1;
		}
	}
	for(int x=2;x<=n;x++)
		for(int j=0;j<(1<<m);j++)
			if(((j&F[x-1])==j)&&g[j])
				for(int k=0;k<(1<<m);k++)
					if(((k&F[x])==k)&&!(j&k)&&g[k]){
						f[x][k]=(f[x][k]+f[x-1][j])%p;
					}
	int ans=0;
	for(int i=0;i<(1<<m);i++)
		ans=(ans+f[n][i])%p;
	printf("%d\n",ans);
    return 0;
}