背景
(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 eq 1) 时总的运算结果才会 ( eq j) 。
细节
(1.) 枚举的顺序：先枚举当前行方案是否合法，再枚举与上一行是否有相同位（两行是否兼容）。
(2.) 对于一行数总可使用状态的建立：从左往右建立，按自然规律左移添加位数即可。