自动搬运

查看原文

来自洛谷，原作者为

	五更琉璃 琉璃想要变得可爱

搬运于2025-08-24 21:24:09，当前版本为作者最后更新于2019-11-08 10:45:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

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

$$00 \rightarrow \begin{cases} \_00 \\ \_01 \end{cases} $$$$01 \rightarrow \begin{cases} \_10 \end{cases}$$ $$10 \rightarrow \begin{cases} \_00 \\ \_01\end{cases} $$

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

$$i = \begin{cases} j >> 1 \\ (j >>1) \ | \ (1 << (m - 1)) \end{cases} $$

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

$$f[i][j] =f[i][j] + \begin{cases} f[i - 1][j>>1] \\ f[i - 1][(j >> 1) \ | \ (1 << ( m - 1) ) \end{cases} $$

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

然后要处理环形的问题，可以简单的短环成链，然后对于给定初状态 $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]$；得到方程：

$$\begin{cases} f'[00] = f[00] + f[10] \\ f'[01] = f[00] + f[10] \\ f'[10] = f[01] \\ f'[11] = 0 \end{cases} $$

构造出转移矩阵：

$$\begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} $$

对于任意的 $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;
}

$p.s.$ 前文 $f,i,j$ 重复使用的太多了，不要把意义混起来了。另代码中的 $i,j$ 和前面推矩阵时的 $i,j$ 时相反的。