RainbowDash 的旅行

D RainbowDash 的旅行 - 第七届校赛正式赛 —— 补题

题目大意：

湖中心有一座岛，湖的外围有 $m$ 间木屋（围绕小岛） ，第 $i$ 间木屋和小岛之间有 $a_i$ 座 $A$ 类桥，$b_i$ 座 $B$ 类桥，$A$ 桥有车可以快速通过， $B$ 桥需要步行，速度稍慢。

你计划一次 $n$ 天的旅行，对于每一天，你都需要从当前木屋走到小岛游玩，再走到任何一间木屋（包括出发时所在的木屋），你不想浪费时间在赶路上，于是一天通过的两座桥必须有一座是 $A$ 类桥，起始在 $1$ 号木屋，问旅行 $n$ 天，有多少不同的路线组合？

$1<=n<=1000,1<=m<=100$

$1<=a_i,b_i<=10^4$

思路：

考虑第 $i$ 间木屋到第 $j$ 间木屋有多少种方法

设 $f[i][j]$ 表示第 $i$ 间木屋到第 $j$ 间木屋总方案数

如果从第 $i$ 间木屋去小岛走 $A$ 桥，去第 $j$ 间木屋则可以走 $A$ 桥或者 $B$ 桥

那么方案数为 $a[i]\ast (a[j]+b[j])$

如果从第 $i$ 间木屋去小岛走 $B$ 桥，去第 $j$ 间木屋只可以走 $A$ 桥

方案数为 $b[i]\ast a[j]$

int f[M][M];
for(int i=1;i<=m;i++){
    for(int j=1;j<=m;j++){
        f[i][j]=a[i]*(a[j]+b[j])+b[i]*a[j];
    }
}

有了第 $i$ 间木屋到第 $j$ 间木屋总方案数，可以考虑 $1-n$ 天总方案数的 $dp$ 了

考虑第 $k$ 天到达 第 $1-m$ 间木屋的的方案数

设 $dp[k][j]$ 表示第 $k$ 天到达第 $j$ 间木屋的方案数

对于第 $k$ 天到达第 $j$ 间木屋的方案数，

考虑由第 $k-1$ 天 从 $i(1-n)$ 间木屋转移到第 $j$ 间木屋的方案数：$dp[k][j]+=dp[k-1][i]\ast f[i][j]$

第一天在1号木屋，所以第一天应由$dp[0][1]$ 去转移，所以初始化 $dp[0][1]=1$

int dp[N][M];

for(int k=1;k<=n;k++){
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            dp[k][j]+=dp[k-1][i]*f[i][j];
        }
    }
}

最后统计第 $n$ 天到达第 $1-m$ 间木屋总数即可

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define PII pair<int,int>
#define lowbit(x) x&-x
#define ALL(x) x.begin(),x.end()

const int mod = 998244353;
const int N = 100 + 10;

int f[N][N],dp[1010][N];
int a[N],b[N];
int n,m;


void solve() {
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		cin>>b[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			f[i][j]=a[i]*(a[j]+b[j])%mod+b[i]*a[j]%mod;
			f[i][j]%=mod;
		}
	}
	dp[0][1]=1;
	for(int k=1;k<=n;k++){
		for(int i=1;i<=m;i++){
			for(int j=1;j<=m;j++){
				dp[k][j]+=dp[k-1][i]*f[i][j]%mod;
				dp[k][j]%=mod;
			}
		}
	}
	int ans=0;
	for(int i=1;i<=m;i++){
		ans+=dp[n][i];
		ans%=mod;
	}
	cout<<ans<<'\n';
	
}

signed main() {
	std::ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
//	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}