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]?(a[j]+b[j])$

如果從第 $i$ 間木屋去小島走 $B$ 橋，去第 $j$ 間木屋只可以走 $A$ 橋

方案數為 $b[i]?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]?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;
}