前置知识
- 状压 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
", 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
", Ans);
return 0;
}