题目684：颠倒数位和

永恒的蓝色梦想

这个标题难搞哦……

                               
登录/注册后可看大图

                               
登录/注册后可看大图

_2_

woc......
一个初中学历的学生表示不懂

代号-K

i = 10时 结果：8042614
提供个思路，可以用python 跑一下

1. void getInverseDigitSum(int start, int stop, int *sum){
   
2.     int i = start+1;
   
3.     int temp1, temp2;
   
4.     while(i <= stop){
   
5.         temp1 = (i+1) % 9;
   
6.         temp2 = (i+1) / 9;
   
7.         if(temp1 == 0){
   
8.             *sum += 9*(int)pow(10,temp2-1)-1;
   
9.         }else{
   
10.             *sum += temp1*(int)pow(10,temp2)-1;
    
11.         }
    
12.         i++;
    
13.     }
    
14. }
    
15. 
    
16. void getFibonacci(int flag, int *array){
    
17.    int a = 0;
    
18.    int b = 1;
    
19.    int c;
    
20.    int i = 2;
    
21.    array[0] = 0;
    
22.    array[1] = 1;
    
23.    while(i < flag){
    
24.        c = a;
    
25.        a = b;
    
26.        b = c + a;
    
27.        array[i++] = b;
    
28.    }
    
29. }
    
30. 
    
31. int main(int argc, char *argv[]){
    
32.     int answer = 1;
    
33.     int sum = 1;
    
34.     int array[100] = {0};
    
35.     getFibonacci(21, array);
    
36.     for(int i = 2; i < 10; i++){
    
37.         getInverseDigitSum(array[i],array[i+1],&answer);
    
38.         sum += answer;
    
39.         printf("%d\n",sum);
    
40.     }
    
41.     return 0;
    
42. }

复制代码

永恒的蓝色梦想

代号-K 发表于 2020-4-24 23:09
i = 10时 结果：8042614
提供个思路，可以用python 跑一下

大佬牛皮

guosl

令k=n/9，r=n%9，则s(n)=r*10^k+9..(k个9)...9。应用这个思路加上9..(k个9)...9=10^k - 1 以及等比级数求和与快速幂的综合可以计算出最终结果：922058210，耗时不到1秒。

1. //答案：922058210
   
2. #include <iostream>
   
3. using namespace std;
   
4. 
   
5. const long long MOD = 1000000007ll;
   
6. 
   
7. long long f[100];
   
8. 
   
9. long long qpow(long long k)
   
10. {
    
11.   if (k == 0)
    
12.     return 1LL;
    
13.   else if (k == 1)
    
14.     return 10LL;
    
15.   long long t = 0;
    
16.   if ((k & 1) == 0)
    
17.   {
    
18.     t = qpow(k >> 1);
    
19.     t = t*t;
    
20.   }
    
21.   else
    
22.   {
    
23.     t = qpow(k - 1);
    
24.     t *= 10LL;
    
25. 
    
26.   }
    
27.   t %= MOD;
    
28.   return t;
    
29. }
    
30. 
    
31. int main(void)
    
32. {
    
33.   f[0] = 0;
    
34.   f[1] = 1;
    
35.   for (int i = 2; i < 100; ++i)
    
36.     f[i] = f[i - 1] + f[i - 2];
    
37.   long long lTS = 1, nS = 1;
    
38.   for (int i = 3; i <= 16; ++i)
    
39.   {
    
40.     long long tS = 0, t = 0;
    
41.     for (int j = int(f[i - 1]) + 1; j <= int(f[i]); ++j)
    
42.     {
    
43.       int k = int(j / 9), r = int(j % 9);
    
44.       t = qpow(k);
    
45.       t *= (r + 1);
    
46.       --t;
    
47.       tS += t;
    
48.     }
    
49.     nS += tS;
    
50.     lTS += nS;
    
51.   }
    
52.   lTS %= MOD;
    
53.   for (int i = 17; i <= 90; ++i)
    
54.   {
    
55.     long long k1 = (f[i - 1] + 1) / 9;
    
56.     long long k2 = f[i] / 9;
    
57.     int r = int((f[i - 1] + 1) % 9);
    
58.     long long tS = 0, t = 0;
    
59.     for (int r1 = r; r1 < 9; ++r1)
    
60.     {
    
61.       t = qpow(k1);
    
62.       t *= (r1 + 1);
    
63.       --t;
    
64.       if (t < 0)
    
65.         t += MOD;
    
66.       t %= MOD;
    
67.       tS += t;
    
68.       tS %= MOD;
    
69.     }
    
70.     ++k1;
    
71.     if (k2 > k1)
    
72.     {
    
73.       t = qpow(k2 - k1);
    
74.       --t;
    
75.       if (t < 0)
    
76.         t += MOD;
    
77.       long long t1 = qpow(k1);
    
78.       t *= t1;
    
79.       t %= MOD;
    
80.       t *= 5;
    
81.       t -= 9 * (k2 - k1);
    
82.       if (t < 0)
    
83.         t += MOD;
    
84.       t %= MOD;
    
85.       tS += t;
    
86.       tS %= MOD;
    
87.     }
    
88.     r = int((f[i]) % 9);
    
89.     for (int r1 = 0; r1 <= r; ++r1)
    
90.     {
    
91.       t = qpow(k2);
    
92.       t *= (r1 + 1);
    
93.       --t;
    
94.       if (t < 0)
    
95.         t += MOD;
    
96.       t %= MOD;
    
97.       tS += t;
    
98.       tS %= MOD;
    
99.     }
    
100.     nS += tS;
     
101.     nS %= MOD;
     
102.     lTS += nS;
     
103.     lTS %= MOD;
     
104.   }
     
105.   cout << lTS << endl;
     
106.   return 0;
     
107. }
     

复制代码