题目链接：Luogu 1357

小 L 有一座环形花园，沿花园的顺时针方向，他把各个花圃编号为 $1$ 到 $n$。他的环形花园每天都会换一个新花样，但他的花园都不外乎一个规则，任意相邻 $m$ 个花圃中有不超过 $k$ 个 $C$ 形的花圃，其余花圃均为 $P$ 形的花圃。

请帮小 L 求出符合规则的花园种数，答案对 $10 ^ 9 + 7$ 取模。

数据范围：$2\le n\le 10 ^ {15}$，$2\le m\le 5$，$1\le k<m$。

Solution

由于花园是一个环形的，我们考虑能够回到初始状态的方案数。设初始状态为 $S$，则进行 $n$ 次转移，对答案的贡献为最终状态依旧是 $S$ 的方案数。

很显然这个东西是可以矩阵快速幂优化的。记转移矩阵的 $n$ 次幂为 $A$；设一个合法的初始状态为 $S$，那么对答案的贡献就是 $A_{S,S}$（显然 $A$ 左乘一个长度为 $n$、只有第 $S$ 个数为 $1$ 的列向量后，得到的矩阵第 $(S,S)$ 个值就是 $A_{S,S}$）。

时间复杂度：$\mathcal O(8^m\log n)$。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 35;
const int mod = 1e9 + 7;

long long n;
int m, k, msk;
bool ok[N];

void add(int &x, int y) {
    (x += y) >= mod && (x -= mod);
}

struct Matrix {
    int n, A[N][N];
    Matrix(int _n = 0) {
        n = _n, memset(A, 0, sizeof(A));
    }
    void operator~() {
        for (int i = 0; i < n; i++) A[i][i] = 1;
    }
    Matrix operator*(const Matrix &b) const {
        Matrix ret(n);
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int k = 0; k < n; k++) {
            add(ret.A[i][k], 1LL * A[i][j] * b.A[j][k] % mod);
        }
        return ret;
    }
    Matrix operator^(long long p) const {
        Matrix ret(n), x = *this;
        ~ret;
        for (; p; p >>= 1, x = x * x) {
            if (p & 1) ret = ret * x;
        }
        return ret;
    }
};

void init() {
    for (int i = 0; i < msk; i++) {
        int cnt = 0;
        for (int j = 0; j < m; j++) {
            cnt += (i >> j) & 1;
        }
        ok[i] = (cnt <= k);
    }
}
Matrix calc() {
    Matrix a(msk);
    for (int i = 0; i < msk; i++) {
        int j = i >> 1;
        a.A[j][i] = (ok[i] && ok[j]);
        j = (i >> 1) + (1 << (m - 1));
        a.A[j][i] = (ok[i] && ok[j]);
    }
    return a;
}
int main() {
    scanf("%lld%d%d", &n, &m, &k);
    msk = 1 << m;
    init();
    Matrix x = calc() ^ n;
    int ans = 0;
    for (int i = 0; i < msk; i++) {
        if (ok[i]) add(ans, x.A[i][i]);
    }
    printf("%d\n", ans);
    return 0;
}