永恒的蓝色梦想 发表于 2020-4-24 09:45:28

题目684：颠倒数位和

本帖最后由 永恒的蓝色梦想 于 2020-4-24 09:52 编辑

这个标题难搞哦……{:10_266:}
https://s1.ax1x.com/2020/04/24/J0h7OP.png
https://s1.ax1x.com/2020/04/24/J05wvR.png

_2_ 发表于 2020-4-24 10:36:02

woc......
一个初中学历的学生表示不懂{:10_266:}

代号-K 发表于 2020-4-24 23:09:28

本帖最后由 代号-K 于 2020-4-24 23:12 编辑

i = 10时 结果：8042614
提供个思路，可以用python 跑一下{:10_249:}{:10_256:}
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;
   array = 1;
   while(i < flag){
       c = a;
       a = b;
       b = c + a;
       array = b;
   }
}

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

永恒的蓝色梦想 发表于 2020-4-25 06:33:13

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

大佬牛皮{:10_266:}

guosl 发表于 2021-11-28 10:25:15

本帖最后由 guosl 于 2021-11-28 10:27 编辑

令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;

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;
f = 1;
for (int i = 2; i < 100; ++i)
    f = f + f;
long long lTS = 1, nS = 1;
for (int i = 3; i <= 16; ++i)
{
    long long tS = 0, t = 0;
    for (int j = int(f) + 1; j <= int(f); ++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 + 1) / 9;
    long long k2 = f / 9;
    int r = int((f + 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) % 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;
}
页: [1]
查看完整版本: 题目684：颠倒数位和