/*
假设t1,t2,t3分别是三种跃迁方式的次数
(x,y) =>  (x + t1*A + t2*C + t3*E, y + t1*B ...)

初始化: 
dp[0][0][0] = 1
dp[i][u][v]的方案数
w = i - u - v; //第三种方式
dp[i][u][v] = dp[i-1][u][v]
如果这一次跃迁是第一种方式:
dp[i][u][v] += dp[i-1][u - 1][v]
如果第二种方式:
dp[i][u][v] += dp[i-1][u][v-1]

如果是障碍点 则不用转移

结果是什么?
dp[n][]
*/

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

const int N = 310, mod = 998244353;
int n, m, a, b, c, d, e, f;
long long ans, dp[N][N][N];
map<pair<long long, long long>, bool> mp; //是否是被标记的不能走的坐标

int main()
{
	cin >> n >> m >> a >> b >> c >> d >> e >> f;
	while(m --)
	{
		int x, y;
		cin >> x >> y;
		mp[{x, y}] = 1;
	}
	
	dp[0][0][0] = 1;
	for(int i = 1; i <= n; i++)
		for(int u = 0; u <= i; u++)
			for(int v = 0; u + v <= i; v ++)
			{
				int w = i - v - u;
				//三种跃迁方式:u v w
				long long x = 1ll*u*a + 1ll*v*c + 1ll*w*e;
				long long y = 1ll*u*b + 1ll*v*d + 1ll*w*f;
				//if(!mp[{x, y}]) //是障碍点不转移

        if(!mp.count({x, y})) //是障碍点不转移
				{
					//选第三种方式
					dp[i][u][v] = dp[i-1][u][v];
					if(u) dp[i][u][v] = (dp[i][u][v] + dp[i-1][u - 1][v]) % mod;
					if(v) dp[i][u][v] = (dp[i][u][v] + dp[i-1][u][v - 1]) % mod ;
					
					if(i == n)	
						ans = (ans + dp[n][u][v]) % mod;
				}
			}
	cout << ans;
}

2 条评论

  • @ 2025-7-19 16:59:32

    第50行 if(!mp.count({x, y})) //是障碍点不转移

    • @ 2025-7-19 16:32:03

      老师你的这份代码好像RE了

      • 1