[abc300_e]Dice Product 3
很明显，概率是由其因子转移而来的，设\(dp[i]\)表示结果为i的概率，则有转移方程：
\[dp_i=\sum_{j=2}^6 dp_{\frac{i}{j}}\times \frac{1}{5}\times[i \bmod j =0] \]为什么是从二开始？因为乘1结果不变，不影响概率，所以只有5中情况，因为n很大，所以可以用记忆化搜索。
分数取模写的很抽象，形象的可以理解为输出\(P\times Q^{-1} \ (\bmod\ 998244353)\)
代码：
#include<cstdio>
#include<map>
#define ll long long
using namespace std;
const int m=998244353;
ll n,d;
map<ll,ll> mp;
ll qpow(ll x,int y)
{
ll res=1;
while(y)
{
if(y&1) res=res*x%m;
x=x*x%m;
y>>=1;
}
return res;
}
void dfs(ll x)
{
if(mp[x]) return;
for(int i=2;i<=6;i++)
{
if(x%i!=0) continue;
dfs(x/i);
mp[x]=(d*mp[x/i]%m+mp[x])%m;
}
}
int main()
{
scanf("%lld",&n);
d=qpow(5,m-2);
mp[1]=1;
dfs(n);
printf("%lld",mp[n]);
return 0;
}
[abc263_e]Sugoroku 3
因为转移存在环，所以无法直接正推，考虑逆推，设\(dp[i]\)表示当前在i，期望还需走的步数，易得转移方程：
\[dp_i=\frac{\sum_{j=i}^{i+a_i} (dp_j+1)}{a_i+1} \]即
\[dp_i=\frac{\sum_{j=i+1}^{i+a_i}dp_j}{a_i}+\frac{a_i+1}{a_i} \]注意，因为在转移时也要掷一次，所以在列第一个式子时要+1，不然会推出某些奇怪的东西
代码：
#include<cstdio>
#define ll long long
using namespace std;
const int m=998244353;
int n,a[200005];
ll dp[200005],sum[400005];
ll qpow(ll x,int y)
{
ll res=1;
while(y)
{
if(y&1) res=res*x%m;
x=x*x%m;
y>>=1;
}
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d",&a[i]);
}
for(int i=n-1;i>0;i--)
{
dp[i]=((sum[i+1]-sum[i+a[i]+1])%m*qpow(a[i],m-2)%m+(a[i]+1)*qpow(a[i],m-2)%m)%m;
sum[i]=(sum[i+1]+dp[i])%m;
//printf("%d ",dp[i]);
}
printf("%lld ",dp[1]);
}