洛谷 P1357 花园

题意简述

一个只含字母C和P的环形串
求长度为n且每m个连续字符不含有超过k个C的方案数

题解思路

由于(m<=5)所以很显然状压
但由于(n<=10^{15})。可以考虑用矩阵加速
即设(a[i][j])表示是否能从(i)状态转向(j)状态
考虑到每种合法状态转移n次之后会变回原状态
所以(a^n)中主对角线上的元素之和就是答案

代码

#include <cstdio>
#include <cstring>
#define REP(i) for (register int i = 0; i < M; ++i)
typedef long long ll;
const int mod = 1000000007;
int m, k, M, x1, x2, ans;
ll n;
bool check[32];
inline void _add(int& x, const int& y) { x = (x + y) % mod; }
inline int calc(int x)
{
	int res = 0;
	for (; x; x &= x - 1) ++res;
	return res;
}
struct Matrix
{
	int a[32][32];
	Matrix() { memset(a, 0, sizeof(a)); }
	Matrix operator * (const Matrix &x) const
	{
		Matrix res;
		REP(i) REP(j) REP(k) _add(res.a[i][j], (ll)a[i][k] * x.a[k][j] % mod);
		return res;
	}
	Matrix operator ^ (ll x) const
	{
		Matrix res, r = *this;
		REP(i) res.a[i][i] = 1;
		for (; x; x >>= 1, r = r * r) if (x & 1) res = res * r;
		return res;
	}
}a;
int main()
{
	scanf("%lld%d%d", &n, &m, &k);
	M = 1 << m;
	REP(i) check[i] = (calc(i) <= k);
	REP(i) if (check[i])
	{
		x1 = (x2 = i >> 1) | (1 << (m - 1));
		a.a[i][x1] = (a.a[i][x2] = 1) * (check[x1]);
	}
	a = a ^ n;
	REP(i) _add(ans, a.a[i][i] * check[i]);
	printf("%d
", ans);
}