题目传送门
题目背景
暴龙爱吃火锅。
题目描述
定义 \(S(x)\) 表示 \(x\) 的每一位的数字之和，例如：\(S(14)=1+4=5\)，\(S(114514)=1+1+4+5+1+4=16.\)
另外，定义 \(fib(x)\) 代表斐波那契数列的第 \(x\) 项，具体地：
\[fib(1)=fib(2)=1,\ fib(x)=fib(x-1)+fib(x-2)\ (x≥3). \]现在给定 \(n\)，求出下式的值，其中 \(\bmod 9\) 表示对 \(9\) 取余数：
\[(S(fib(1))+S(fib(2))+S(fib(3))+...+S(fib(n))) \bmod 9. \]输入格式
第一行一个整数 \(T\)。
接下来 \(T\) 组问询，每次一个整数 \(n\)。
输出格式
\(T\) 行，每行一个整数代表答案。
样例 #1
样例输入 #1
3
7
14
114514
样例输出 #1
6
5
8
提示
【样例解释】
对于第一组询问，\(n=7\)，答案为：
\[\begin{aligned} & \ \ \ \ \ (S(fib(1))+S(fib(2))\ldots+S(fib(6))+S(fib(7)))\bmod 9 \\ & =(1+1+2+3+5+8+(1+3))\bmod 9 \\ & =6. \end{aligned} \]【数据范围】
「本题采用捆绑测试」
- \(\texttt{Subtask 1(10 pts)：}T=1,\ n\le 10\)；
- \(\texttt{Subtask 2(30 pts)：}T=10^2,\ n\le 10^3\)；
- \(\texttt{Subtask 3(60 pts)：}\)无特殊限制。
对于 \(100\%\) 的数据，满足 \(1\le T\le 10^5,\ 1\le n\le 10^6\)。
题目分析：
我们已经知道题目是让我们求从 \(1\) 到 \(n\) 这一串数据被称为 \(a_i\) 让我们求第 \(_i\) 项的斐波那契数列的值的各位相加，如果直接用暴力解会变成这样（编者一开始就是这么写的...）
int kkks(int x) {
int b = x, sum = 0;
while (b) sum += b % 10, b /= 10;
return sum;
}
int fib(int x) {
int f[MAX];
f[1] = 1, f[2] = 1;
if (x == 1 || x == 2)return 1;
for (int i = 3; i <= x; i++) f[i] = f[i - 1] + f[i - 2];
return f[x];
}
这两个函数是分别求第 \(_i\) 项斐波那契数列的值和求各位数之和的函数，然后暴力一个一个计算
for (int i = 1; i <= n; i++) {
sum = 0;
int x = read();
for (int j = 1; j <= x; j++) sum += kkks(fib(j));
write(sum % 9);
puts("");
}
写到这里，你可以得 \(10\) 分，我们再反过来看题，斐波那契数列的第 \(7\) 项是 \(13\) 而我们要求的各位数之和是 \(4\) ，\(13 ~mod ~9==4\)，我们惊奇的发现了这个规律，再继续验证 第 \(8\) 项是 \(21\), \(21\) \(~mod ~\) \(9==3\) 发现这个规律是行的通的，所以我们现在不需要这两个函数了
f[1] = 1, f[2] = 1;
while (n--) {
sum = 2;
int x = read();
for (int j = 3; j <= x; j++) f[j] = (f[j - 1] + f[j - 2]) % 9, sum += f[j], sum %= 9;
write(sum);
puts("");
}
我们可以直接这样写，在计算的时候就将其值 \(~mod ~9\) 可以缩短时间，但每一组数据都要算一次，这样只能得 \(40\) 分，所以我们可以先来一波预处理
f[1] = 1, f[2] = 1;
sum[1] = 1, sum[2] = 2;
for (int j = 3; j <= 1000001; j++) {
f[j] = (f[j - 1] + f[j - 2]) % 9;
sum[j] = (f[j] + sum[j - 1]) % 9;
}
while(n--)
{
x = read();
write(sum[x]);
puts("");
}
像这样写，我们直接把最大范围的值算出来了，就读一个数直接输出就对了，大大增加效率。（所以这道题是真的有坑啊...）
最后附上 AC Code
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
const int MAX = 1000010;
int read() {
int f = 1, x = 0;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-')f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
void write(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9)write(x / 10);
putchar(x % 10 + '0');
}
int n = read(), sum[MAX], x;
int f[MAX];
signed main() {
f[1] = 1, f[2] = 1;
sum[1] = 1, sum[2] = 2;
for (int j = 3; j <= 1000001; j++) {
f[j] = (f[j - 1] + f[j - 2]) % 9;
sum[j] = (f[j] + sum[j - 1]) % 9;
}
while(n--)
{
x = read();
write(sum[x]);
puts("");
}
return 0;
}