[luogu 1660]数位平方和

题目描述

定义S(n)表示n的各个数位的k次方的和。定义$H(n)=min{n,S(n),H(S(n))}$。

求$$ $_{i=A} ^{B} {H(i)} mod 10000007$$$

输入输出格式

输入格式：

一行三个数K、A、B。

【数据规模】

对于20%的数据，满足1≤A、B≤50;

对于100%的数据，满足1≤A、B≤10^6，K≤6.

输出格式：

B 一个数∑H(i) mod 10000007

i=A

输入输出样例

输入样例#1：

2 1 5

输出样例#1：

题解：

很暴力的解法，把每一个数都看作一个点，那么我们可以从一个数的每一位来得到它的下一个数，并向下一个数连一条有向边。

这样我们就得到了一个有向有环图，那么题意就变成了从一个点开始，一直向下走，所经过的所有点的最小值（包括环）。

考虑tarjan缩点，统计一下每一个强连通分量（也就是环）上的最小值。

很显然环上是没有出边的，我们将所有边反向，从入度为0的分量开始拓扑，一路上不断更新路径上的最小值，那么这样就统计出来了每一个点一直向下走，所经过的所有点的最小值。

然后把题目要求的点加在一起输出就可以了。（我用的是前缀和）

另外不要怀疑这道题会因为点过多而超时，当k=6时，以1～100000分别为起点，所经过的数的最大值是3188...（反正是个七位数），还是可以承受的。

时空复杂度O（能过）

 1 //Never forget why you start
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<algorithm>
 8 #include<queue>
 9 #define mod (10000007)
10 using namespace std;
11 int n,t[10];
12 bool vis[3200005];
13 int suan(int x){
14   int ans=0;
15   while(x){
16     ans+=t[x%10];
17     x/=10;
18   }
19   return ans;
20 }
21 int to[3200005];
22 void dfs(int r){
23   if(vis[r])return;
24   vis[r]=1;
25   int Next=suan(r);
26   to[r]=Next;
27   dfs(Next);
28 }
29 int dfn[3200005],low[3200005],sccno[3200005],scc,dfscnt,mmin[3200005];
30 int s[3200005],top;
31 void tarjan(int r){
32   dfn[r]=low[r]=++dfscnt;
33   s[++top]=r;
34   int y=to[r];
35   if(!dfn[y]){
36     tarjan(y);
37     low[r]=min(low[r],low[y]);
38   }
39   else if(!sccno[y])low[r]=min(low[r],dfn[y]);
40   if(low[r]==dfn[r]){
41     scc++;
42     int x;
43     while(1){
44       x=s[top--];
45       sccno[x]=scc;
46       mmin[scc]=min(x,mmin[scc]);
47       if(x==r)break;
48     }
49   }
50 }
51 struct node{
52   int next,to;
53 }edge[3200005];
54 int size=0;
55 void putin(int from,int to){
56   size++;
57   edge[size].to=to;
58   edge[size].next=dfn[from];
59   dfn[from]=size;
60 }
61 void bfs(){
62   queue<int>mem;
63   for(int i=1;i<=scc;i++)if(!s[i])mem.push(i);
64   while(!mem.empty()){
65     int x=mem.front();mem.pop();
66     for(int i=dfn[x];i!=-1;i=edge[i].next){
67       int y=edge[i].to;
68       mmin[y]=min(mmin[y],mmin[x]); 
69       s[y]--;
70       if(!s[y])mem.push(y);
71     }
72   }
73 }
74 int main(){
75   int i,j;
76   scanf("%d",&n);
77   memset(mmin,127/3,sizeof(mmin));
78   for(i=0;i<=9;i++)t[i]=pow(i,n);
79   for(i=1;i<=1000000;i++){
80     dfs(i);
81   }
82   for(i=1;i<=3200000;i++)
83     if(!dfn[i])tarjan(i);
84   memset(dfn,-1,sizeof(dfn));
85   memset(s,0,sizeof(s));
86   for(i=1;i<=3200000;i++)
87     if(sccno[i]!=sccno[to[i]])putin(sccno[to[i]],sccno[i]),s[sccno[i]]++;
88   bfs();
89   low[0]=0;
90   for(i=1;i<=1000000;i++){
91     low[i]=mmin[sccno[i]];
92     (low[i]+=low[i-1])%=mod;
93   }
94   int l,r;
95   scanf("%d%d",&l,&r);
96   printf("%d
",(low[r]-low[l-1]+mod)%mod);
97   return 0;
98 }