- 2025七月DAY5
T6
- @ 2025-7-19 16:06:42
/*
假设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 条评论
-
root LV27 至高道祖 LV 1 SU @ 2025-7-19 16:59:32第50行
if(!mp.count({x, y})) //是障碍点不转移 -
@ 2025-7-19 16:32:03老师你的这份代码好像RE了

- 1