【BZOJ3328】PYXFIB

Description

Input

第一行一个正整数，表示数据组数据 ，接下来T行

每行三个正整数N,K,P

Output

T行，每行输出一个整数，表示结果

Sample Input

1

1 2 3

Sample Output

1

HINT

题解：首先看到斐波那契数列我们肯定要想到矩阵乘法，但是给出的形式并不能直接求，我们试图将其转化为矩乘的形式。

如果不考虑k的话，我们可以设A表示斐波那契数列的转移矩阵，然后套用二项式定理（这显然对矩阵运算成立），得到$ans=(I+A)^n$。

如果考虑k的限制呢？所求的式子变成$\sum\limits_{i=0}^n[k\mid i]C_n^iF_i$。而题中保证p是质数且p%k=1，即(p-1)%k=0，p-1的出现暗示着我们可能要用到原根。

接下来就是最神的一步：设g是p的原根，$g^{i\frac {p-1} k}=1$当且仅当$k\mid i$，所以令$w=g^{\frac {p-1} k}$，我们构造：$\sum\limits_{j=0}^{k-1}w^{ij}$，这个式子当$k\mid i$时=k，而当$k\nmid i$时，由等比数列求和可知该式=0。所以答案就可以表示成$\sum\limits_{i=0}^{n}\frac 1 k \sum\limits_{j=0}^{k-1}w^{ij}C_n^iF_i$。

下一步也挺神的（其实应该是个我不知道的套路），我们希望对这个式子强行套用二项式定理，但是这个式子本身并不满足二项式定理的形式，所以我们先枚举j，得到$\frac 1 k \sum\limits_{j=0}^{k-1}\sum\limits_{i=0}^nw^{ij}C_n^iF_i$。如果想套用二项式定理，我们需要式子中有一个n-i，于是我们强行把$w^{ij}$变成$w^{nj-(n-i)j}$，然后将$w^{nj}$提出来即可，最后的形式如下：

$\frac 1 k \sum\limits_{j=0}^{k-1}w^{nj}(w^{-j}I+A)^n$。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long ll;ll n,k,P,ans,g,w;int m;ll pri[20];struct M{	ll v[2][2];	M () {memset(v,0,sizeof(v));}	ll * operator [] (const int &a) {return v[a];}	M operator * (const M &a) const	{		M b;		int i,j,k;		for(i=0;i<2;i++)	for(j=0;j<2;j++)	for(k=0;k<2;k++)	b.v[i][j]=(b.v[i][j]+v[i][k]*a.v[k][j])%P;		return b;	}}S,T;inline ll pm(ll x,ll y){	ll z=1;	while(y)	{		if(y&1)	z=z*x%P;		x=x*x%P,y>>=1;	}	return z;}inline void pm(ll y){	while(y)	{		if(y&1)	S=S*T;		T=T*T,y>>=1;	}}inline void work(){	ans=0,m=0;	scanf("%lld%lld%lld",&n,&k,&P);	int i;	ll t=P-1;	for(i=2;i*i<=t;i++)	if(t%i==0)	{		pri[++m]=i;		while(t%i==0)	t/=i;	}	if(t>1)	pri[++m]=t;	for(g=2;;g++)	{		for(i=1;i<=m;i++)	if(pm(g,(P-1)/pri[i])==1)	break;		if(i>m)	break;	}	w=pm(g,(P-1)/k);	for(i=0;i