【BZOJ3328】PYXFIB
Description
Input
第一行一个正整数，表示数据组数据 ，接下来T行
每行三个正整数N,K,P
Output
T行，每行输出一个整数，表示结果
Sample Input
1 2 3
Sample Output
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 <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
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<k;i++)
{
S[0][0]=1,S[1][1]=S[0][1]=S[1][0]=0;
t=pm(w,P-1-i);
T[0][0]=T[1][0]=T[0][1]=1,T[0][0]+=t,T[1][1]=t;
pm(n);
t=S[0][0];
ans=(ans+t*pm(w,n%(P-1)*i))%P;
}
printf("%lld\n",ans*pm(k,P-2)%P);
}
int main()
{
int cas;
scanf("%d",&cas);
while(cas--) work();
return 0;
}//1 100000000000000000 15232 998244353