解題思路：用公式遞推顯然是會超時的，於是根據題目明顯的提示，就想到用矩陣快速冪。
之所以快，是運用了二分的思想，算出了矩陣A的值，那麼我可以一步算出A*A的值，進而一步算出A*A*A*A的值，進而……
題目鏈接：點擊打開鏈接
#include
#include
#define N 100000
#define MOD 10000
using namespace std;
int f[N];
int Get(int n) //將n轉化成二進制並存到數組f
{
int cnt=0;
while(n)
{
if(n%2) f[cnt++]=1;
else f[cnt++]=0;
n/=2;
}
return cnt;
}
int b[2][2],s[2][2]; //數組b保存矩陣A，A*A，A*A*A*A……數組s保存答案。
void Cal(int k)
{
int t[2][2];
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
t[i][j]=s[i][j];
if(k) //此二進制位為1.
{
s[0][0]=((t[0][0]*b[0][0])%MOD+(t[0][1]*b[1][0])%MOD)%MOD; //矩陣乘法
s[0][1]=((t[0][0]*b[0][1])%MOD+(t[0][1]*b[1][1])%MOD)%MOD;
s[1][0]=((t[1][0]*b[0][0])%MOD+(t[1][1]*b[1][0])%MOD)%MOD;
s[1][1]=((t[1][0]*b[0][1])%MOD+(t[1][1]*b[1][1])%MOD)%MOD;
}
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
t[i][j]=b[i][j];
//繼續求下一個A*A*A*A*A*A*A*A……
b[0][0]=((t[0][0]*t[0][0])%MOD+(t[0][1]*t[1][0])%MOD)%MOD;
b[0][1]=((t[0][0]*t[0][1])%MOD+(t[0][1]*t[1][1])%MOD)%MOD;
b[1][0]=((t[1][0]*t[0][0])%MOD+(t[1][1]*t[1][0])%MOD)%MOD;
b[1][1]=((t[1][0]*t[0][1])%MOD+(t[1][1]*t[1][1])%MOD)%MOD;
}
int main()
{
int n;
while(scanf("%d",&n)==1)
{
if(n==-1)
break;
int len=Get(n);
b[0][0]=1; b[0][1]=1; b[1][0]=1; b[1][1]=0; //初始化。
s[0][0]=1; s[0][1]=0; s[1][0]=0; s[1][1]=1;
for(int i=0;i
