详细解题：
https://fanxinglanyu.blog.csdn.net/article/details/104611998

1 题目

星际密码
时间限制 1000 ms 内存限制 32768 KB 代码长度限制 100 KB 判断程序 Standard (来自 小小)
题目描述
星际战争开展了100年之后，NowCoder终于破译了外星人的密码！他们的密码是一串整数，通过一张表里的信息映射成最终4位密码。表的规则是：n对应的值是矩阵X的n次方的左上角，如果这个数不足4位则用0填充，如果大于4位的则只输出最后4位。
$$

例如n=2时，

即2对应的数是“0002”。

输入描述:
输入有多组数据。
每组数据两行：第一行包含一个整数n (1≤n≤100)；第二行包含n个正整数Xi (1≤Xi≤10000)

输出描述:
对应每一组输入，输出一行相应的密码。

输入例子:
6
18 15 21 13 25 27
5
1 10 100 1000 10000

输出例子:
418109877711037713937811
00010089410135017501

2 解析

求矩阵的n次方的结果的矩阵的左上角。

。。。
矩阵结果的左上角的值1、1、2、5、8、。。。，满足斐波那契数列。

3 参考代码

#include <cstdio>

const int MAXN = 10010;
int f[MAXN] = {1,1,2};

int main(int argc, char const *argv[]){
    int n;
    for (int i = 3; i < MAXN; ++i) {
        f[i] = (f[i -1] + f[i -2])% 10000;//递推式//f[20] = 10946
    }
    int x;
    while(scanf("%d", &n) != EOF){
        for (int i = 0; i < n; ++i) {
            scanf("%d", &x);
            printf("%04d", f[x]);
        }
        printf("\n");
    }
    return 0;
}