T7 - 乌龟养殖场
题目链接跳转：点击跳转
前置知识：
1. 了解过基本的动态规划。
2. 熟练掌握二进制的位运算。
> 至于为什么放了一道模版题，原因是因为需要凑到八道题目，实在凑不到了，找了一个难度适中的。
题解思路
这是一道典型的状压动态规划问题。设 dpi,jdp_{i, j}dpi,j 表示遍历到第 iii 行的时候，当前行以 j(base2)j_{(base2)}j(base2) 的形式排列乌龟可以构成的方案数。
对于每一行的方案，我们可以用一个二进制来表示。例如二进制数字 101001010010100，表示有一个横向长度为 555 的场地中，第 1,31, 31,3 号位置分别放置了一只小乌龟。因此，每一种摆放状态都可以用一个二进制数字来表示。我们也可以通过遍历的方式来遍历出二进制的每一种摆放状态。
首先，我们预处理出横排所有放置乌龟的合法情况。根据题意，两个乌龟不能相邻放置，因此在二进制中，不能有两个 111 相邻。如何预处理出这种情况呢？我们可以使用位运算的方法：
如果存在一个二进制数字有两个 111 相邻，那么如果我们对这个数字 xxx 进行位运算操作 (x << 1) & x 的结果或 (x >> 1) & x 的结果必定大于等于 111。我们通过把这种情况排除在外。同时，我们还需要注意有些格子中不能放置乌龟。这一步也可以通过二进制的方法预处理掉，如果网箱在第 iii 一个格子中不能放置乌龟，那么在枚举所有方案数的时候直接忽略掉第 iii 位为 111 的情况即可。
接下来如何保证上下两行的乌龟不冲突？假如上一行的摆放状态是 yyy，当前行的摆放状态为 jjj，如果 i & j 的结果大于等于 111，也可以证明有两个数字 111 在同一位置上。因此我们也需要把这种情况排除在外。
综上所述，我们可以得出状态转移方程：dpi,j=dpi,j+dpi−1,kdp_{i, j} = dp_{i, j} + dp_{i-1, k}dpi,j =dpi,j +dpi−1,k 。其中，jjj 和 kkk 表示所有横排合法的方案。答案就是 ANS=∑j=02M−1dpN,j\mathtt{ANS} = \sum_{j=0}^{2^M-1}{dp_{N, j}}ANS=∑j=02M−1 dpN,j 。
状态的初始化也很简单，另 dp0,0=1dp_{0, 0} = 1dp0,0 =1 ，表示一只乌龟都不放有一种摆放方案。
时间复杂度
通过观察上述代码，在枚举所有状态和转移状态的时候有三层循环，分别是枚举当前行、枚举当前行的合法摆放情况以及枚举上一行的摆放情况。因此总时间复杂度约为 O(n×2M×2M)=O(n×2M2)=O(n×4M)O(n \times 2^M \times 2^M) = O(n \times 2^{M^2}) = O(n \times 4^M)O(n×2M×2M)=O(n×2M2)=O(n×4M)。但由于合法的摆放数量远远少于 2M2^M2M，因此实际情况下程序运行的速度会快许多。
代码实现
本题的代码实现如下。在输出的时候需要减一，因为不放置也是一种合法情况，根据题目要求需要把这一合法情况排除。
本题的 Python 代码如下，Python 可以通过本题的所有测试点：
再提供一个暴力解法用于对拍：
