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

· · 题解

本题我想到一个不同于其他人的优化 dp 的做法

考虑我们将问题转化，看成一个下面的问题：

一共有 s 的时间，可以用 t 时间( t 为奇数)移动到本行或者相邻行，问方案数

那么就可以想到奇数往往是一个特殊的限制条件，奇数时间的跳跃可以看作 2\times x+1 的跳跃

也就是说，我们将每一个点分为3个点，分别是入点，奇数点，偶数点

我们 2\times x 的跳跃可以看作在奇数点和偶数点组成的环上来回走，这也就变成了类似于求两个点经过 k 条边到达的方案数，就直接套用矩阵乘法

下面用一张图来说明一下拆点过后的连边方式：

(2a有一个自环我画不出来了)

下面是代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n,m,t;

int mod=30011;

struct M
{
  int s[160][160],r,c;
  void clear()
  {
    for(int i=1;i<=151;i++) for(int j=1;j<=151;j++) s[i][j]=0;
  }
}ans,Ye;

M operator * (const M &x,const M &y)
{
  M now;
  now.clear();
  now.r=x.r;
  now.c=y.c;
  for(int i=1;i<=x.r;i++)
  {
    for(int k=1;k<=x.c;k++)
    {
      for(int j=1;j<=y.c;j++)
      {
        now.s[i][j]=(now.s[i][j]+x.s[i][k]*y.s[k][j]%mod)%mod;
      }
    }
  }
  return now;
}

M ksm(M a,int b)
{
  M ans=a;
  b--;
  while(b)
  {
    if(b&1) ans=ans*a;
    a=a*a;
    b>>=1;
  }
  return ans;
}

int main()
{
  scanf("%d%d",&n,&m);
  ans.clear();
  ans.r=1;
  ans.c=3*n;
  ans.s[1][1]=1;
  Ye.clear();
  Ye.r=3*n;
  Ye.c=3*n;
  for(int i=1;i<=n;i++)
  {
    Ye.s[3*i-2][3*i-1]=1;
    Ye.s[3*i-1][3*i]=1;
    Ye.s[3*i][3*i-1]=1;
    Ye.s[3*i-2][3*i-2]=1;
    Ye.s[3*i][3*i-2]=1;
    if(i!=n) Ye.s[3*i-2][3*(i+1)-2]=1;
    if(i!=1) Ye.s[3*i-2][3*(i-1)-2]=1;
    if(i!=n) Ye.s[3*i][3*(i+1)-2]=1;
    if(i!=1) Ye.s[3*i][3*(i-1)-2]=1;
  }
  ans=ans*ksm(Ye,m-1);
  printf("%d\n",ans.s[1][3*n-2]);
}