题解 P3990 【[SHOI2013]超级跳马】

· · 题解

前言

题解中各位大佬的方法好像都有点烦诶

窝来一个（个人感觉）比较简单的方法

解法

依旧是考虑dp方程

依旧是设f[i][j]为跳到(i,j)的方案数

先考虑一次只能往右跳一格的情况

那么方程很简单

f[i][j]=f[i-1][j-1]+f[i-1][j]+f[i-1][j+1]

那么如何加上一次往右跳任意奇数格呢？

我们发现除去只能往右跳一格的情况外，所有可以一步跳到(i,j)的都可以一步跳到(i-2,j)，所有可以一步跳到(i-2,j)的都可以一步跳到(i,j)

于是，我们的方程就出来了：

f[i][j]=f[i-1][j-1]+f[i-1][j]+f[i-1][j+1]+f[i-2][j]

直接递推的复杂度O(nm)，显然不可以接受

于是我们可以采用矩阵优化

构造矩阵也很简单（以n=4为例）

\left( \begin{matrix} 1&1&0&0&1&0&0&0\\ 1&1&1&0&0&1&0&0\\ 0&1&1&1&0&0&1&0\\ 0&0&1&1&0&0&0&1\\ 1&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0&0\\ 0&0&1&0&0&0&0&0\\ 0&0&0&1&0&0&0&0 \end{matrix} \right) \times \left( \begin{matrix} f[i-1][1]\\ f[i-1][2]\\ f[i-1][3]\\ f[i-1][4]\\ f[i-2][1]\\ f[i-2][2]\\ f[i-2][3]\\ f[i-2][4] \end{matrix} \right) = \left( \begin{matrix} f[i][1]\\ f[i][2]\\ f[i][3]\\ f[i][4]\\ f[i-1][1]\\ f[i-1][2]\\ f[i-1][3]\\ f[i-1][4] \end{matrix} \right)

接下来，矩阵快速幂就好了qwq

代码

#include<bits/stdc++.h>
#define p 30011
#define int long long
using namespace std;
int n,m;
struct Node
{
    int a[110][110];
    Node(int x){memset(a,0,sizeof(a));};
}e(0),base(0);
Node operator * (Node x,Node y)
{
    Node ret(0);
    for(int i=1;i<=2*n;i++)
        for(int j=1;j<=2*n;j++)
            for(int k=1;k<=2*n;k++)
                ret.a[i][j]=(ret.a[i][j]+x.a[i][k]*y.a[k][j]+p)%p;
    return ret;
}
Node operator ^ (Node x,int y)
{
    Node ret(0);ret=e;
    while(y)
    {
        if(y%2==1)ret=ret*x;
        x=x*x;y>>=1;
    }
    return ret;
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=2*n;i++)e.a[i][i]=1;
    for(int i=1;i<=n;i++)
        for(int j=max(i-1,1ll);j<=min(i+1,n);j++)
            base.a[i][j]=1;
    for(int i=1;i<=n;i++)base.a[i][i+n]=1;
    for(int i=1;i<=n;i++)base.a[i+n][i]=1;
    if(m==2)//一波特判（应该很好理解）
    {
        if(n==1||n==2)
        {
            printf("1\n");
            return 0;
        }
        printf("0\n");
        return 0;
    }
    if(m==3)
    {
        if(n==1||n==3)
        {
            printf("1\n");
            return 0;
        }
        if(n==2)
        {
            printf("2\n");
            return 0;
        }
        printf("0\n");
        return 0;
    }
    base=base^(m-2);
    if(n==1)printf("%lld",(base.a[2*n][1]+base.a[2*n][2])%p);
    else if(n==2)printf("%lld",(base.a[2*n][1]*2+base.a[2*n][2]*2+base.a[2*n][n+1]+base.a[2*n][n+2])%p);
    else printf("%lld",(base.a[2*n][1]*2+base.a[2*n][2]*2+base.a[2*n][3]+base.a[2*n][n+1]+base.a[2*n][n+2]+p)%p);
    return 0;//输出时也要特判（边界各位自己思考吧qwq，其实还是挺坑的）
}