题意
Takahashi在二维平面的原点,它可以瞬移\(N\)次,每次可以从当前点\((x,y)\)瞬移至\((x+A,y+B)\),\((x+C,y+D)\),\((x+E,y+F)\)中的任一点.平面上有\(M\)个障碍点不能到达.问经过\(N\)次瞬移可能的不同路径数.
题目细节详见E - Warp (atcoder.jp).
思路
比赛时想的是组合数学,用\(3^N\)减去不能到达的路径总数,但是有一些路径可能会被重复减去,容斥原理似乎也不太好解决.乱搞了一小时还是毫无头绪.赛时代码:Submission #34242009 - AtCoder Beginner Contest 265.
正解是DP.用\(dp(i,x,y)\)表示已经瞬移了\(i\)次,当前坐标为\((x,y)\)时的方案数,注意到\((x,y)\)可能的取值并不多(因为只能瞬移\(N\)次),可以用map来辅助DP,总的复杂度为\(O(N^3(\log N+\log M))\).实际由于map的效率较低可能会TLE.代码:
#include<bits/stdc++.h>
using namespace std;
#define N 305
#define MOD 998244353
#define p make_pair
int n,m,a,b,c,d,e,f;
set< pair<int,int> >s;
map< pair<int,int>, int>dp[N];
int dfs(int step,int x,int y){
if(step==n){
return 1;
}
if(dp[step].find(p(x,y))!=dp[step].end()){
return dp[step][p(x,y)];
}
if(s.find(p(x+a,y+b))==s.end()){
dp[step][p(x,y)]+=dfs(step+1,x+a,y+b);
dp[step][p(x,y)]%=MOD;
}
if(s.find(p(x+c,y+d))==s.end()){
dp[step][p(x,y)]+=dfs(step+1,x+c,y+d);
dp[step][p(x,y)]%=MOD;
}
if(s.find(p(x+e,y+f))==s.end()){
dp[step][p(x,y)]+=dfs(step+1,x+e,y+f);
dp[step][p(x,y)]%=MOD;
}
return dp[step][p(x,y)];
}
int main(){
int i,x,y;
scanf("%d%d",&n,&m);
scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
for(i=1;i<=m;i++){
scanf("%d%d",&x,&y);
s.insert(p(x,y));
}
printf("%d",dfs(0,0,0));
return 0;
}
用同样的思路,换一种DP方式.设\(dp(i,j,k)\)表示按第一种方法瞬移了\(i\)次,按第二种方法瞬移了\(j\)次,按第三种方法瞬移了\(k\)次的方案数,则当前坐标\((x,y)\)可以用\((a\times i+c\times j+e\times k,b\times i+d\times j+f\times k)\)来计算,如果当前位置没有障碍,则转移状态.AC代码:
#include<bits/stdc++.h>
using namespace std;
#define N 305
#define MOD 998244353
#define p make_pair
int n,m,a,b,c,d,e,f,ans;
set< pair<int,int> >s;
int dp[N][N][N];
int main(){
int i,j,k,x,y;
scanf("%d%d",&n,&m);
scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
for(i=1;i<=m;i++){
scanf("%d%d",&x,&y);
s.insert(p(x,y));
}
dp[0][0][0]=1;
for(i=0;i<=n;i++){
for(j=0;i+j<=n;j++){
for(k=0;i+j+k<=n;k++){
x=a*i+c*j+e*k;
y=b*i+d*j+f*k;
if(s.find(p(x+a,y+b))==s.end())
dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k])%MOD;
if(s.find(p(x+c,y+d))==s.end())
dp[i][j+1][k]=(dp[i][j+1][k]+dp[i][j][k])%MOD;
if(s.find(p(x+e,y+f))==s.end())
dp[i][j][k+1]=(dp[i][j][k+1]+dp[i][j][k])%MOD;
if(i+j+k==n)
ans=(ans+dp[i][j][k])%MOD;
}
}
}
printf("%d",ans);
return 0;
}