题目

牛客

解题思路

本题的基本意思就是给你给定一个矩阵：，然后一个数n，n表示矩阵的n次方，这个n代表一个数也就是解密的结果，即为ⁿ的结果的（也是一个矩阵）的左上角数字。
如果该数字小于4就用0补充，如果大于4就只输出最后4位

同时矩阵的乘法公式如下：

所以先代入前几个数，可以发现如下规律

当n=1时，左上角值=1

当n=2时，左上角值=2

=

当n=3时，左上角值=3

=

当n=4时，左上角值=4

=

当n=5时，左上角的值=8

=

当n=6时，左上角的值=?

····
····
····

可以发现是很明显的斐波那契数列

代码

// write your code here cpp
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

void Fib(vector<int>& fib)
{
    for(int i=2 ;i < 10001;i++)
    {
        fib.push_back((fib[i-1]+fib[i-2])%10000);
    }
}
int main()
{
    int number=0;//数据个数
    vector<int> fib={1,1};//斐波那契数列
    Fib(fib);//初始化
    while(cin >> number)
    {
        int temp;
        while(number--)
        {
            cin >> temp;
            printf("%04d",fib[temp]);
        }
        cout<<endl;
    }
    return 0;
}