星际密码(PAT)

1.题目描述

星际战争开展了100年之后，NowCoder终于破译了外星人的密码！他们的密码是一串整数，通过一张表里的信息映射成最终4位密码。表的规则是：n对应的值是矩阵X的n次方的左上角，如果这个数不足4位则用0填充，如果大于4位的则只输出最后4位。
|1 1|^n => |Xn …|
|1 0|_____|… …|

例如n=2时，
|1 1|^2 => |1 1| * |1 1| => |2 1|
|1 0| ____ |1 0|_ |1 0|___|1 1|
即2对应的数是“0002”。

2.输入描述:

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

3.输出描述:

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

4.输入例子:

6
18 15 21 13 25 27
5
1 10 100 1000 10000

5.输出例子:

418109877711037713937811
00010089410135017501

6.解题思路：

题目简单的来说就是矩阵的n次幂乘法，求矩阵乘积结果的左上角元素的值
由A、A²、A³……得左上角数为1、2、3、5、8……我们容易推导出其X的n次方所得Xi的规律就是斐波那契数列；
注意输入描述中k才是X的n次方中的n，而输入描述中的n是指需要翻译的个数
因为只需要四位数，所以我们要对每个斐波那契数取余；
最后我们只要输出n个四位斐波那契数密码即可

7.源代码：

#include<stdio.h>
int main()
{
	int i,k,n,num[10000];
	num[0]=1;
	num[1]=1;
	for(i=2;i<=10000;i++)
		num[i]=(num[i-1]+num[i-2])%10000;
	while(scanf("%d",&n)!=-1)
	{
		while(n--)
		{
			scanf("%d",&k);
			printf("%04d",num[k]);
		}
		printf("\n");
	}
	return 0;
}