P5059 中国象棋

由题意可知，首先将 \(n+1\) 。
每一行显然是互不干扰的，所以最终的答案就是第一行答案 \(ans\) 的 \(n\) 次方。

下面考虑如何求第一行的答案。

首先，如果一次将两个限制都考虑进去，那么有一个显然的 dp，设 \(dp_{i,j,k}\) 表示第 \(i\) 个格子的状态为 \(k\) ，\(k\) 为 \(1\) 表示这个格子有棋子，\(0\) 则表示没有，前 \(i\) 个格子填了 \(j\) 个棋子的方案数。但这样是不可做的。
接下来，考虑只有第二个限制。有 \(dp_{i,k}\) ，就是省去前面第二维的 dp 式子。那么转移就是 $$dp_{i,0}=dp_{i-1,0}+dp_{i-1,1}$$ $$dp_{i,1}=dp_{i-1,0}$$
设 \(ans_i\) 表示仅考虑前 \(i\) 个格子的方案数（不考虑第一个限制的情况下），有 $$ans_{i-1}=dp_{i,0}$$ $$ans_i=dp_{i,0}+dp_{i,1}=2\times dp_{i-1,0}+dp_{i-1,1}=ans_{i-1}+dp_{i-1,0}=ans_{i-1}+ans_{i-2}$$
然后加入第一个限制，设 \(Ans_i\) 表示前 \(i\) 个格子真正的方案数，显然就是从 \(ans_i\) 里减去只放一个棋子和不放的方案数，则$$Ans_i=ans_i-(i+1)$$
现在就可以得到第一行的最终答案 \(Ans_n=ans_n-(n+1)\) ，而其中的 \(ans_n\) 显然可以通过矩阵快速幂求出。
最后总的答案就是 \(Ans_n^n\) ，进行快速幂求解即可。

#include<bits/stdc++.h>
#define int __int128
using namespace std;

inline int rd()
{
    int ret=0;
    char c=getchar();
    for (;!isdigit(c);c=getchar());
    for (; isdigit(c);c=getchar()) ret=ret*10+(c-'0');
    return ret;
}
inline void wr(int x)
{
    if (!x) return putchar('0'),void();
    short pt[100],tp=0;
    for (;x;x/=10) pt[++tp]=x%10;
    for (;tp;tp--) putchar(pt[tp]^48);
}

int n,mod,ans,d;
inline int add(int x) {return x%mod;}

struct Matrix1{
    int a[2];
    inline void init() {a[0]=a[1]=0;}
    int& operator[](int x) {return a[x];}
}bas;
struct Matrix2{
    int a[2][2];
    inline void init() {memset(a,0,sizeof a);}
    Matrix1 operator*(const Matrix1& b)const{
        Matrix1 c;
        c.init();
        for (int i=0;i<2;i++)
            for (int j=0;j<2;j++) c.a[i]=add(c.a[i]+a[i][j]*b.a[j]%mod);
        return c;
    }
    Matrix2 operator*(const Matrix2& b)const{
        Matrix2 c;
        c.init();
        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]=add(c.a[i][j]+a[i][k]*b.a[k][j]%mod);
        return c;
    }
}tmp;

inline void ksm(int b)
{
    while (b)
    {
        if (b&1) bas=tmp*bas;
        tmp=tmp*tmp;
        b>>=1;
    }
}

inline int ksm(int a,int b)
{
    int ret=1;
    while (b)
    {
        if (b&1) ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}

signed main()
{
    n=rd(),mod=rd();
    n++;
    if (n==1) ans=0;
    else if (n==2) ans=0;
    else
    {
        bas[0]=3,bas[1]=2;
        tmp.a[0][0]=tmp.a[0][1]=tmp.a[1][0]=1;
        tmp.a[1][1]=0;
        ksm(n-2);
        ans=bas.a[0];
        ans=add((ans-n-1)%mod+mod);
    }
    wr(ksm(ans,n));
}

这题其实最难的地方是在想到要一个个的满足限制，想到了这里，后面的就很简单了。