ABC265E题解

Ginger_he · 2022-10-22 07:54:58 · 题解

题目描述

给定平面直角坐标系上的 M 个点。一开始你在原点，接下来执行 N 次操作，每次操作你可以从 (i,j) 走到 (i+A,j+B) 或 (i+C,j+D) 或 (i+E,j+F)，求不经过给定的 M 个点的方案数，答案对 998244353 取模。

题解

建议评绿。

这题和乌龟棋很像，考虑设计一个 dp，dp_{i,j,k} 表示走 i 次 (A,B)，j 次 (C,D)，k 次 (E,F) 的方案数。我们可以简单的用一下哈希，把某个点 (x,y) 用一个数 2x\times10^9+y 来表示，放到 map 里表示可不可走，转移的时候判断当前点能否经过即可，时间复杂度 O(n^3\log m)，不过显然跑不满。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 305
const ll p=998244353;
ll n,m,a,b,c,d,e,f,x,y,dp[N][N][N],ans;
map<ll,bool> mp;
int main()
{
    scanf("%lld%lld%lld%lld%lld%lld%lld%lld",&n,&m,&a,&b,&c,&d,&e,&f);
    for(ll i=1;i<=m;i++)
    {
        scanf("%lld%lld",&x,&y);
        mp[x*2e9+y]=1;
    }
    dp[0][0][0]=1;
    for(ll i=0;i<=n;i++)
    {
        for(ll j=0;i+j<=n;j++)
        {
            for(ll k=0;i+j+k<=n;k++)
            {
                x=i*a+j*c+k*e,y=i*b+j*d+k*f;
                if(!mp[x*2e9+y])
                {
                    if(i) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k])%p;
                    if(j) dp[i][j][k]=(dp[i][j][k]+dp[i][j-1][k])%p;
                    if(k) dp[i][j][k]=(dp[i][j][k]+dp[i][j][k-1])%p; 
                }
                if(i+j+k==n)
                    ans=(ans+dp[i][j][k])%p;
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}