import java.util.*;
public class Main{
    public static void main(String[] args){
        int[] arr = new int[10001];
        arr[1] = 1;
        arr[2] = 2;
        for(int i = 3;i < 10001;i++){
            arr[i] = arr[i - 1] + arr[i - 2];
             arr[i] =  arr[i] % 10000;
        }
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            StringBuffer sb = new StringBuffer();
            int n = sc.nextInt();
            for(int i = 0;i < n;i++){
                int x = sc.nextInt();
                sb.append(String.format("%04d",arr[x]));
            }
            System.out.println(sb);
        }
        
    }    
}

详细解题：
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;
}

#include<iostream>
(720)#include<vector>
#include<iomanip>
using namespace std;
/*
set A=|1 1|  A^2=|2 1|  A^3=|3 2|  A^4=|5 3|  A^5=|8 5|
	  |1 0|      |1 1|      |2 1|      |3 2|      |5 3|
事实上，实对称矩阵相乘仍然是实对称矩阵。观察易得，A^(n-1)由于左乘A（也可以右乘,此处举例左乘）
X1为上A^(n-1)的第一行元素相加 X2为A^(n-1)的第一个元素（左上角元素），由于对称X3和X2一样，
X4=A^(n-1)的第2个元素
迭代得到规律左上角元素X1[n]=X1[n-1]+X1[n-2] 为fb数列1 2 3 5 8
另外，不只是X1为此数列，其他所有元素都是这个数列
取4位只需%10000即可。
*/
int main() {
	int n;
	int index = 0;
	vector<short int> code(10000, 0);
	code[0] = 1;
	code[1] = 2;
	for (int i = 2; i < 10000; i++) {
		code[i] = (code[i - 1] + code[i - 2])%10000;
	}
	while (cin >> n) {
		for (int i = 0; i < n; i++) {
			cin >> index;
			cout << setw(4) << setfill('0') << code[index - 1];
		}
		cout << endl;
	}
}

测试用例:
1

对应输出应该为:

7501

你的输出为:

0001

有没有遇到这个情况的

#include<cstdio>
int main()
{
    int n,fib[10001],i,x;fib[0]=1;fib[1]=1;
    for(i=2;i<10001;i++) fib[i]=(fib[i-1]%10000+fib[i-2]%10000)%10000;
    while(~scanf("%d",&n))
    {
    	while(n--) 
		{
			scanf("%d",&x);printf("%04d",fib[x]);
		}
		printf("\n");
    }
    return 0;
}

	#include <stdio.h>



	void data_init(int*a);



	int main()



	{



	    int a[10001]={0,1,2};



	    int n, t, i;



	    data_init(a);



	    while(scanf("%d",&n)!=EOF)



	    {



	        for(i=0;i<n;i++)



	        {



	            scanf("%d",&t);



	            printf("%04d",a[t]);



	        }



	        printf("\n");



	    }



	    return0;



	}



	void data_init(int*a)



	{



	    inti;



	    for(i=3;i<10001;i++)



	    {



	        a[i]=a[i-1]+a[i-2];



	        if(a[i]>=10000)



	        {



	            a[i]%=10000;



	        }



	             



	    }



	}

#include <stdio.h>
int a[10005]={0,1,2,3,5};
void data_init()
{
	int i;
	for(i=3;i<10005;i++)
	{
		a[i]=a[i-1]+a[i-2];
		if(a[i]>=10000) a[i]%=10000;
	}
}
int main()
{
	int n,t;
	data_init();
	while(scanf("%d",&n)!=EOF)
	{
		while(n--)
		{
			scanf("%d",&t);
                        printf("%04d",a[t]);
		}
		printf("\n");
	}
	return 0;
}
/*矩阵是   |1 1|^2=|1 1|*|1 1|=|2 1|
//         |1 0|   |1 0| |1 0| |1 1|

 n的取值：1 2 3 4 5 6 ....
左上角值：1 2 3 5 8 13 ....

又是变式的斐波那契！！！！！！！！！！！
*/

乍一看，感觉这道题不是一般的复杂，题目都有些没读懂。。。
我们先计算几个矩阵预算结果再说。

