题目684：颠倒数位和

永恒的蓝色梦想

这个标题难搞哦……

                               
登录/注册后可看大图

                               
登录/注册后可看大图

_2_

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

代号-K

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

void getInverseDigitSum(int start, int stop, int *sum){
    int i = start+1;
    int temp1, temp2;
    while(i <= stop){
        temp1 = (i+1) % 9;
        temp2 = (i+1) / 9;
        if(temp1 == 0){
            *sum += 9*(int)pow(10,temp2-1)-1;
        }else{
            *sum += temp1*(int)pow(10,temp2)-1;
        }
        i++;
    }
}

void getFibonacci(int flag, int *array){
   int a = 0;
   int b = 1;
   int c;
   int i = 2;
   array[0] = 0;
   array[1] = 1;
   while(i < flag){
       c = a;
       a = b;
       b = c + a;
       array[i++] = b;
   }
}

int main(int argc, char *argv[]){
    int answer = 1;
    int sum = 1;
    int array[100] = {0};
    getFibonacci(21, array);
    for(int i = 2; i < 10; i++){
        getInverseDigitSum(array[i],array[i+1],&answer);
        sum += answer;
        printf("%d\n",sum);
    }
    return 0;
}

永恒的蓝色梦想

代号-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秒。

//答案：922058210
#include <iostream>
using namespace std;

const long long MOD = 1000000007ll;

long long f[100];

long long qpow(long long k)
{
  if (k == 0)
    return 1LL;
  else if (k == 1)
    return 10LL;
  long long t = 0;
  if ((k & 1) == 0)
  {
    t = qpow(k >> 1);
    t = t*t;
  }
  else
  {
    t = qpow(k - 1);
    t *= 10LL;

  }
  t %= MOD;
  return t;
}

int main(void)
{
  f[0] = 0;
  f[1] = 1;
  for (int i = 2; i < 100; ++i)
    f[i] = f[i - 1] + f[i - 2];
  long long lTS = 1, nS = 1;
  for (int i = 3; i <= 16; ++i)
  {
    long long tS = 0, t = 0;
    for (int j = int(f[i - 1]) + 1; j <= int(f[i]); ++j)
    {
      int k = int(j / 9), r = int(j % 9);
      t = qpow(k);
      t *= (r + 1);
      --t;
      tS += t;
    }
    nS += tS;
    lTS += nS;
  }
  lTS %= MOD;
  for (int i = 17; i <= 90; ++i)
  {
    long long k1 = (f[i - 1] + 1) / 9;
    long long k2 = f[i] / 9;
    int r = int((f[i - 1] + 1) % 9);
    long long tS = 0, t = 0;
    for (int r1 = r; r1 < 9; ++r1)
    {
      t = qpow(k1);
      t *= (r1 + 1);
      --t;
      if (t < 0)
        t += MOD;
      t %= MOD;
      tS += t;
      tS %= MOD;
    }
    ++k1;
    if (k2 > k1)
    {
      t = qpow(k2 - k1);
      --t;
      if (t < 0)
        t += MOD;
      long long t1 = qpow(k1);
      t *= t1;
      t %= MOD;
      t *= 5;
      t -= 9 * (k2 - k1);
      if (t < 0)
        t += MOD;
      t %= MOD;
      tS += t;
      tS %= MOD;
    }
    r = int((f[i]) % 9);
    for (int r1 = 0; r1 <= r; ++r1)
    {
      t = qpow(k2);
      t *= (r1 + 1);
      --t;
      if (t < 0)
        t += MOD;
      t %= MOD;
      tS += t;
      tS %= MOD;
    }
    nS += tS;
    nS %= MOD;
    lTS += nS;
    lTS %= MOD;
  }
  cout << lTS << endl;
  return 0;
}