Project Euler 684 Inverse Digit Sum

Posted on | | 阅读数 次
Words count in article: 757 | Reading time ≈ 3

开启传送门

题目描述

Define $s(n)$ to be the smallest number that has a digit sum of $n$. For example $s(10)=19$.

Let $S(k)=\sum_{n=1}^k s(n)$. You are given $S(20)=1074$.

Further let $f_i$ be the Fibonacci sequence defined by $f_0=0,f_1=1$ and $f_i=f_{i−2}+f_{i−1}$ for all $i≥2$.

Find $\sum_{i=2}^{90} S(f_i)$. Give your answer modulo $1\ 000\ 000\ 007$.

题意

定义 $s(n)$ 表示最小的数位和为 $n$ 的整数，例如 $s(10) = 19$。

并定义 $S(k) = \sum_{n=1}^k s(n)$ ，例如 $S(20) = 1074$ 。

此外定义 $f_i$ 为fibonacci第 $n$ 项。

求 $\sum_{i=2}^{90} S(f_i) % 1\ 000\ 000\ 007$ 。

分析

首先我们有，$s(n)$ 的后缀显然是一串 $9$ ，前缀是某一个数字或者空。这样为最大。

然后一个简单的想法是，我们诸位统计答案，对于每一位来说，显然是存在 $1\rightarrow 9$ 。然后剩下的这个位置一定全是 $9$ 。这样可以统计出答案，但是我们发现，数据量太大了。$o(n)$ 的显然不太够。

我的做法是，我把每个数字都 $+1$ ，这样做的好处是，每一位一定是$1\rightarrow9$ 。然后后面的位数就是一个等比数列，然后稍微处理一下前面几位就可以了。

简单画个示意图，假设 $n = 20$。

老做法是这样：

百位 十位 个位
$0$ $0$ $1\rightarrow9$
$0$ $1\rightarrow 9$ $9$
$1\rightarrow 2$ $9$ $9$

然后我们诸位统计，答案的计算表达式大概是这样：${\sum_{i=1}^9 1 + 9(n-9)} + {\sum_{i=1}^9 + 9(n-18)}10 + {\sum_{i=1}^2}*100$

新做法是每个数 $+1$ ，然后补一个 $1$ 然后总答案 $-(n+1)$ 。补 $1$ 后：

百位 十位 个位
$0$ $0$ $1\rightarrow9$
$0$ $1\rightarrow 9$ $0$
$1\rightarrow 3$ $0$ $0$

然后对于后缀是一个公比为 $10$ 的等比数列。可以直接统计：

$45(1+10) + \sum_{i=1}^{3}100 - (20+1)$

代码

给大佬递上我奇丑无比的代码　(/ω＼)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
inline int add(long long a,long long b) {a%=mod, b%=mod;return (a+b+mod)%mod;}
inline int mul(long long a,long long b) {return a*b%mod;}
inline int qpow(long long a, long long b) {/*{{{*/
	int ret = 1;
	while(b) {
		if(b&1) ret = mul(ret, a);
		a = mul(a,a);
		b>>=1;
	}
	return ret;
}/*}}}*/
inline int inv(long long a) { return qpow(a, mod-2); }
long long num[100];
long long S(long long a) {
	long long ret = 0;
	ret = add(ret, mul(45, mul(inv(9), add(qpow(10, a/9), -1))));
	long long buf = a%9+1;
	ret = add(ret, mul(mul(buf, buf+1), mul(inv(2), qpow(10, a/9))));
	ret = add(ret, -a-1);
	return ret;
}
void init_num() {/*{{{*/
	num[1] = 1;
	cout<<"f_1 = "<<num[1]<<endl;
	for(int i = 2;i<=90;i++) {
		num[i] = num[i-1] + num[i-2];
		cout<<"f_"<<i<<" = "<<num[i]<<endl;
	}
}/*}}}*/
long long ans[100];
int main() {
	init_num();
	for(int i = 2;i<=90;i++) {
		ans[i] = add(ans[i-1],S(num[i]));
		cout<<"sum of S(f_"<<i<<") = "<<ans[i]<<endl;
	}
	return 0;
}