「洛谷P5059」中国象棋

发表于 | 分类于 | | 浏览量： 次

又是数数题QwQ…

传送门

洛谷P5059

题解

首先注意题目中说的是有$n^2$个格子，也就是$(n+1)^2$个格点。

以下是出题人的推导：

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

设$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]$

好了很显然这是一个斐波那契数列。自己再推一下，注意一下细节，不难发现最后的答案就是

矩阵加快速幂就可以在$\Theta(\log n)$的复杂内求解。

还有一个问题，由于n和P都非常大，直接乘long long也会boom。所以这里用了一个类似于快速幂的方法来求$(a*b)\mod P$的值。虽然复杂度多了一只log，但是很好写，并且避免了高精度又臭又长的代码和大常数复杂度。

代码

还挺好写的呢poi。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<cstdio>
using namespace std;
typedef long long LL;
LL n,P;
LL Multiply(LL x,LL y)          //两个10^18级别的数在模P意义下的乘法
{
	LL ret=0,w=x;
	while(y)
	{
		if(y&1) ret=(ret+w)%P;
		w=(w+w)%P;y>>=1;
	}
	return ret;
}
struct Matrix
{
	LL a[2][2];
	Matrix(){a[0][0]=a[0][1]=a[1][0]=a[1][1]=0;}
	Matrix operator * (Matrix b)   //矩阵乘法
	{
		Matrix c;
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				for(int k=0;k<2;k++)
					c.a[i][j]=(c.a[i][j]+Multiply(a[k][j],b.a[i][k]))%P;
		return c;
	}
}ans,mat,tep;
LL QP(LL a,LL b)               //普通快速幂
{
	LL ret=1,w=a;
	while(b)
	{
		if(b&1) ret=Multiply(ret,w);
		w=Multiply(w,w);b>>=1;
	}
	return ret;
}
int main()
{
	scanf("%lld%lld",&n,&P);
	ans.a[0][0]=ans.a[0][1]=mat.a[0][0]=mat.a[0][1]=mat.a[1][0]=1;
	LL b=n+1;tep=mat;
	while(b)                //矩阵加速斐波那契数列
	{
		if(b&1) mat=mat*tep;
		tep=tep*tep;b>>=1;
	}
	ans=ans*mat;
	printf("%lld\n",QP(((ans.a[0][0]-n-2)%P+P)%P,n+1));
	return 0;
}