[ABC275E] Sugoroku 4 题解
FFTotoro
·
·
题解
前言
这题生动地展现了飞行棋最后几步的经典画面，赛时瞎搞居然搞出来了。同学严重怀疑出题人飞行棋输多了才想到的这一题
解法
本题需要使用动态规划算法。
我们令 f_{i,j} 为第 i 轮转转盘的时候，走到格子 j 的概率（易得边界条件 f_{0,0}=1）；令 s(x,y) 为从 x 格子开始，转盘转到了 y 后走到的格子，根据游戏规则有：
s(x,y)=\begin{cases}2n-x-y&x+y>n\\x+y &\operatorname{otherwise}\end{cases}
因为转盘转到 1 至 M 的概率相同，所以易得：
除法时用乘法逆元求解即可，最终答案即为 $\sum\limits_{i=1}^Kf_{i,N}$。
放代码：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p=998244353;
int n,f[1001][1001];
int qpow(int a,int b){
int r=1;
while(b){
if(b&1)r=r%p*a%p;
a=a%p*a%p; b>>=1;
}
return r;
}
int inv(int a,int b){
return a*qpow(b,p-2)%p;
} // 逆元
int s(int x,int y){
return x+y>n?(n<<1ll)-x-y:x+y;
} // 判断 x 走 y 步后会到哪
main(){
ios::sync_with_stdio(false);
int m,k,c=0; cin>>n>>m>>k; f[0][0]=1; // 初始化
for(int i=1;i<=k;i++){
for(int j=0;j<n;j++)
for(int r=1;r<=m;r++)
(f[i][s(j,r)]+=inv(f[i-1][j],m))%=p; // 状态转移
(c+=f[i][n])%=p; // 求和
}
cout<<c<<endl;
return 0;
}
```