题解 P1660 【数位平方和】

_Lemon_ · 2017-11-08 21:20:37 · 题解

先膜拜一下楼下的大神,可伶的我今天考试果断爆零了

不多BB,我们进入正题吧

首先如果小伙伴们直接打的递归的话就会发现会陷入死循环,

那么我们就想到了记忆化搜索,然后环上的点的H值就是环上最小的值

如果某个点访问了两次,就说明出现了环

但这时我们还需要再绕着环走一遍(也就是访问到第三遍)

因为只走一圈的话就会导致这个点没办法跟新到环上最小值

然后大家可以先处理出来1-9的k次方,让程序跑得快一点.

然后上代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
const int mod=10000007;
long long h[4000005],s[4000005],small;
int lemon[10],k,cnt;
int vis[4000005];
long long q[4000005];
void solve()
{    
    for(int i=1;i<=9;i++)
    {
        int w=1;
        for(int j=1;j<=k;j++)
            w*=i;
        lemon[i]=w;
    }
}
long long get_s(int x)
{
    if(s[x]) return s[x];
    int w,all=0;
    while(x>0)
    {
        w=x%10;
        all+=lemon[w];
        x/=10;
    }
    return s[x]=all;
}
long long get_h(long long x)
{
    if(h[x]) return h[x];
    if(vis[x]==2) return x;
    vis[x]++;
    s[x]=get_s(x);
    h[x]=min(x,min(s[x],get_h(s[x])));
    vis[x]--;
    return h[x];
}
int main()
{
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    int a,b;
    long long ans=0;
    cin>>k>>a>>b;
    solve();
    h[1]=1;
    for(int i=a;i<=b;i++)
    {
        cnt=0;    
        ans+=get_h(i);
        ans%=mod;
    }
    cout<<ans;
    return 0;
}