中国象棋 题解
学无止境
2018-11-20 17:53:54
本题数据规模较大,容易看出这是一道数学题,有一个坑点,就是格点与格子并不是一个东西,有没有掉坑呢 $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;
}
```