题解 P5059 【中国象棋】

本题数据规模较大，容易看出这是一道数学题，有一个坑点，就是格点与格子并不是一个东西，有没有掉坑呢 $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; } ```