2道Fibonacci。
2道Fibonacci。。求助
Description
斐波那契数列应该是世界上最美的数列了，但是要是不算出它的前100000000项你就体会不到它的美丽，我们现在就要算出第N个Fibonacci数是多少
Input
输入包括多组数据，每行一个整数N(1 =< N <= 10^9),输入以0结束
Output
对应每组输出，请输出第N个Fibonacci数列的值，因为它可能非常大，输出它mod 10000的值
Sample Input
4
63
12
78
0
Sample Output
3
9842
144
1464
==========================================
Description
如果你感觉到普通Fibonacci数列是简约的美，那么我们来试试通俗的Fibonacci，它是这样定义的
F0=x
F1=y
Fn=p*Fn-1+q*Fn-2，
同样，这次我们要计算这个数列的前10^9次项
Input
输入包括多组数据，每组数据包括一行格式为 x,y,p,q,n，其中1 =< x,y,p,q =< 1000,n<=10^9,输入以0 0 0 0 0结束
Output
每行输出给定Fibonacci的第N项，由于数据比较庞大，给出结果 mod 10003的值
Sample Input
1 1 1 1 1
1 1 1 1 3
1 2 1 3 2
1 2 1 3 3
1 2 1 3 4
0 0 0 0 0
Sample Output
1
2
2
5
11
------解决方案--------------------
运用矩阵相乘，可以实现log(n)
------解决方案--------------------
直接递归也行，为了效率考虑矩阵乘法也行，反正中间每步的结果都mod 10000拿来计算就行了
------解决方案--------------------
那也不是吧，每次递归了一半的，这方法是很烂的，你可以预先求好，2^k的Fibonacci数，然后把N分解成2进制相乘
------解决方案--------------------
每步都mod10000，保留计算过的值，应该很快的
Description
斐波那契数列应该是世界上最美的数列了，但是要是不算出它的前100000000项你就体会不到它的美丽，我们现在就要算出第N个Fibonacci数是多少
Input
输入包括多组数据，每行一个整数N(1 =< N <= 10^9),输入以0结束
Output
对应每组输出，请输出第N个Fibonacci数列的值，因为它可能非常大，输出它mod 10000的值
Sample Input
4
63
12
78
0
Sample Output
3
9842
144
1464
==========================================
Description
如果你感觉到普通Fibonacci数列是简约的美，那么我们来试试通俗的Fibonacci，它是这样定义的
F0=x
F1=y
Fn=p*Fn-1+q*Fn-2，
同样，这次我们要计算这个数列的前10^9次项
Input
输入包括多组数据，每组数据包括一行格式为 x,y,p,q,n，其中1 =< x,y,p,q =< 1000,n<=10^9,输入以0 0 0 0 0结束
Output
每行输出给定Fibonacci的第N项，由于数据比较庞大，给出结果 mod 10003的值
Sample Input
1 1 1 1 1
1 1 1 1 3
1 2 1 3 2
1 2 1 3 3
1 2 1 3 4
0 0 0 0 0
Sample Output
1
2
2
5
11
------解决方案--------------------
运用矩阵相乘，可以实现log(n)
------解决方案--------------------
直接递归也行，为了效率考虑矩阵乘法也行，反正中间每步的结果都mod 10000拿来计算就行了
------解决方案--------------------
那也不是吧，每次递归了一半的，这方法是很烂的，你可以预先求好，2^k的Fibonacci数，然后把N分解成2进制相乘
------解决方案--------------------
每步都mod10000，保留计算过的值，应该很快的