前置知识
- 状压 DP
- 矩阵乘法
Description
小 L 有一座环形花园，沿花园的顺时针方向，他把各个花圃编号为 \(1 \sim n\)。花园 \(1\) 和 \(n\) 是相邻的。
他的环形花园每天都会换一个新花样，但他的花园都不外乎一个规则：任意相邻 \(m\) 个花圃中都只有不超过 \(k\) 个 \(C\) 形的花圃，其余花圃均为 \(P\) 形的花圃。
例如，若 \(n=10\), \(m=5\), \(k=3\)，则
-
CCPCPPPPCC是一种不符合规则的花圃。 -
CCPPPPCPCP是一种符合规则的花圃。
请帮小 L 求出符合规则的花园种数对 \(10^9+7\) 取模的结果。
\(n \le 10^15, 2 \le m \le \min (n, 5), 1 \le k < m\)
Solution
这题的 \(80\%\) 数据加上 \(m \le 5\) 让你感觉很可以 DP，所以你考虑写部分分。
设 \(f_{i,j}\) 表示考虑到第 \(i\) 位，后 \(m-1\) 位的状态为 \(j\)。
\[f_{i,j} = \sum_k f_{i-1,k} \]可以枚举前一位的状态 \(k\) 来转移，实际只考虑新增一位对前面的影响，如果 \(g(k) < K\) 则可以转移。（其中 \(g(k)\) 表示 \(k\) 中 \(1\) 的个数，\(K\) 表示题目的限制）
因为要序列为环形，考虑 多次 DP 来消除影响。
每次以一个合法的 \(f_{m-1,i}\) 开始，一直 DP 到 \(f_{n+m-1,i}\)，用一个 \(ans\) 统计 \(f_{n+m-1,i}\) 的和即可。对应着与环上前 \(m-1\) 个位置的状态相同。
理论有 \(80pts\)，但我只得了 \(50pts\)，蛮怪的。
你发现每一次转移所枚举的状态都是相同的。
于是你考虑用矩阵加速转移。
初始化矩阵 \(base\)
如果 \(i\) 状态能向 \(j\) 状态转移，那么 \(base_{i,j} = 1\)
剩下的就是矩阵快速幂板子了。
计算贡献也可像上面的一样计算多次。但你发现他实际就是这个矩阵的对角线之和。
Code
状压 DP
/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl
using namespace std;
const int MAXN = 2e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;
int n, m, K, ans = 0;
int f[MAXN][20];
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}
void DP() {
for(int i = m; i <= n + m; ++i) {
for(int j = 0; j < (1 << m - 1); ++j) {
int cnt = 0;
for(int k = 1; k < m; ++k) if(j & (1 << k - 1)) cnt++;
f[i][j >> 1] = (f[i][j >> 1] + f[i - 1][j]) % mod;
if(cnt < K) f[i][(j >> 1) + (1 << m - 2)] = (f[i][(j >> 1) + (1 << m - 2)] + f[i - 1][j]) % mod;
}
}
}
signed main()
{
n = read(), m = read(), K = read();
for(int i = 0; i < (1 << m - 1); ++i) {
int cnt = 0;
for(int j = 1; j < m; ++j) {
if(i & (1 << j - 1)) cnt++;
}
if(cnt > K) continue;
memset(f, false, sizeof f);
f[m - 1][i] = (cnt <= K);
DP();
ans = ans + f[n + m - 1][i];
}
printf("%lld\n", ans);
return 0;
}
矩阵快速幂
/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl
using namespace std;
const int MAXN = 2e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;
int n, m, K, Ans = 0;
int f[MAXN][20];
struct Matrix {
int a[17][17];
Matrix () { memset(a, false, sizeof a); }
void Init() { memset(a, false, sizeof a); }
Matrix operator * (Matrix b) {
Matrix res;
for(int i = 0; i < (1 << m - 1); ++i)
for(int j = 0; j < (1 << m - 1); ++j)
for(int k = 0; k < (1 << m - 1); ++k)
res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % mod;
return res;
}
Matrix operator ^ (int p) {
Matrix res, x = *this;
for(int i = 0; i < (1 << m - 1); ++i) res.a[i][i] = 1;
while(p) {
if(p & 1) res = res * x;
x = x * x, p >>= 1;
}
return res;
}
}ans, base;
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}
signed main()
{
n = read(), m = read(), K = read();
for(int i = 0; i < (1 << m - 1); ++i) {
int cnt = 0;
for(int j = 1; j < m; ++j) if(i & (1 << j - 1)) cnt++;
base.a[i][i >> 1] = 1;
if(cnt < K) base.a[i][(i >> 1) + (1 << m - 2)] = 1;
}
base = base ^ n;
ans = ans * base;
for(int i = 0; i < (1 << m - 1); ++i) {
int cnt = 0;
for(int j = 1; j < m; ++j) if(i & (1 << j - 1)) cnt++;
if(cnt <= K) {
ans.Init();
ans.a[1][i] = 1;
ans = ans * base;
Ans = (Ans + ans.a[1][i]) % mod;
}
}
printf("%lld\n", Ans);
return 0;
}