[ABC265E] Warp 题解

FFTotoro · 2022-10-23 22:44:26 · 题解

本题可以使用记忆化搜索。

首先，我们要明白一个性质：

设题目中的三种操作从原点开始分别进行了 t_1,t_2,t_3 次，那么高桥君现在所处的位置就是 (t_1A+t_2C+t_3E,t_1B+t_2D+t_3F)。

很显然，利用一个 std::set 就可以存储所有禁止走到的点的坐标，查找时利用 find 函数即可。

我们可以定义一个函数 int dfs(int x,int y,int z)，代表目前搜到了“三种操作分别进行了 x,y,z 次的点”，并用一个三维数组 g 保存答案。如果 x+y+z=n，那么就代表搜到了答案，返回 1。然后不断递归下去就可以求解。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int P=998244353;
set<pair<int,int> > s;
int n,m,a,b,c,d,e,f,g[301][301][301];
int dfs(int x,int y,int z){
  int x0=a*x+c*y+e*z,y0=b*x+d*y+f*z; // 求坐标
  if(s.find(make_pair(x0,y0))!=s.end())return 0; // 不能走
  if(x+y+z==n)return 1; // 搜到了合法方案
  if(g[x][y][z])return g[x][y][z]; // 已经标记过
  return g[x][y][z]=(dfs(x+1,y,z)+dfs(x,y+1,z)+dfs(x,y,z+1))%P; // 三种走法分别 +1
}
main(){
  ios::sync_with_stdio(false);
  cin>>n>>m>>a>>b>>c>>d>>e>>f;
  for(int i=0;i<m;i++){int x,y; cin>>x>>y,s.emplace(x,y);}
  cout<<dfs(0,0,0)<<endl;
  return 0;
}