自动搬运

查看原文

来自洛谷，原作者为

	学无止境 冲冲冲!

搬运于2025-08-24 22:06:41，当前版本为作者最后更新于2018-12-01 22:58:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本题数据规模较大，容易看出这是一道数学题，有一个坑点，就是格点与格子并不是一个东西，有没有掉坑呢 $QwQ$

然后就是对本题的解决了

首先我们可以发现每一行是独立的，所以只需要处理一行的答案即可

设 $F[i][0]$ 表示一行中摆了 $i$ 个位置且第 $i$ 个位置不摆放棋子的方案数

设 $F[i][1]$ 表示一行中摆了 $i$ 个位置且第 $i$ 个位置摆放棋子的方案数

设 $Ans[i]$ 表示 $F[i][0]+F[i][1]$

那么忽略第二个限制可以发现有:

$F[i][0]=F[i-1][0]+F[i-1][1]$

$F[i][1]=F[i-1][0]$

所以有

$Ans[i]$

$=F[i][0]+F[i][1]$

$=2F[i-1][0]+F[i-1][1]$

$=(F[i-1][0]+F[i-1][1])+(F[i-2][0]+F[i-2][1])$

$=Ans[i-1]+Ans[i-2]$

初始条件：$Ans[1]=2,Ans[2]=3$

可以发现这就是 $Fibonacci$ 数列：$Ans[i]=Fib[i+2]$

接着进行拓展，由于存在第二个限制，仅仅摆了一个棋子的方案以及没有棋子的方案不合法，需要减去 $(i+1)$

所以最终答案是 $Fib[N+3]-N-2$ $(N$即是题目中的含义$)$

接着便可以使用矩阵快速幂在 $O(log_2N)$ 的时间复杂度内求出答案

最后再使用快速幂算出整个棋盘的方案数就好啦

$Code:$

#include<iostream>
#include<cstdio>
#include<cstring> 
using namespace std;
struct Martrix
{
	long long f[2][2];
}ans,mat;
long long n,p,temp[2][2];
inline long long multiply(long long a,long long b)
{
	long long x=a,y=b,tmp=0;
	while(y)
	{
		if(y&1)
			tmp=(tmp+x)%p;
		x=(x*2)%p;
		y>>=1;
	}
	return tmp;
}

long long qpow(long long a,long long b)
{
	long long tmp=1;
	while(b)
	{
        if(b&1)
			tmp=multiply(tmp,a);
        a=multiply(a,a);
		b>>=1;
    }
    return tmp;
}

void mat_mul(Martrix &q,Martrix &w)
{
	memset(temp,0,sizeof(temp));
	for(int i=0;i<=1;i++)
		for(int j=0;j<=1;j++)
			for(int k=0;k<=1;k++)
				temp[i][j]=(temp[i][j]+multiply(q.f[i][k],w.f[k][j]))%p;
	memcpy(q.f,temp,sizeof(temp));
}

long long fib(long long a)
{
	while(a)
	{
		if(a&1)
			mat_mul(ans,mat);
		a>>=1;
		mat_mul(mat,mat);
	}
	return ans.f[0][0];
}


int main()
{
	ans.f[0][0]=ans.f[1][1]=mat.f[0][1]=mat.f[1][0]=mat.f[0][0]=1;
	scanf("%lld%lld",&n,&p);
	printf("%lld",qpow(((fib(n+2)-n-2)%p+p)%p,n+1));
	return 0;
}