这份代码记忆化直接看 dp[n] 是否存在，本地就 T 飞，1min 都运行不完。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll ksm(ll a,ll b)
{
    ll ret=1;
    while(b)
    {
        if(b&1)ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}
ll inv(ll a)
{
    return ksm(a,mod-2);
}
ll N;
map<ll,ll> dp;
ll inv5;
ll dfs(ll n)
{
    if(n>N)return 0;
    if(n==N)return 1;
    if(dp[n]!=0)return dp[n];
//	printf("n = %lld\n",n);
    dp[n]=(dfs(n*2ll)+dfs(n*3ll)+dfs(n*4ll)+dfs(n*5ll)+dfs(n*6ll))*inv5%mod;
    return dp[n];
}
int main()
{
    inv5=inv(5);
    scanf("%lld",&N);
    printf("%lld",dfs(1));
    return 0;
}

而这份换成了使用 map.count，跑得飞快。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll ksm(ll a,ll b)
{
    ll ret=1;
    while(b)
    {
        if(b&1)ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}
ll inv(ll a)
{
    return ksm(a,mod-2);
}
ll N;
map<ll,ll> dp;
ll inv5;
ll dfs(ll n)
{
    if(n>N)return 0;
    if(n==N)return 1;
    if(dp.count(n))return dp[n];
//	printf("n = %lld\n",n);
    dp[n]=(dfs(n*2ll)+dfs(n*3ll)+dfs(n*4ll)+dfs(n*5ll)+dfs(n*6ll))*inv5%mod;
    return dp[n];
}
int main()
{
    inv5=inv(5);
    scanf("%lld",&N);
    printf("%lld",dfs(1));
    return 0;
}

这是怎么回事