转载

$Luogu$ $P1879$ $[USACO06NOV]$ 玉米田 $Corn Fields$

链接

背景

\(USACO\) \(2006\) \(Nov.\) \(Gold\) \(T2\)\(Luogu\) \(P1879/POJ3254/AcWing327\)

题意

给定 \(n\)\(m\) 列的矩阵,每个格子中的数为 \(0\)\(1\) ,表示是否能使用( \(1\) 表示能使用)。求选出两两不相邻的任意多个能使用的格子的方案数对 \(10^9\) 取模的值。

解法

预处理每一行数的总可使用状态,设第 \(i\) 行数总可使用状态为 \(gr_i\)
\(f_{i,S}\) 表示选完第 \(i\) 行后,第 \(i\) 行的状态为 \(S\) 的总方案数。则转移方程为 \(f_{i,k}+=f_{i-1,S}\)\((S \& k=0) \&\& (k \& (k>>1)=0) \&\& (k \& gr_i=0)\) )。
限制条件的含义是第 \(i-1\) 行和第 \(i\) 行每个在同一列的数状态都不相同,且第 \(i\) 行每两个相邻数状态都不相同,且第 \(i\) 行所有的被选数都可以使用。
则边界条件是 \(f_{0,0}=1\) ,意为一个也不选的方案唯一;答案是 \(\sum_{S=0}^{2^m-1} f_{n,S}\) ,意为所有行选完后最后一行所有状态的总方案数。

\(trick\)

对于是否是可使用的格子判断:设当前状态为 \(j\) ,该行总可使用状态为 \(S\) 。那么当前状态内所有选中的格子全部可以使用的条件是 \(j \& S =j\) 。原因是按位或运算的性质,只有在某一位上 \(j=1\)\(S \neq 1\) 时总的运算结果才会 \(\neq j\)

细节

\(1.\) 枚举的顺序:先枚举当前行方案是否合法,再枚举与上一行是否有相同位(两行是否兼容)。

\(2.\) 对于一行数总可使用状态的建立:从左往右建立,按自然规律左移添加位数即可。

代码

\(View\) \(Code\)

#include<bits/stdc++.h> using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } const int mod=1e9; int n,m,gr[13],f[13][4096],ans; bool a[13][13]; int main() { n=read(); m=read(); for(register int i=1;i<=n;i++) { for(register int j=1;j<=m;j++) { a[i][j]=read(); gr[i]=(gr[i]<<1)+a[i][j]; } } f[0][0]=1; for(register int i=1;i<=n;i++) for(register int j=0;j<(1<<m);j++) if(!(j&(j/2))&&((j&gr[i])==j)) for(register int k=0;k<(1<<m);k++) if(!(j&k)) f[i][j]=(f[i][j]+f[i-1][k])%mod; for(register int i=0;i<(1<<m);i++) ans=(ans+f[n][i])%mod; printf("%d\n",ans); return 0; }

转载于:https://www.cnblogs.com/Peter0701/p/11589299.html

正文到此结束
本文目录