刷题记录:牛客NC17890方格填色 [矩阵快速幂详解]

传送门:牛客

题目描述:

给一个m x n的方格，Applese想要给方格填上颜色，每个格子可以是黑色或者白色。他要求左右相邻两格不能
同为白色且相邻两列不能全为黑色。
输入:
3 5
输出:
1640

一道矩阵快速幂的好题

当时碰到这道题的时候是在状压dp的题单里碰到的,就…当时已经想出了应该使用递推的方式进行,递推的公式也不难推出,但是就是因为$n$是在是太大了,导致递推数组肯定开不下的,当时也没想到矩阵乘法,所以,就卡了很久

但是当你想到这道题应该是用矩阵快速幂的时候,就意味着你离解出这道题不久了

那么今天就以这道题来好好的复习一下矩阵快速幂

首先是矩阵,矩阵是什么呢,就是一个形同二维数组的数据的集合,如下图就是一个$3\ast 3$的矩阵

$\left\{\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\end{array}\right\}$

然后对于我们的矩阵乘法有以下的乘法准则:
两个大小分别为 $m\times n$ 和 $n\times p$ 的矩阵 $A,B$ 相乘的结果为一个大小为 $m\times p$ 的矩阵。将结果矩阵记作 $C$，则
$$c_{ij}=\sum _{k=1}^n{a}_{ik}{b}_{kj}\text{,(1≤i≤m, 1≤j≤p).}$$

而如果 $A$ 的列数与 $B$ 的行数不相等，则无法进行乘法。
可以验证，矩阵乘法满足结合律，即 $(AB)C=A(BC)$。
一个大小为 $n\times n$ 的矩阵 $A$ 可以与自身进行乘法，得到的仍是大小为 $n\times n$ 的矩阵，记作 $A^2=A\times A$。进一步地，还可以递归地定义任意高次方 $A^k=A\times A^{k-1}$，或称 $A^k=\underset{k\text{ 次}}{\underbrace{A\times A\times \cdots \times A}}$。

特殊地，定义 $A^0$ 为单位矩阵 $I=\left[\begin{array}{cccc}1& 0& \cdots & 0\\ 0& 1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 1\end{array}\right]$。

那么对于矩阵乘法来说,满足我们的快速幂性质,因为对于矩阵来说满足乘法结合律和加法结合律,也就是对于矩阵来说,我们是可以对此采用类快速幂计算的.

所以对于快速幂中的乘法,我们只要将两个矩阵按照上述的矩阵乘法法则进行即可

void juzhen_qpow(int k) {
	while(k) {
		if(k&1) ans_pow();
		x_pow();
		k>>=1;
	}
}

至此我们的矩阵快速幂部分结束

接下来是这道题的讲解.

对于本题来说,我们可以将黑色部分记为1,白色部分记为0,那么对于每一列来说我们就可以使用二进制来记录该列的状态

那么对于本题的限制来说就是相邻两类的状态$S_1$,$S_2$的,然后$S_1$$\mid$$S_2$的值为$(1<<m)-1$并且$S_1$,$S_2$不能都为$(1<<m)-1$.

然后呢,我们可以将$S_1,S_2$的状态都记为矩阵的形式

$\left\{\begin{array}{c}f[0][m]\\ f[1][m]\\ f[2][m]\\ f[3][m]\\ ...\end{array}\right\}$

然后我们找一下前后矩阵的关系,就会发现$S_1$矩阵显然可以经过一个01矩阵相乘得到$S_2$,因为对于每一个状态来说,前一种状态都可以或不可以转移到后一种状态,那么根据矩阵来说就是01矩阵的相乘.

举个栗子,当$n=2$时我们有以下的递推公式

$\left\{\begin{array}{c}f[0][m]\\ f[1][m]\\ f[2][m]\\ f[3][m]\end{array}\right\}$ $=$ $\left\{\begin{array}{cccc}0& 0& 0& 1\\ 0& 0& 1& 1\\ 0& 1& 0& 1\\ 1& 1& 1& 0\end{array}\right\}$ $\ast$ $\left\{\begin{array}{c}f[0][m-1]\\ f[1][m-1]\\ f[2][m-1]\\ f[3][m-1]\end{array}\right\}$

并且对于我们的第一列来说我们的所有的值都是1
$\left\{\begin{array}{c}f[0][0]\\ f[1][0]\\ f[2][0]\\ f[3][0]\end{array}\right\}$ $=$ $\left\{\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right\}$

那么对于第$n$列来说,我们最终的答案就是上述矩阵矩阵系数的$N$次方即可,就是一个等比数列,那么直接使用之前讲过的矩阵快速幂解决即可.

注意因为对于矩阵来说我们需要使用矩阵相乘才行,所以我们本来在快速幂中的$ans=1$,此时要换算成矩阵的形式,也就是之前讲过的单位矩阵就行

至此我们即解决了这道题

下面是具体的代码部分:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define int long long
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
const int mod=1e9+7;
int m,n;int a[1<<6][1<<6];int ans[1<<6][1<<6];int c[1<<6][1<<6];
void ans_pow() {
	for(int i=0;i<1<<m;i++) {
		for(int j=0;j<1<<m;j++) {
			c[i][j]=ans[i][j];
			ans[i][j]=0;
		}
	}
	for(int i=0;i<1<<m;i++) {
		for(int j=0;j<1<<m;j++) {
			for(int k=0;k<1<<m;k++) {
				ans[i][j]=(ans[i][j]+c[i][k]*a[k][j])%mod;
			}
		}
	}
}
void x_pow() {
	for(int i=0;i<1<<m;i++) {
		for(int j=0;j<1<<m;j++) {
			c[i][j]=a[i][j];
			a[i][j]=0;
		}
	}
	for(int i=0;i<1<<m;i++) {
		for(int j=0;j<1<<m;j++) {
			for(int k=0;k<1<<m;k++) {
				a[i][j]=(a[i][j]+c[i][k]*c[k][j])%mod;
			}
		}
	}
}
void juzhen_qpow(int k) {
	while(k) {
		if(k&1) ans_pow();
		x_pow();
		k>>=1;
	}
}
signed main() {
	m=read(),n=read();
	for(int i=0;i<1<<m;i++) {
		for(int j=0;j<1<<m;j++) {
			if((i|j)==(1<<m)-1&&!(i==(1<<m)-1&&j==(1<<m)-1)) {
				a[i][j]=1;
			}else {
				a[i][j]=0;
			}
		}
	}
	for(int i=0;i<1<<m;i++) {
		for(int j=0;j<1<<m;j++) {
			if(i==j) {
				ans[i][j]=1;
			}else {
				ans[i][j]=0;
			}
		}
	}
	juzhen_qpow(n-1);
	int Ans=0;
	for(int i=0;i<1<<m;i++) {
		for(int j=0;j<1<<m;j++) {
			Ans=(Ans+ans[i][j])%mod;
		}
	}
	cout<<Ans<<endl;
	return 0;
}