问题分析

有一个 $n$ 行 $m$ 列的棋盘，要摆放特殊的棋子。每个棋子的攻击范围由 $3 \times p$ 的模板给出，棋子位于模板的第一行第 $k$ 列。要求找出在棋子互不攻击的前提下，摆放棋子的方案数，结果对 $2^{32}$ 取模。

关键观察

攻击范围特性：每个棋子的攻击范围跨越 $3$ 行，因此当前行的摆放状态会受到前两行的影响

数据范围：$m \leq 10$，可以使用状态压缩 DP

矩阵快速幂：由于 $n$ 可达 $10^6$，需要优化状态转移

算法思路

1.状态表示

用二进制状态 $s$ 表示一行的棋子摆放情况，其中第 $i$ 位为 $1$ 表示该位置有棋子。状态总数最多为 $2^m = 1024$。

2.状态预处理

函数 chk1(s)：检查单行状态 $s$ 是否合法

确保同一行内棋子不互相攻击（根据模板的第一行）

对于 $s$ 中的每个棋子，检查其攻击范围内是否有其他棋子

函数 chk2(sta, s1, s2)：检查两行状态 $s1$ 和 $s2$ 是否兼容

确保 $s1$ 中的棋子不会攻击到 $s2$ 中的棋子

使用模板的不同行来处理不同行间的攻击关系

3.矩阵快速幂优化

将状态转移表示为矩阵乘法：

矩阵 $base$ 的大小为 $B \times B$，其中 $B = 2^m$

$base[s2][s1] = 1$ 表示可以从状态 $s1$ 转移到状态 $s2$

初始向量 $ans$ 表示第一行的所有合法状态

状态转移方程：

$$dp[i][s] = \sum_{s' \text{ 与 } s \text{ 兼容}} dp[i-1][s'] $$

使用矩阵快速幂在 $O(B^3 \log n)$ 时间内计算 $dp[n]$。

复杂度分析

状态数：最多 $2^m = 1024$ 个状态

矩阵乘法：$O(B^3) = O(2^{3m}) = O(2^{30})$，但实际合法状态数远少于 $2^m$

总复杂度：$O(|v|^3 \log n)$，其中 $|v|$ 是合法状态数

总结

本题通过以下技巧高效解决问题：

1.状态压缩：利用 $m$ 较小的特点，用二进制表示状态

2.矩阵快速幂：将递推关系转化为矩阵乘法，处理大的 $n$

3.攻击范围处理：通过模板位移来检查棋子间的攻击关系