洛谷1357 花园

原题链接

可以使用二进制来表示后\(m\)个花圃的状态。
设\(f[i][k]\)表示前\(i\)个花圃，后\(m\)个状态为\(k\)，设\(k\)可由\(k ^ \prime\)转移来，则有状态转移方程：

\(\qquad\qquad f[i][k] = \sum f[i][k ^ \prime]\)

发现这个转移方程可以用矩阵乘法来优化，直接将矩阵中\((k ^ \prime, k)\)定为\(1\)即可。
因为\(1 \sim m\)的花圃可以看成\(n + 1 \sim n + m +1\)，所以原来的状态转移方程需要转移\(n\)次，即该矩阵的\(n\)次方即是最终目标矩阵。
最后的答案即为矩阵中对角线上合法状态的值的和，因为花园是一个环最后\(m\)个花圃的状态和最初的必须一样。
合法状态的转移其实就是对转移后的状态右移一位，最左位添\(1\)或\(0\)的合法状态即为转移前的状态。
这里我使用\(DFS\)来预处理。

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int N =35;
const int mod = 1e9 + 7;
int L, m, k;
ll n;
bool v[N];
struct sq{
    int a[N][N];
    sq() { memset(a, 0, sizeof(a)); }
    sq operator * (const sq &b) const
    {
        int i, j, k;
        sq c;
        for (i = 0; i <= L; i++)
            for (j = 0; j <= L; j++)
                for (k = 0; k <= L; k++)
                    c.a[i][j] = (1LL * a[i][k] * b.a[k][j] % mod + c.a[i][j]) % mod;
        return c;
    }
};
sq A, an;
void dfs(int x, int nw, int da)
{
    if (!(x ^ m))
    {
        v[da] = 1;
        int ne = da >> 1;
        A.a[ne][da] = 1;
        if (nw ^ k || da & 1)
            A.a[ne | (1 << (m - 1))][da] = 1;
        return;
    }
    dfs(x + 1, nw, da);
    if (nw < k)
        dfs(x + 1, nw + 1, da | (1 << x));
}
void ksm()
{
    an = A;
    if (!n)
        return;
    for (n--; n; n >>= 1, A = A * A)
        if (n & 1)
            an = an * A;
}
int main()
{
    int i, s = 0;
    scanf("%lld%d%d", &n, &m, &k);
    L = (1 << m) - 1;
    dfs(0, 0, 0);
    ksm();
    for (i = 0; i <= L; i++)
        if (v[i])
            s = (1LL * s + an.a[i][i]) % mod;
    printf("%d", s);
    return 0;
}

洛谷1357 花园

原文：https://www.cnblogs.com/Iowa-Battleship/p/9865622.html