ABC265E 题解

dAniel_lele · 2022-08-18 14:06:35 · 题解

蛮经典的一道题。

思路

考虑 n\leq 300，我们改变定义，令 dp_{i,j,k} 表示三种走法各走了 i,j,k 步的方案。如果终点是不合法点直接为 0，i+j+k=n 时统计入答案，否则转移到 dp_{i+1,j,k},dp_{i,j+1,k},dp_{i,j,k+1} 即可。题目难度其实还行，dp 的一个小套路。关于记录点可以用 map 或 unordered_map。复杂度 \Theta(n^3\log m)，由于 unordered_map 常数极小几乎 \Theta(1) 所以没啥问题。

代码

#include <bits/stdc++.h>
#define int long long
#define double long double
#define mid ((l+r)>>1)
using namespace std;
const int mod=998244353;
int dp[305][305][305];
unordered_map<int,int> mp;
signed main(){
    dp[0][0][0]=1;
    int n,m;
    cin>>n>>m;
    int a,b,c,d,e,f;
    cin>>a>>b>>c>>d>>e>>f;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        mp[(x+1000000007)*(2000000114)+(y+1000000007)]=1;
    }
    int ans=0;
    for(int i=0;i<=n;i++){
        for(int j=0;j+i<=n;j++){
            for(int k=0;k+j+i<=n;k++){
                int px=a*i+c*j+e*k,py=b*i+d*j+f*k;
                if(mp[(px+1000000007)*(2000000114)+(py+1000000007)]) continue;
                if(i+j+k==n){
                    ans=(ans+dp[i][j][k])%mod;
                    continue;
                }
                dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k])%mod;
                dp[i][j+1][k]=(dp[i][j+1][k]+dp[i][j][k])%mod;
                dp[i][j][k+1]=(dp[i][j][k+1]+dp[i][j][k])%mod;
            }
        } 
    }
    cout<<ans;
    return 0;
}