题解 P1357 花园

五更琉璃 · 2019-11-08 10:45:08 · 题解

先考虑普通的DP，因为 m \leq 5，可以状压。

从第二个样例来看，m=2,k=1，有状态

可以知道前状态的最右几位要和后状态相同，不过最前面的一位被挤出去了，有没有摆C花没有关系， 01 皆可，因此设前状态为 i，后状态为 j，可以得到 i,j 关系：

另设 f[i][j] 为到第 i 盆花，前面 m 盆的状态为 j，可以由上面的关系得到DP方程：

需要判一下第二个转移的前状态是否合法。

然后要处理环形的问题，可以简单的短环成链，然后对于给定初状态 f[0][s] ，统计DP后的 f[n][s] 计入答案。这是因为这样对于一个长度为 n 的环， i=0 和 i=n 是等价的，所以 j_0,j_n 相同的时候就是一个合法的环。

依照这个思路写出40分代码:

#include <bits/stdc++.h>

int f[100000][1 << 5];
int n, m, K;
int t, ans;
int main() {
    n = read(); m = read(); K = read();
    t = (1 << m) - 1;
    for (int statu = 0; statu <= t; ++statu) {
        if (__builtin_popcount(statu) > K) continue;
        memset(f, 0, sizeof(f));
        f[0][statu] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= t; ++j) {
                f[i][j] += f[i - 1][j >> 1];
                if (__builtin_popcount((j >> 1) | (1 << (m - 1))) <= K)
                    f[i][j] += f[i - 1][(j >> 1) | (1 << (m - 1))];
            }
        }
        ans += f[n][statu];
    }

    printf("%d\n", ans);
    return 0;
}
\\ 不知道__builtin_popcount() 的可以自行百度，这是好东西

然后想着 f[i][j] 只和 f[i - 1][k] 有关，所以第一维 [i] 可以滚动优化掉，然后按照这个 n 的范围肯定是得上矩阵乘法的，试着构造转移矩阵。还是以上面的 m=2,k=1 为例，状态转移还是一样的，设 f[i] 为状态为 i 时的方案数， 由 f[i] 推出 f'[i] ，就是下一轮的 f[i]；得到方程：

构造出转移矩阵：

对于任意的 m,k，也可以通过前后 i,j 两个状态的关系，令转移矩阵中的 mat[i][j] = 1，构造出转移矩阵。

另外还有一点，对于之前每一个状态做一遍DP，现在我们有了矩阵，就没有必要对于 f[0][0] = 1, f[0][1] = 1, \ldots ,f[0][(1 << m) - 1] 各做一次的必要了，可以把初始矩阵的第一维利用起来，即令 f[0][0] = 1,f[1][1]=1, \ldots ,f[i][i] = 1 可以让每一种初状态并行处理，每一行中就是我们要的初状态只有一种的一轮DP。然而根据矩阵乘法的性质，这个矩阵乘上任意矩阵都等于所乘的矩阵，也就是说是一个单位矩阵，所以乘不乘没差，那么我们所求的答案就是转移矩阵自乘之后 \sum_{i=0}^{2^m - 1} mat[i][i]。

AC代码：

#include <bits/stdc++.h>
typedef long long lint;

inline lint read() {
    lint x = 0, f = 0; char c = getchar();
    for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = 1;
    for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
    return f ? -x : x;
}

const int p = 1e9 + 7;
lint n;
int m, K;
int t, ans;

struct mat {
    int row, col;
    int a[32][32];
    mat() {
        memset(a, 0, sizeof(a));
    }
    void init() {
        *this = mat();
        row = col = t;
        for (int i = 0; i < t; ++i)
            a[i][i] = 1;
    }
    mat operator * (const mat &x) const {
        mat ans = mat(); ans.row = row; ans.col = col;
        for (int i = 0; i < row; ++i) 
            for (int j = 0; j < col; ++j)
                for (int k = 0; k < col; ++k)
                    (ans.a[i][j] += (1ll * a[i][k] * x.a[k][j]) % p) %= p;
        return ans;
    }
    mat operator ^ (lint n) {
        mat ans = mat(); 
        ans.init();
        mat base = *this;
        for (; n; n >>= 1, base = base * base)
            if (n & 1) ans = ans * base;
        return ans;
    }
} ;

int main() {
    n = read(); m = read(); K = read();
    t = 1 << m;
    mat b = mat(); b.row = b.col = t;
    for (int i = 0, j; i < t; ++i) {
        if (__builtin_popcount(i) > K) continue;
        j = i >> 1;
        // j -> i
        b.a[j][i] = 1;
        j = (i >> 1) | (1 << (m - 1));
        if (__builtin_popcount(j) <= K)
            b.a[j][i] = 1;
    }

    mat c = (b ^ n);
    for (int i = 0; i < t; ++i) {
        ans = (ans + c.a[i][i]) % p;
    }
    printf("%d\n", ans);
    return 0;
}