[ABC265E] Warp

· · 题解

题目

读完题之后很容易设 f(i,j) 为到 i,j 的方案数……吗？
可是发现并不是的,因为 i,j 都是大于 10^9 的数,数组没办法开那么大。

这时候又看到 n 为 300，300^3 正好可以过，那怎么设三维的 DP ? 发现 题目的移动方法正好有 3 种,那就设 f[i][j][k] 中

所以状态转移方程就是： ${f}_{i,j,k}={f}_{i-1,j,k}+{f}_{i,j-1,k}+{f}_{i,j,k-1}

所以说当前的位置就是：

x=i\times A +j\times C+k\times E y=i\times B+j\times D+k\times F

还有一个地方需要处理,因为题目中 M 的范围是 10^5 ,所以如果暴力判断是否经过,会超时。我们可以用 map 存 X_i,Y_i。

code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map> 
using namespace std;
const int mod=998244353;
int n,m;
long long A,B,C,D,E,F;
int f[302][302][302];
map<long long,int> vi;
long long ans=0;
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%lld%lld%lld%lld%lld%lld",&A,&B,&C,&D,&E,&F);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        vi[x*1e9+y]=1;
    }
    f[0][0][0]=1;
    for(int i=0;i<=n;i++)//注意从0开始，因为可能一次都不用 
    {
        for(int j=0;j<=n;j++)
        {
            if(i+j<=n)//小优化 
            {
                for(int k=0;k<=n;k++)
                {   
                    if(i+j+k<=n) 
                    {
                        if(vi[(i*A+j*C+k*E)*1e9+i*B+j*D+k*F]==1) continue;
                        if(i-1>=0) f[i][j][k]=(f[i][j][k]+f[i-1][j][k])%mod;
                        if(j-1>=0) f[i][j][k]=(f[i][j][k]+f[i][j-1][k])%mod;
                        if(k-1>=0) f[i][j][k]=(f[i][j][k]+f[i][j][k-1])%mod; 
                        if(i+j+k==n)
                        ans=(ans+f[i][j][k])%mod;
                    }

                }
            }

        }
    } 
    printf("%lld\n",ans);
    return 0;
}