ABC300E逆元哈希期望DP倒搜

#include <bits/stdc++.h>
using namespace std;
long long n, m;
int i, j, k, ans, mo=998244353;
map <long long, int> f;
int mi(long long a, int b){
    int s=1;
    while(b){
        if(b&1) s = s*a%mo;
        b /= 2, a = a*a%mo;
    }
    return s;
}//快速幂
int dfs(long long s){
    if(s > n) return 0;
    if(s == n) return 1;
    long long i, p=0;
    if(f.find(s) != f.end()){
        return f[s];//map记忆化
    }
    for(i=2; i<=6; i++){
        p += dfs(s*i) * m;
    }//公式优化：fs = (f2+f3+f4+f5+f6)/5
    return f[s] = p % mo;
}
int main(){
    scanf("%lld", &n);
    m = mi(5, mo-2), ans = dfs(1);
    printf("%d\n", ans);
    return 0;
}