牛客小白月赛 传送门

F题 小杜跑酷（补题）

自己思路：递归跑每一种情况，机关位置分三个数组存排序+用指针（变量指向下标模拟）。
写了很久+改了更久，最后发现递归过程中一种情况修改了下标后会影响到下一种情况，
裂开不整去看题解...

题解dp+地图压缩
基本就是题解原代码，累了，copy借鉴大佬代码，快乐AC！
`#include <bits/stdc++.h>
using namespace std;

define ll long long

define endl '\n'

const ll mod=998244353;
const int N=5e5;
ll n,m;
ll mp[3][(N+10)3];
ll dp[3][(N+10)3];
pair<ll,ll> a[N+10];
ll newpose[N+10];
void add(ll &x,ll &y)
{
x+=y;
if(x>=mod) x-=mod;
}
int main()
{
cin>>n>>m;
for(ll i=1;i<=m;i++){
cin>>a[i].second>>a[i].first;
}
sort(a+1,a+1+m);
for(ll i=1;i<=m;i++){
ll dis=a[i].first-a[i-1].first;
if(dis<2) newpose[i]=newpose[i-1]+dis;
else newpose[i]=newpose[i-1]+2;
mp[a[i].second-1][newpose[i]]=1;
}
dp[0][1]=1;
for(ll i=1;i<=3N+10;i++){
for(ll j=0;j<=2;j++){
if(!(j==1&&mp[j][i-1])) add(dp[j][i],dp[j][i-1]);
if(i-2>=0&&mp[j][i-2]) add(dp[j][i],dp[j][i-2]);
if(j>=1&&mp[j-1][i-1]) add(dp[j][i],dp[j-1][i-1]);
if(j<=1&&mp[j+1][i-1]) add(dp[j][i],dp[j+1][i-1]);
}
}
cout<<dp[0][3N+10]<<endl<<dp[1][3N+10]<<endl<<dp[2][3N+10];
return 0;
}`