Luogu

算法

发现$S(i)$可以在常数时间内求出。预处理出$s[1]$~$s[9]$会跑的更快。

然后将$H(n)$展开，发现$H(n)=min\{n,S(n),S(S(n)),S(S(S(n))),...\}$。

然后就可以递归搞，但是边界不好找。

仔细一想，发现这个东西会出现环。

那么在一个数访问两次时，说明成环了，直接返回即可。

然后再加上记忆化，即可AC本题。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
#define MOD 10000007
using namespace std;

inline int min_(const int a,const int b) { if (a<b) return a; else return b; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int s[4000010];

inline void gets(int i) {
    if (s[i]) return;
    re int m=i;
    while (m) {
        s[i]+=s[m%10];
        m/=10;
    }
}

int h[4000010];
int vis[4000010];

inline int geth(int i) {
    if (h[i]) return h[i];
    if (vis[i]==2) return i;
    gets(i); ++vis[i];
    h[i]=min_(min_(i,s[i]),geth(s[i]));
    --vis[i];
    return h[i];
}

int main() {
    int k=read(),A=read(),B=read();
    for (re int i=1;i<=9;++i) {
        s[i]=1;
        for (re int j=1;j<=k;j++) s[i]*=i;
    }
    h[1]=1;
    long long ans=0;
    for (re int i=A;i<=B;++i) (ans+=geth(i))%=MOD;
    printf("%lld\n",ans);
    return 0;
}