模拟赛

首先考虑暴力 DP。

设 $f_{i}$ 表示 $i$ 的期望步数，则有转移

$$f_{i}=1+\sum_{j=1}^i \frac{f_{i\mod j}}{i}$$

考虑怎么快速计算后面的东西。

结论：$a \mod b=a-\lfloor \frac {a}{b} \rfloor\times b$。

考虑根号分治。

对于 $j < \sqrt i$，我们直接暴力计算，这部分是 $O(\sqrt n)$ 的。

对于 $j \ge \sqrt i$，可以发现 $\lfloor \frac {i}{j} \rfloor \le \sqrt i$。

设 $d=\lfloor \frac {i}{j} \rfloor$，其对应区间为 $[l,r]$。

设 $i=p+k\times d$，则

$$\begin{align*} \sum_{j=1}^i f_{i \mod j} &= \sum_{n=l}^r f_{i-n\times d} \\ &=\sum_{q=k-l}^{k-r} f_{p+q\times d} \\ &=\sum_{v=p+(k-l)\times d}^{p+(k-r)\times d} f_{v} \end{align*}$$

这是一个区间求和的形式，可以前缀和优化。

所以对每一个 $d$ 都维护一个前缀和即可。

复杂度 $O(n\sqrt n)$

实现时，可以对每个 $i$ 做一次整除分块，然后做上面说的东西。

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=2e5+10,V=2e5,M=450,mod=998244353;
int f[maxn],inv[maxn];
int s[M][maxn];
inline void pre(){
    inv[0]=inv[1]=1;
    for(re int i=2;i<=V;++i) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
}
inline void init(){
    pre();
    for(re int i=1;i<=V;++i){
        for(re int l=1,r,d;l<=i;l=r+1){
            r=i/(i/l);
            d=i/l;
            if(d>=M) for(re int j=l;j<=r;++j) f[i]=(f[i]+f[i%j])%mod;
            else{
                int mo=i%d,k=i/d;
                int L=(k-r)*d+mo,R=(k-l)*d+mo;
                if(L-d<0) f[i]=(f[i]+s[d][R]%mod)%mod;
                else f[i]=(f[i]+(s[d][R]-s[d][L-d])%mod+mod)%mod;
            }	
        }
        f[i]=(f[i]*inv[i]+1)%mod;
        for(re int d=1;d<M;++d){
            if(i<=d) s[d][i]=f[i];
            else s[d][i]=(s[d][i-d]+f[i])%mod;
        }
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    init();
    int n,T;cin>>T;while(T--) cin>>n,cout<<f[n]<<'\n';
    return 0;
}