自动搬运

查看原文

来自洛谷，原作者为

	yanqijin **

搬运于2025-08-24 22:08:46，当前版本为作者最后更新于2024-04-07 13:06:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

有一个 $N \times M$ 的地板，可以铺上一些黑白的砖，要求每个 $2 \times 2$ 的区域里，颜色不能完全一样，问有多少种方案($N \le 10^{100}$ $M \le 5$)。

思路

首先看到 $M$ 这么小，还要统计方案数，容易想到暴力 状压，枚举 $i(i \le n)$，$j(j \le 2^m-1)$，则 $f_{i,j} =\sum_{s=1}^{2^m-1}f_{i-1,s}[s\text{和}j\text{合法}]$。但是 $N \le 10^{100}$，这么大的数据范围，普通的状压承受不了，所以要用 矩阵快速幂 优化。

式子 $[f_{1,0},f_{1,1},f_{1,2}\dots f_{1,2^m-2},f_{1,2^m-1}]\times C^{n-1}=[f_{n,0},f_{n,1},f_{n,2}\ldots f_{n,2^m-2},f_{n,2^m-1}]$。其中矩阵 $C$ 中，若 $S'\to S$ 合法，则 $C_{S',S}=1$，否则 $C_{S',S}=0$。

时间复杂度 $O(2^{3m}\log n)$。

(记得高精度)。

$Code$

#include<cstdio>
using namespace std;
int n[105],m,p,c[32][32],x[32][32],ans[32],z=0,cnt;//高精度
void read(int &x) {//快读
	x=0;
	char ch=0;
	while(ch<'0'||ch>'9') {
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=(x<<3)+(x<<1)+ch-48;
		ch=getchar();
	}
}
void write(int x) {//快输
	if(x<0) putchar('-'),x=-x;
	int sta[100];
	int top=0;
	do {
		sta[top++]=x%10,x/=10;
	} while(x);
	while(top) putchar(sta[--top]+48);
	putchar('\n');
}
void cheng() {
	if(z==0) {
		for(int j=0; j<(1<<m); j++) {
			for(int j1=0; j1<(1<<m); j1++) {
				c[j][j1]=x[j][j1];
			}
		}
		z=1;
		return ;
	}
	int q[32][32];
	for(int j=0; j<(1<<m); j++) {
		for(int j1=0; j1<(1<<m); j1++) {
			q[j][j1]=c[j][j1];
			c[j][j1]=0;
		}
	}
	for(int j=0; j<(1<<m); j++) {
		for(int j1=0; j1<(1<<m); j1++) {
			for(int k=0; k<(1<<m); k++) {
				c[j][j1]=(c[j][j1]+q[j][k]*x[k][j1])%p;
			}
		}
	}
}
void cheng1() {
	int q[32][32],s[32][32];
	for(int j=0; j<(1<<m); j++) {
		for(int j1=0; j1<(1<<m); j1++) {
			q[j][j1]=x[j][j1];
			s[j][j1]=x[j][j1];
			x[j][j1]=0;
		}
	}
	for(int j=0; j<(1<<m); j++) {
		for(int j1=0; j1<(1<<m); j1++) {
			for(int k=0; k<(1<<m); k++) {
				x[j][j1]=(x[j][j1]+q[j][k]*s[k][j1])%p;
			}
		}
	}
}
void qpow() {//矩阵快速幂
	while(cnt) {
		if(n[1]&1) {
			cheng();
		}
		cheng1();
		long long s=0,d=cnt;
		for(int i=cnt; i>=1; i--) {
			n[i]+=s*10;
			s=n[i]&1;
			n[i]>>=1;
		}
		cnt=0;
		for(int i=1; i<=d; i++) {
			if(n[i]) cnt=i;
		}
	}
}
int main() {
	char ch=0;
	while(ch<'0'||ch>'9') {
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		n[++cnt]=ch-48;
		ch=getchar();
	}
	int h[105];
	for(int j=1; j<=cnt; j++) h[j]=n[j];
	for(int j=1; j<=cnt; j++) n[j]=h[cnt-j+1];
	read(m);
	read(p);
	if(p==1) {
		write(0);
		return 0;
	}
	for(int j=0; j<(1<<m); j++) {
		for(int j1=0; j1<(1<<m); j1++) {
			int a=j,d=j1;
			bool q=1;
			for(int s=1; s<m; s++) {
				if((a&1)==(d&1) and ((a>>1)&1)==((d>>1)&1) and (a&1)==((a>>1)&1)) q=0;
				a>>=1;
				d>>=1;
			}
			if(q) {
				x[j][j1]=1;
			}
		}
	}
	n[1]--;
	int v=1;
	while(n[v]<0) {
		n[v]+=10;
		n[v+1]--;
		v++;
	}
	qpow();
	for(int j1=0; j1<(1<<m); j1++) {
		for(int k=0; k<(1<<m); k++) {
			ans[j1]+=c[k][j1];
		}
	}
	int sum=0;
	for(int i=0; i<1<<m; i++) {
		sum=(sum+ans[i])%p;
	}
	write(sum);//输出
	return 0;
}