矩阵快速幂与环形状压 DP：洛谷 P1357 花园 详解
题目简述：有一个周长为 N 的环形花园，每个位置可以种 'C' 或 'P' 两种花。要求任意连续的 M 个位置中，'C' 的数量不能超过 K 个。求合法的种植方案数，对 10^9 + 7 取模。 数据范围：4 \leq N \leq 10^{15}，2 \leq M \leq 5，1 \leq K \leq M。
一、 算法嗅觉：如何一眼看透这道题？
当我们在考场上看到这组数据范围时，应该立刻触发两个条件反射：
- M 极小：任意时刻只需要关注连续的 M 个位置，暗示这一定是一个 状态压缩 DP，总状态数最多只有 2^M 种！
- N 极大：要求 O(N) 的递推是绝对不可能的，必须用 O(\log N) 的算法。再结合 DP 的线性递推性质，这一定是 矩阵快速幂 的绝对领域！
二、 核心推导：降维打击三步曲
第一步：状态定义 (State Representation)
我们把连续的 M 个花圃看作一个滑动窗口。规定种 'C' 为 1，种 'P' 为 0。 那么长度为 M 的窗口可以用一个 M 位的整数 S 来表示。
- 合法状态的约束：只有当二进制数 S 中
1的个数不超过 K 时，这个状态才是合法的。我们可以使用 GCC 内置函数__builtin_popcount(S) <= K瞬间完成判定。
第二步：状态转移 (Transition Matrix)
假设当前窗口的状态是 S（代表第 i 到 i+M-1 个花圃）。我们现在要种第 i+M 个花圃。 随着窗口向右滑动一格，最左边（最老）的花会被挤出窗口，最右边（最新）的花会进入窗口。
这在位运算中如何表现？
- 左移腾出空位：
S << 1 - 种下新的花：种 'P' 就是末尾加 0，种 'C' 就是末尾加 1（即
| 1）。 - 截断保持长度：只保留低 M 位，即
& ((1 << M) - 1)。
如果旧状态 S 和生成的新状态 S' 都是合法的（1 的个数都 \leq K），那么这就是一次合法的转移，我们在邻接矩阵中记作：T[S][S'] = 1。
第三步：环形约束与“矩阵的迹 (Trace)”
普通的矩阵快速幂通常是求起点到一个特定终点的路径数，但这道题是环形的！
这意味着什么？ 想象我们在环上随机选一段长度为 M 的起始状态 S。我们绕着花园走一圈，发生 N 次转移后，由于是环，最后这 M 盆花必须严丝合缝地变回状态 S！
在矩阵乘法中，设转移矩阵为 T：
- (T^N)[S][S] 的物理意义：从状态 S 出发，经过 N 步转移，最终又回到状态 S 的方案数。
因此，所有合法的环形花园总数，就是枚举所有合法的起始状态 S，把它们绕一圈回到自己的方案数全部加起来：
在线性代数中，矩阵主对角线元素之和被称为“矩阵的迹 (Trace)”。 这道题的终极答案，就是转移矩阵 T 的 N 次方的迹！
三、 C++ 极简最优解代码
书上的预处理逻辑使用递归 DFS 构建矩阵，显得有些繁琐。由于 M \leq 5，我们直接用两个 for 循环和几行位运算，就能极其清晰地把状态转移矩阵构建出来。
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1000000007;
// 定义矩阵结构体，封装矩阵乘法
struct Matrix {
int size;
long long mat[35][35]; // M<=5，状态最多32个
// 构造函数：初始化为全0矩阵
Matrix(int s) : size(s) {
for (int i = 0; i < size; ++i)
for (int j = 0; j < size; ++j)
mat[i][j] = 0;
}
// 设置为单位矩阵 (主对角线为1，其余为0)
void setIdentity() {
for (int i = 0; i < size; ++i)
mat[i][i] = 1;
}
// 重载乘号，实现矩阵乘法
Matrix operator*(const Matrix& other) const {
Matrix res(size);
for (int i = 0; i < size; ++i) {
for (int k = 0; k < size; ++k) {
if (mat[i][k] == 0) continue; // 常数级优化
for (int j = 0; j < size; ++j) {
res.mat[i][j] = (res.mat[i][j] + mat[i][k] * other.mat[k][j]) % MOD;
}
}
}
return res;
}
};
// 矩阵快速幂：求 base 的 exp 次方
Matrix power(Matrix base, long long exp) {
Matrix res(base.size);
res.setIdentity(); // 答案矩阵初始为单位矩阵
while (exp > 0) {
if (exp & 1) res = res * base;
base = base * base;
exp >>= 1;
}
return res;
}
int main() {
// 优化输入输出流
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long n;
int m, k;
if (!(cin >> n >> m >> k)) return 0;
int maxS = 1 << m; // 状态总数为 2^m
int mask = maxS - 1; // 用于截断高位，保留最低的 m 位
Matrix A(maxS);
// 【核心一】构建一次转移矩阵 A
for (int S = 0; S < maxS; ++S) {
// 如果当前状态 S 不合法（'C' 的数量超过 k），直接跳过
if (__builtin_popcount(S) > k) continue;
// 尝试种一盆 'P' (即在末尾加 0)
int next0 = (S << 1) & mask;
if (__builtin_popcount(next0) <= k) {
A.mat[S][next0] = 1; // 转移合法，标记为 1
}
// 尝试种一盆 'C' (即在末尾加 1)
int next1 = ((S << 1) | 1) & mask;
if (__builtin_popcount(next1) <= k) {
A.mat[S][next1] = 1; // 转移合法，标记为 1
}
}
// 【核心二】计算矩阵 A 的 n 次方
Matrix An = power(A, n);
// 【核心三】由于是环形，起始状态必须等于最终状态
// 我们将所有合法状态 S 的 An[S][S] (即主对角线元素) 加起来，这就是答案
long long total_valid_gardens = 0;
for (int S = 0; S < maxS; ++S) {
if (__builtin_popcount(S) <= k) {
total_valid_gardens = (total_valid_gardens + An.mat[S][S]) % MOD;
}
}
cout << total_valid_gardens << "\n";
return 0;
}