题解 P3713 【[BJOI2017]机动训练】

· · 题解

容易看出，假如一共有 k 种地形序列，第 i 种地形序列对应的合法机动路径有 a_i 种，则答案为 \sum a_i^2。

有没有觉得这个式子很眼熟？可以去看看 [NOI2009]管道取珠 这道题。

和那道题思路一样，我们将这个式子解释为两个人同时出发，在机动路径合法的前提下，走出相同地形序列的方案数。

我们设 f(x_1,y_1,x_2,y_2) 表示两条机动路径的方向分别为 (x_1,y_1) 和 (x_2,y_2) 时的方案数。我们枚举左上，左下，右上，右下四个方向即可。考虑到坐标轴的方向会被重复计算，需要再减去在坐标轴上的方向的方案数。

接下来再设 g(x_1,y_1,x_2,y_2) 表示第一个人从 (x_1,y_1) 出发，第二个人从 (x_2,y_2) 出发时，方向与上面 f 的方向对应，地形序列相同的方案数。

记忆化搜索即可。

// Problem : P3713 [BJOI2017]机动训练
// Contest : Luogu
// URL : https://www.luogu.com.cn/problem/P3713
// Memory Limit : 250 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <cstdio>
#include <cstring>
#include <vector>
#define MOD 1000000009
using namespace std;
int f[5][5][5][5],g[35][35][35][35];
int m,n;
char s[35][35];
vector<pair<int,int> > a,b;
int dp(int x,int y,int r,int c)
{
 if(s[x][y]!=s[r][c])return 0;
 if(x<1||x>m||y<1||y>n||r<1||r>m||c<1||c>n)return 0;
 if(~g[x][y][r][c])return g[x][y][r][c];
 int ans=1;
 for(auto i:a)
  for(auto j:b)
  {
   int dx=i.first,dy=i.second,dr=j.first,dc=j.second;
   ans=(ans+dp(x+dx,y+dy,r+dr,c+dc))%MOD;
  }
 return g[x][y][r][c]=ans;
}
int dfs(int x,int y,int p,int q)
{
 if(~f[x+1][y+1][p+1][q+1])
  return f[x+1][y+1][p+1][q+1];
 a.clear(),b.clear();
 for(int i=-1;i<=1;i++)
  if(!i||i==x)
   for(int j=-1;j<=1;j++)
    if((i||j)&&(!j||j==y))
     a.emplace_back(i,j);
 for(int i=-1;i<=1;i++)
  if(!i||i==p)
   for(int j=-1;j<=1;j++)
    if((i||j)&&(!j||j==q))
     b.emplace_back(i,j);
 memset(g,-1,sizeof(g));
 int ans=0;
 for(int i=1;i<=m;i++)
  for(int j=1;j<=n;j++)
   for(int r=1;r<=m;r++)
    for(int c=1;c<=n;c++)
     ans=(ans+dp(i,j,r,c))%MOD;
 f[x+1][y+1][p+1][q+1]=f[p+1][q+1][x+1][y+1]=ans;
 f[-x+1][-y+1][-p+1][-q+1]=f[-p+1][-q+1][-x+1][-y+1]=ans;
 return ans;
}
int calc(int x,int y)
{
 int ans=0;
 ans=(ans+dfs(x,y,1,1))%MOD;
 ans=(ans+dfs(x,y,1,-1))%MOD;
 ans=(ans+dfs(x,y,-1,1))%MOD;
 ans=(ans+dfs(x,y,-1,-1))%MOD;
 ans=(ans-dfs(x,y,1,0)+MOD)%MOD;
 ans=(ans-dfs(x,y,-1,0)+MOD)%MOD;
 ans=(ans-dfs(x,y,0,1)+MOD)%MOD;
 ans=(ans-dfs(x,y,0,-1)+MOD)%MOD;
 return ans;
}
int main()
{
 memset(f,-1,sizeof(f));
 scanf("%d%d",&m,&n);
 for(int i=1;i<=m;i++)
  scanf("%s",s[i]+1);
 int ans=0;
 ans=(ans+calc(1,1))%MOD;
 ans=(ans+calc(1,-1))%MOD;
 ans=(ans+calc(-1,1))%MOD;
 ans=(ans+calc(-1,-1))%MOD;
 ans=(ans-calc(1,0)+MOD)%MOD;
 ans=(ans-calc(-1,0)+MOD)%MOD;
 ans=(ans-calc(0,1)+MOD)%MOD;
 ans=(ans-calc(0,-1)+MOD)%MOD;
 printf("%d\n",ans);
 return 0;
}