洛谷 P1357 花园

题目传送门

暴力

思路

状态设计

设 $d{p}_{i,j}$ 表示目前放到第 $i$ 个花圃，且最近 $m$ 个花圃的状态是 $j$（$C$ 形花圃用 $1$，$P$ 形花圃用 $0$ 表示）的方案数。

状态转移

当前状态为 $j$ 时，上一个状态就是 $j>>1$ 或 $(j>>1)|(1<<(m-1))$。
因为当上一个状态转移到当前状态时，它会左移一位，并且挤掉最左边一位的状态。那么上一个状态的最左边的那一位就有 $0/1$ 两种可能。
转移时再判断上一个状态是否合法，即 $1$ 的个数是否不超过 $k$ 个。

边界条件

由于它是一个环形花园，因此我们要枚举最初始 $m$ 个花圃的状态。假设其状态为 $start$，那么边界就是 $d{p}_{m,start}=1$。

答案统计

还是因为它是圆形花园，所以当初始 $m$ 个花圃的状态固定时，它的贡献就是 $d{p}_{n+m,start}$（相当于转一圈转回来了），将其累加即可。

时间复杂度

$O(n\times 2^{2m})$，可以通过 $n\le 10^5$ 的数据。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 7;
const int maxs = (1 << 5) + 7;
const int mod  = 1e9 + 7;

ll n;
int m, k, ms;
bool vis[maxs];
int dp[maxn][maxs], ans;
int main() {
	scanf("%lld%d%d", &n, &m, &k);
	ms = (1 << m) - 1;
	for (int st = 0; st <= ms; ++st) {  // 枚举最初始 m 个的状态
		// __builtin_popcount 用来得到 st 的二进制中 1 的个数
		if (__builtin_popcount(st) > k) continue;  
		memset(dp, 0, sizeof(dp));
		
		// 由于初始时 dp[m][st] = 1, 最后统计也是 dp[n + m][st]
		// 所以直接将整个数组向左平移 m 个位置 
		dp[0][st] = 1;  
		for (int i = 1; i <= n; ++i) {
			for (int s = 0; s <= ms; ++s) {
				if (__builtin_popcount(s) > k) continue;
				
				int pre1 = (s >> 1), pre2 = (s >> 1) | (1 << (m - 1));
				if (__builtin_popcount(pre1) <= k)
					dp[i][s] = (dp[i][s] + dp[i - 1][pre1]) % mod;
				if (__builtin_popcount(pre2) <= k)
					dp[i][s] = (dp[i][s] + dp[i - 1][pre2]) % mod;
			}
		}
		ans = (ans + dp[n][st]) % mod;
	}
	printf("%d\n", ans);
	return 0;
} 

优化

$100\%$ 的数据范围时是 $n\le 10^{15}$，肯定需要 $O(log(n))$ 级别的算法。
这又是在转移方面优化，所以可以想到用矩阵快速幂转移。

假设我们用 $tran{s}_{j,k}$ 表示状态 $j$ 是否可以转移到状态 $k$（就是转移矩阵），那么转移方程就可以转换为：
$$d{p}_{i,j}=\sum _{k=0}^{2^m-1}d{p}_{i-1,k}\times tran{s}_{k,j}$$
又发现当前行状态只与上一行状态有关，所以这就相当于 $d{p}_i=d{p}_{i-1}\times trans$。
更进一步地，$d{p}_n=d{p}_0\times tran{s}^n$。
因此先计算好转移矩阵的 $n$ 次方后，再乘以初始状态矩阵就好了。

时间复杂度

$O(log(n)\times 2^{3m})$

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 7;
const int maxs = (1 << 5) + 7;
const int mod  = 1e9 + 7;

ll n;
int m, k, ms;
int ans;
struct matrix {
	int a[maxs][maxs];
	void init() {memset(a, 0, sizeof(a));}
	matrix operator * (const matrix& x) const {
		matrix res; res.init();
		for (int i = 0; i <= ms; ++i)
			for (int j = 0; j <= ms; ++j)
				for (int k = 0; k <= ms; ++k)
					res.a[i][j] = (res.a[i][j] + 1ll * a[i][k] * x.a[k][j] % mod) % mod;
		return res;
	} 
} trans;
matrix qpow(matrix x, ll y) {
	matrix res; res.init();
	for (int i = 0; i <= ms; ++i)
		res.a[i][i] = 1;
	for (; y; y >>= 1, x = x * x)
		if (y & 1) res = res * x;
	return res;
}
int main() {
	scanf("%lld%d%d", &n, &m, &k);
	ms = (1 << m) - 1;
	for (int s = 0; s <= ms; ++s) {
		if (__builtin_popcount(s) > k) continue;
		int pre1 = (s >> 1), pre2 = (s >> 1) | (1 << (m - 1));
		if (__builtin_popcount(pre1) <= k)
			trans.a[pre1][s] = 1;
		if (__builtin_popcount(pre2) <= k)
			trans.a[pre2][s] = 1;
	}
	trans = qpow(trans, n);
	for (int s = 0; s <= ms; ++s) {
		if (__builtin_popcount(s) > k) continue;
		matrix dp; dp.init(), dp.a[0][s] = 1;
		dp = dp * trans;
		ans = (ans + dp.a[0][s]) % mod;
	}
	printf("%d\n", ans);
	return 0;
}