本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
Description
农夫栋栋近年收入不景气，正在他发愁如何能多赚点钱时，他听到隔壁的小朋友在讨论兔子繁殖的问题。
问题是这样的：第一个月初有一对刚出生的小兔子，经过两个月长大后，这对兔子从第三个月开始，每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第n个月有多少只兔子？
聪明的你可能已经发现，第n个月的兔子数正好是第n个Fibonacci(斐波那契)数。栋栋不懂什么是Fibonacci数，但他也发现了规律：第i+2个月的兔子数等于第i个月的兔子数加上第i+1个月的兔子数。前几个月的兔子数依次为：
1 1 2 3 5 8 13 21 34 …
栋栋发现越到后面兔子数增长的越快，期待养兔子一定能赚大钱，于是栋栋在第一个月初买了一对小兔子开始饲养。
每天，栋栋都要给兔子们喂食，兔子们吃食时非常特别，总是每k对兔子围成一圈，最后剩下的不足k对的围成一圈，由于兔子特别害怕孤独，从第三个月开始，如果吃食时围成某一个圈的只有一对兔子，这对兔子就会很快死掉。
我们假设死去的总是刚出生的兔子，那么每个月的兔子数仍然是可以计算的。例如，当k=7时，前几个月的兔子数依次为：
1 1 2 3 5 7 12 19 31 49 80 …
给定n，你能帮助栋栋计算第n个月他有多少对兔子么？由于答案可能非常大，你只需要告诉栋栋第n个月的兔子对数除p的余数即可。
Input
输入一行，包含三个正整数n, k, p。
Output
输出一行，包含一个整数，表示栋栋第n个月的兔子对数除p的余数。
Sample Input
6 7 100
Sample Output
7
HINT
1<=N<=10^18
Source
本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
5,5,3,0,
3,3,6,2,0,
2,2,4,6,3,2,5,0,5,5,3,0,
3,3,6,2,0,
是不是很有规律？
会发现每行第一个数是上一行最后一个非0数（这不是废话吗，0+任何数=自己啊...），而这一行的第i个数=第一个数×斐波那契数列的第i个数取模即可得到。
这就在暗示我们或许可以做了！令这一行的长度为len，那么第一个数×fib[len]=1(mod k)，我们可以通过已知得到fib[len] 的值，假如我们预处理出斐波那契数列在模k意义下的值，就可以做出每个模第一次出现的位置，就从而得到长度。所以只要对第一个数求个逆元就可以了，但是模数可能不是质数...那就上exgcd！当然如果没有逆元，意味着可以直接快速幂结束了...
但是这似乎还是会T，观察到上述序列很有可能出现循环节！就比如样例中的这个序列，我们没有必要反复计算，可以考虑一个循环节视为一个整体，对这个整体矩乘快速幂，剩下的零头再单独做，就可以完美解决这道题了。
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
const int inf = (<<);
const int MAXN = ;
const int MAXL = ;
LL n,fir;
int k,MOD;
int fib[MAXL],vis[MAXN],len[MAXN];
LL F[MAXN];//每个开头的数对应的使得其最后一个数为1的斐波那契数
bool hav[MAXN];//这个k意义下的模数作为开头是否出现过
struct matrix{
int n,m;
LL s[][];
}ans,ini,dan,mul,jian,I,old[MAXN]; inline matrix operator * (matrix a,matrix b){
matrix tmp=ini; tmp.n=a.n; tmp.m=b.m;
for(int i=;i<a.n;i++)
for(int j=;j<b.m;j++)
for(int l=;l<a.m;l++)
tmp.s[i][j]+=a.s[i][l]*b.s[l][j],tmp.s[i][j]%=MOD;
return tmp;
} inline int getint()
{
int w=,q=; char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar(); if(c=='-') q=,c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar(); return q ? -w : w;
}
inline LL gcd(LL x,LL y){ if(y==) return x; return gcd(y,x%y); }
inline matrix fast_pow(matrix a,LL y){ matrix tmp=dan; while(y>) { if(y&) tmp=tmp*a; a=a*a; y>>=; } return tmp; }
inline LL exgcd(LL aa,LL bb,LL &x,LL &y){
if(bb==) {
x=; y=;
return aa;
}
LL cun=exgcd(bb,aa%bb,x,y),lin=x;
x=y; y=lin-(aa/bb)*y;
return cun;
}
inline void out(){ if(n!=) ans=ans*fast_pow(mul,n); ans.s[][]%=MOD; ans.s[][]+=MOD; ans.s[][]%=MOD; printf("%lld",ans.s[][]); exit(); }
inline void work(){
scanf("%lld",&n); k=getint(); MOD=getint(); fib[]=fib[]=;
for(int i=;;i++) {//斐波那契数列的模k意义下的循环节不超过6*k
fib[i]=fib[i-]+fib[i-]; fib[i]%=k;
if(!vis[fib[i]]) vis[fib[i]]=i;
if(fib[i-]== && fib[i]==) break;
}
for(int i=;i<;i++) for(int j=;j<;j++) ini.s[i][j]=; for(int i=;i<;i++) dan.s[i][i]=; jian=dan; ans.s[][]=ans.s[][]=;
ans.n=; ans.m=; mul.n=mul.m=jian.n=jian.m=dan.n=dan.m=; bool FFF=false;
mul.s[][]=mul.s[][]=mul.s[][]=mul.s[][]=; jian.s[][]=-; fir=; LL xx,yy,gg;
for(;n;) {
if(F[fir]==) {
gg=gcd(fir,k); if(gg!=) F[fir]=-;
else { exgcd(fir,k,xx,yy); xx%=k; xx+=k; xx%=k;/*exgcd!!!*/ F[fir]=xx; }
}
if(F[fir]==-) out();
if(!hav[fir] || FFF) {//未出现过
if(!vis[F[fir]]) out();//不存在这种模数
len[fir]=vis[F[fir]];//出现的第一个位置
if(n>=len[fir]) {
old[fir]=fast_pow(mul,len[fir]);
n-=len[fir];
}
else out();
old[fir]=old[fir]*jian;
ans=ans*old[fir];
hav[fir]=; fir*=fib[len[fir]-]; fir%=k;
}
else{//出现循环节
LL ff=fir; LL cnt=/*!!!*/;//统计计算的次数
I=dan;
for(ff=fir*fib[len[fir]-]%k;ff!=fir;(ff*=fib[len[ff]-])%=k){
I=I*old[ff]; cnt+=len[ff];
}
cnt+=len[ff]; I=old[ff]*I;/*矩乘不满足交换律！！！*///I=I*old[ff];
ans=ans*fast_pow(I,n/cnt);
n=n%cnt; FFF=true;//标记
}
}
out();
} int main()
{
work();
return ;
}