题解 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;
}