T6 空间跃迁

solution

用 $dp$ 解决，设 $dp_{i,u,v}$ 为当前走了 $i$ 步，用方案一走了 $u$ 次，用方案二走了 $v$ 次

显然的，用方案三走了 $i- u - v$ 次

用 $map$ 标记障碍物的坐标，若障碍物则为 $0$，$dp_{0 , 0 , 0}$ 初始化为 $1$ ，表示走 $1$ 步有一种方案

状态转移方程为：

$$dp_{i , u , v} = dp_{i - 1,u,v} + dp_{i-1,u-1,v} + dp_{i-1,u,v-1}$$

最终的答案就是当 $i = n$ 时的 $dp$ 值

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 305;
const int mod = 998244353;

int dp[N][N][N];
ll n , m , a , b , c , d , e , f;
map<pair<ll , ll> , bool> mp;
ll ans;

int main(){
	freopen("jump.in" , "r" , stdin);
	freopen("jump.out" , "w" , stdout);
	
	cin >> n >> m >> a >> b >> c >> d >> e >> f;
	
	for(int i = 1 ; i <= m ; i ++){
		int x , y;
		cin >> x >> y;
		mp[{x , y}] = 1;
	}
	
	dp[0][0][0] = 1;
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 0 ; j <= i ; j ++){
			for(int k = 0 ; j + k <= i ; k ++){
				int w = i - j - k;
				ll nx = a * j + c * k + e * w;
				ll ny = b * j + d * k + f * w;
				
				if(mp.count({nx , ny}) > 0) continue;
				dp[i][j][k] = dp[i - 1][j][k] % mod;
				if(j > 0) dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 1][k]) % mod;
				if(k > 0) dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % mod;
				
				if(i == n) ans = (ans + dp[n][j][k]) % mod;
			}
		}
	}
	cout << ans % mod;
	return 0;
}