P14006

在一个环上有两点，每次白点在从环的两边到黑点更近的路线上走一条边，黑点可以选择是否向左右走一条边，求一定时间内两点最短距离至少为 $2$ 的方案数。

每次的状态只与上一次有关，考虑 DP。

定义 $f_{i,j}$ 为第 $i$ 秒黑点在 $j$ 点的方案数，边界条件为 $f_{0,x}=1$。

预处理出白点每次的位置。

在当前黑点不与白点重合时，首先应加上上一秒不动的方案数。然后若左右点不与白点重合，或当前黑点也不与上一次白点重合（保证最短距离为 $2$），则加上上一秒在该位置的方案数。

注意取模与边界的处理。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pb push_back
const int N = 7e3 + 5, P = 998244353;
int n, x, y, k, f[N][N], p[N];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>x>>y>>k;
	if(x==y)
		return cout<<0, 0;
	p[0]=y;
	int d=((x-y+n)%n<(y-x+n)%n? 1: -1);
	for(int i=1; i<=k; ++i) {
		p[i]=p[i-1]+d;
		if(p[i]>n)
			p[i]=1;
		if(p[i]==0)
			p[i]=n;
	}
	f[0][x]=1;
	int ans=0;
	for(int i=1; i<=k; ++i) {
		for(int j=1; j<=n; ++j) {
			if(j==p[i])
				continue;
			f[i][j]+=f[i-1][j];
			int l=j-1, r=j+1;
			if(r>n)
				r=1;
			if(l==0)
				l=n;
			if(l!=p[i] || j!=p[i-1])
				f[i][j]+=f[i-1][l];
			if(r!=p[i] || j!=p[i-1])
				f[i][j]+=f[i-1][r];
			f[i][j]%=P;
			if(i==k)
				ans=(ans+f[i][j])%P;
		}
	}
	cout<<ans;
	return 0;
}

题解来之不易，麻烦点赞再走~