题目
题目描述
给一个m x n的方格，Applese想要给方格填上颜色，每个格子可以是黑色或者白色。他要求左右相邻两格不能同为白色且相邻两列不能全为黑色。
求满足条件的方案数。
输入描述
输入两个整数m, n。\((1 ≤ m ≤ 5, 1 ≤ n ≤ 10^{18})\)。
输出描述
输出答案对 \(10^9 + 7\) 取模的结果。
**示例1 **
输入
3 1
输出
8
示例2
输入
3 5
输出
1640
示例3
输入
5 5
输出
351032
题解
知识点：状压dp，矩阵快速幂。
注意到可以一列一列摆，设 \(0\) 代表黑色，\(1\) 代表白色，这样比反过来方便。设第 \(i\) 列状态为 \(st1\) ，第 \(i-1\) 列状态为 \(st2\) ，于是首先 \(st1\) 和 \(st2\) 自己都要满足 st & (st<<1) 不能为 \(1\) ，即相邻不为白色，随后 st1 & st2 必须大于 \(0\) ，即两列不能都为黑色。设 \(dp[i][st]\) 表示摆到第 \(i\) 列，状态 \(st\) 时的方案数，有转移方程：
注意到 \(n\) 十分的大，考虑优化。发现转移方程只和这一列的 \(st1\) 和上一列的 \(st2\) 有关，并且对于一组 \((st1,st2)\) 能否转移是不随 \(i\) 变化的，因此我们可以预先确定每一组 \((st1,st2)\) 是否可以从 \(st2\) 转移到 \(st1\)。显然，用矩阵快速幂，可以解决这个问题了。假设 $f(i,j) $ ，表示状态 \((i,j)\) 是否可以转移，用 \(01\) 表示，于是 \(f(i,j) = !(i \& j) \and (i | j)\)。矩阵构造如下：
\[\left ( \begin{array}{c} dp[n][0]\\ dp[n][1]\\ \vdots\\ dp[n][2^m-1] \end{array} \right) = \left ( \begin{array}{c} f(0,0) & f(1,0) & \cdots & f(2^m-1,0)\\ f(0,1) & f(1,1) & \cdots & f(2^m-1,1)\\ \vdots & \vdots & \ddots & \vdots\\ f(0,2^m-1) & f(1,2^m-1) & \cdots & f(2^m-1,2^m-1) \end{array} \right) ^{n-1} \left ( \begin{array}{c} dp[1][0]\\ dp[1][1]\\ \vdots\\ dp[1][2^m-1] \end{array} \right) \]时间复杂度 \(O(8^m \log n)\)
空间复杂度 \(O(4^m)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
///矩阵快速幂取余，O(n^3logk)
struct Matrix {
int n, m;//不能const，快速幂要复制
vector<vector<ll>> mat;
explicit Matrix(int _n) :n(_n), m(_n), mat(_n + 1, vector<ll>(_n + 1)) {
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
mat[i][j] = i == j;
}//初始化n阶单位矩阵，explicit防止误用类型转换
Matrix(int _n, int _m) :n(_n), m(_m), mat(_n + 1, vector<ll>(_m + 1)) {}//初始化nxm零矩阵
friend Matrix operator*(const Matrix &A, const Matrix &B) {
Matrix ans(A.n, B.m);
if (A.m != B.n) return ans;
for (int i = 1;i <= A.n;i++)
for (int j = 1;j <= B.m;j++)
for (int k = 1;k <= A.m;k++) //a.m == b.n
ans.mat[i][j] = (ans.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % mod;
return ans;
}//矩阵乘法取余
friend Matrix operator^(Matrix A, ll k) {
Matrix ans(A.n);//A必须是方阵
while (k) {
if (k & 1) ans = ans * A;
k >>= 1;
A = A * A;
}
return ans;
}//快速幂取余
void output() const {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
cout << mat[i][j] << ' ';
cout << '\n';
}
cout << '\n';
}//输出检测
};
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll m, n;
cin >> m >> n;
Matrix init(1 << m, 1);
for (int i = 1;i <= (1 << m);i++)
init.mat[i][1] = 1;
Matrix feat(1 << m, 1 << m);
for (int i = 0;i < (1 << m);i++)
for (int j = 0;j < (1 << m);j++)
feat.mat[i + 1][j + 1] = !(i & j) && (i | j);
Matrix res = (feat ^ (n - 1)) * init;
int ans = 0;
for (int i = 1;i <= (1 << m);i++) ans = (ans + res.mat[i][1]) % mod;
cout << ans << '\n';
return 0;
}