Atcoder 题解

Atcoder Beginnner Contest 265 problem E 题解

题目链接：点我

题目大意

一个人初始在$(0,0)$的位置。他有一个传送器。他会进行$N$次操作，每次操作进行一下三种中的一种(当前他在$(x,y)$的位置)：

• 从$(x,y)$传送到$(x+A,x+B)$的位置；
• 从$(x,y)$传送到$(x+C,x+D)$的位置；
• 从$(x,y)$传送到$(x+E,x+F)$的位置；

另外，在地图上有$M$个点有障碍物。这个人不能传送到这些点上。

问这个人从初始点开始，经过$N$次操作后能得到多少不同的路径。答案对$998244353$取模。

第一行输入$N,M$，第二行输入$A,B,C,D,E,F$,接下来$M$行,每行两个整数，表示障碍物的坐标。

样例输入1

2 2
1 1 1 2 1 3
1 2
2 2

样例输出1

5

样例解释1

有以下五条路径：

• $(0,0) \rightarrow (1,1) \rightarrow (2,3)$
• $(0,0) \rightarrow (1,1) \rightarrow (2,4)$
• $(0,0) \rightarrow (1,3) \rightarrow (2,4)$
• $(0,0) \rightarrow (1,3) \rightarrow (2,5)$
• $(0,0) \rightarrow (1,3) \rightarrow (2,6)$

样例输入2

10 3
-1000000000 -1000000000 1000000000 1000000000 -1000000000 1000000000
-1000000000 -1000000000
1000000000 1000000000
-1000000000 1000000000

样例输出2

0

样例输入3

300 0
0 0 1 0 0 1

样例输出3

292172978

数据范围

• $1 \leq N \leq 300$
• $0 \leq M \leq 10^5$
• $-10^9 \leq A,B,C,D,E,F \leq 10^9$
• $(A,B),(C,D),(E,F)$是互不相同的
• $-10^9 \leq X_i,Y_i \leq 10^9$
• 所有$(X_i,Y_i)$是互不相同的
• 所有输入均为整型数

解析

本蒟蒻第一次考场拿下第五题！！！(纪念一下)

首先想到的是最最最暴力的$BFS$,时间复杂度$O(3^N)$，(铁定能过)

一般对于这种数路径，又有模数的问题，很容易就想到$dp$。

但这道题的地图是无限大的，所以不可能枚举点。然而我们发现，如果我们确定了三种操作的次数，那么这个人最终到达的点也可以被确定。因此，我们不妨枚举三个操作所用的次数，这样就可以知道当前这个人在那个点，如下：

//三层枚举
int gx=i*A+j*C+k*E;
int gy=i*B+j*D+k*F;

定义$f[i][j][k]$表示这个人走到$(i,j,k)$表示的点处的方案数。

然后，这个点只可能由三种状态转移而来，即$f[i-1][j][k],f[i][j-1][k],f[i][j][k-1]$。用$f[i][j][k]$将它们累加。

如果说$(i,j,k)$这个点是一个障碍物，那么$f[i][j][k]=0$.

当$i+j+k==N$时，将答案累加即可。

比较有趣的一点是，这道题的时间限制是$3s$，众所周知，测评器$1s$能跑$10^7$次循环，而$300^3=2.7 \times 10^7$，刚好是$3s$的时限。本蒟蒻也是从这里受到了启发。

好了，话不多说，上代码：

代码实现:

#include<iostream>
#include<map>
using namespace std;
#define int long long
const int N=305,mod=998244353,base=1e9;
int n,m,a,b,c,d,e,F;
int f[N][N][N],ans;
int x,y;
map<int,bool>mp;
inline int get_point(int x,int y){
    return (x-1)*base+y;
}
signed main(){
    cin>>n>>m>>a>>b>>c>>d>>e>>F;
    for(int i=1;i<=m;i++) cin>>x>>y,mp[get_point(x,y)]=1;//坐标很大，我们可以将二维坐标一维化，然后用map存储
    f[0][0][0]=1;//初始在(0,0)的位置，所以
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++){
            if(i+j>n) break;
            for(int k=0;k<=n;k++){
                if(i+j+k>n) break; //玄学优化
                if(i==0&&j==0&&k==0) continue; //起始点不用更新
                int gx=i*a+j*c+k*e;
                int gy=i*b+j*d+k*F;
                if(mp[get_point(gx,gy)]) {f[i][j][k]=0;continue;} //障碍物
                if(i) f[i][j][k]=(f[i][j][k]+f[i-1][j][k])%mod;
                if(j) f[i][j][k]=(f[i][j][k]+f[i][j-1][k])%mod;
                if(k) f[i][j][k]=(f[i][j][k]+f[i][j][k-1])%mod;
                //一定要注意是否为0，不然数组可能会越界
                if(i+j+k==n) ans=(ans+f[i][j][k])%mod;
            }
        }
    cout<<ans;
    //跑出来刚好2700ms，神不神奇呢
}

完结撒花~~~