当n = 1时
|1 1|                左上角值 = 1
|1 0|
当n = 2时
|1 1|*|1 1|=|2 1|    左上角值 = 2
|1 0| |1 0| |1 1|
当n = 3时
|2 1|*|1 1|=|3 2|    左上角值 = 3
|1 1| |1 0| |2 1|
当n = 4时
|3 2|*|1 1|=|5 3|    左上角值 = 5
|2 1| |1 0| |3 2|
当n = 5时
|5 3|*|1 1|=|8 5|    左上角值 = 8
|3 2| |1 0| |5 3|
当n = 6时
                     左上角值 = 13 ？

从数据表现特征可以看出一个规律f(i) = f(i - 1) + f(i - 2) (当i ≥ 2时)，

接着我们从矩阵运算的过程分析一下得出的规律是否正确。
矩阵运算规则：

|a11 a12|*|b11 b12|=|a11*b11+a12*b12 a11*b21+a12*b22|
|a21 a22| |b21 b22| |a21*b11+a22*b12 a21*b21+a22*b22|

将b矩阵带入举证运算公式，可得:

f(n - 1)             f(n)
|a11 a12|*|1 1|=|a11+a12 a11|
|a21 a22| |1 0| |a21+a22 a21|

也就是说，每次n加1，都是将f(n - 1)的结果进行上面的求和计算，
算出的结果表现的特征就是斐波拉契尔数列。

#include <iostream>
using namespace std;

int main(int argc, const char * argv[]) {
    //建立一张表，用于记录斐波拉契尔数列的各项值
    int fTable[10001] = {0, 1, 2};
    for (int i = 3; i < 10001; ++i) {
        fTable[i] = fTable[i - 1] + fTable[i - 2];
        fTable[i] = fTable[i] % 10000;
    }
    int count = 0;
    //scanf返回值为正确输出数据的变量个数，当一个变量都没有成功获取数据时，此时返回-1
    while (scanf("%d", &count) != - 1) {
        for (int i = 0; i < count; ++i) {
            int number = 0;
            scanf("%d", &number);
            //“%04d”的作用是输出长度不少于4位，少于用0b填充
            printf("%04d", fTable[number]);
        }
        printf("\n");
    }
    return 0;
}

// write your code here cpp
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>

using namespace std;
int getXi(vector<vector<long long int>> a,vector<vector<long long int>>& b,int n){
    //第一次循环 a,b均为 [1110]

    vector<vector<long long int>> c(3,vector<long long int>(3,0));
    while(--n){

        for(int i=1;i<3;i++){//遍历第一行
            for(int j=1;j<3;j++){ //遍历第一列   //
                c[i][j]=(a[i][1]*b[1][j]+  //
                        a[i][2]*b[2][j])%10000;

            }

        }
        a=c;
    }
    return  a[1][1];
}

int main(){
    vector<vector<long long int>> a={{0,0,0},
                 {0,1,1},
                 {0,1,0}};//矩阵
    int n;
    while(cin>>n){
        while(n){
            int xi;
            cin>>xi;
            long long int ret= getXi(a,a,xi);
            printf("%04d",ret);
            n--;
        }
        printf("\n");
    }
    
//测试用例能过,
//but 提交会超时...
}

public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] arr = new int[10001]; arr[1] = 1; arr[2] = 2; for (int i = 3; i < arr.length; i++) { arr[i] = (arr[i - 1] + arr[i - 2]) % 10000;
    } while(sc.hasNext()){ int n = sc.nextInt(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { int x = sc.nextInt(); sb.append(String.format("%04d",arr[x]));
        } System.out.println(sb);
    }
}

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    while (cin >> n)
    {
        vector<int> v(n);
        for(int i = 0; i < n; i++)
            cin >> v[i];
        int m0 = 0;
        int m1 = 1;
        for(int i = 0; i < n; i++)
        {
            m0 = 0;
            m1 = 1;
            while(v[i]--)
            {
                int tmp = m1;
                m1 += m0;
                m1 %= 10000;
                m0 = tmp;
            }
            printf("%04d", m1);
        }
        cout << endl;
    }
    return 0;
}