题解：AT_abc006_2 [ABC006B] トリボナッチ数列

Eric1030 · 2025-02-05 10:20:22 · 题解

题目传送门

题目大意

现有一个数列 a，规定 a_1 = 0，a_2=0，a_3=1，设这个数列的第 i 项为 a_i，当 4 \le i 时 ，a_i=a_{i-1}+a_{i-2}+a_{i-3}。

输入一个数 n，输出这个数列的第 n 项。

思路

这是一道与斐波那契数列很像的题目。只不过这道题的运算规则是 a_i=a_{i-1}+a_{i-2}+a_{i-3}，而正常的斐波那契数列的公式应该是 a_i=a_{i-1}+a_{i-2}。

我们只要把 n 输入进来后，按照题目所要求的规则进行计算，每算完一次就要把这一次的结果 \bmod 10007，最后输出 a_n 就可以了。

AC 代码

#include <bits/stdc++.h>
using namespace std;
long long n, a[1000005];
int main()
{
    //输入数据
    cin >> n;
    //按照题目规则把a[1]、a[2]、a[3]赋值
    a[1] = 0;
    a[2] = 0;
    a[3] = 1;
    for (int i = 4;i <= n;i++)//a[1]~a[3]的值已经有了，所以循环从4开始
    {
        a[i] = a[i - 1] + a[i - 2] + a[i - 3];//按照规则进行计算a[i]
        a[i] %= 10007;//记得mod 10007
    }
    cout << a[n];//输出这个数列的第n项
    return 0;//结束！
}