【BZOJ 2432】 [Noi2011]兔农 矩乘+数论

这道题的暴力分还是很良心嘛~~~~~

直接刚的话我发现本蒟蒻只会暴力，矩乘根本写不出来，然后让我们找一下规律，我们发现如果我们把这个序列在mod k的意义下摆出，并且在此过程中把值为1的的数减一，我们发现他可以成为一段一段的被0(我们在此只关注减1变为0的点)区间，我们继续分析我们分析出来了这样的性质：如果存在这样的点，那么他右边的点一定是两个重复的数，而且往后是fibonacci数列（重头开始）乘第一个数，那么他之后再出现这样的0，的充要条件是其后存在一个fibonacci数是这段数第一个数的逆元。

我们先介绍一个结论（本蒟蒻并不会证）：斐波那契数列模k后一定是0,1,1开头的纯循环，而且这个循环节的长度≤6k。我们开一个数组vis[i]表示第一个在mod k意义下值为i的fibonacci数的位置，这样我们求出某个数的逆元就知道以这个数为首项的数段的长度了（这样我们就可以跳啦）。

现在我说一下到了现在我们做了什么，我们发现在mod k 的意义下，这个数列会是一个由0（再次强调我们在此只关注减1变为0的点）隔开散区间（一整个也算）开头，之后要么成为循环，要么不再有0。先解释成为循环：因为我们在mod k的意义下因此最多不过k个数段就可以找到循环。我们再解释一下不在有0，这个就是当这个数段的第一项在mod k的意义下没有逆元，或者有逆元但是找不到vis[]。

现在我们用k再乘一个不大的数的时间复杂度找出来我们要处理的假fibonacci在哪些位置减一，以及他到底是存在循环节还是到后来没有了0，现在我们就可以想到一些矩阵，进行操作，但是这些矩阵一定要满足可乘。对于循环节我们暴力处理两边和一个循环节，对于最后没有0，我们就在后面直接fibonacci。

坑：I.via[1]!=1！！！！我们要找的是他后面第一个1，而我们前两个数是受法律保护的。

　　II.对于处理一段一段的,最后一段可能顶到n，不满

　　|||.一定要注意矩阵乘没有交换律

#include <cstdio>

#include <cmath>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long LL;

const LL N=;

LL n,k,p,vis[N],f[N*],Ola,Stop,L,R,pos[N];

LL a[][],b[][],temp_ab[][],F[],temp_F[],S[][];

bool huzhi[N];

LL GCD(LL x,LL y){

  return x==?y:GCD(y%x,x);

}

inline LL Min(LL x,LL y){

  return x<y?x:y;

}

inline void get_Ola(){

  LL lim=(LL)sqrt(k+0.5);

  LL x=k;Ola=k;

  for(LL i=;i<=lim;i++)

    if(x%i==){

      Ola=Ola/i*(i-);

      while(x%i==)x/=i;

    }

  if(x!=){

    Ola=Ola/x*(x-);

  }

}

//*******************GCD&&Ola*********************//

inline void Multi_One(){

  memset(temp_F,,sizeof(temp_F));

  for(int i=;i<=;i++)

    for(int j=;j<=;j++)

      temp_F[i]=(temp_F[i]+F[j]*a[j][i]%p+p)%p;

  memcpy(F,temp_F,sizeof(F));

}

inline void Multi_Two(){

  memset(temp_ab,,sizeof(temp_ab));

  for(int i=;i<=;i++)

    for(int j=;j<=;j++)

      for(int l=;l<=;l++)

        temp_ab[i][j]=(temp_ab[i][j]+a[i][l]*a[l][j]%p+p)%p;

  memcpy(a,temp_ab,sizeof(a));

}

inline void Multi_Three(){

  memset(temp_F,,sizeof(temp_F));

  for(int i=;i<=;i++)

    for(int j=;j<=;j++)

      temp_F[i]=((temp_F[i]+F[j]*b[j][i]%p)%p+p)%p;

  memcpy(F,temp_F,sizeof(F));

}

inline void Multi_Four(){

  memset(temp_ab,,sizeof(temp_ab));

  for(int i=;i<=;i++)

    for(int j=;j<=;j++)

      for(int l=;l<=;l++)

        temp_ab[i][j]=(temp_ab[i][j]+S[i][l]*a[l][j]%p+p)%p;

  memcpy(S,temp_ab,sizeof(S));

}

inline void Multi_Five(){

  memset(temp_ab,,sizeof(temp_ab));

  for(int i=;i<=;i++)

    for(int j=;j<=;j++)

      for(int l=;l<=;l++)

        temp_ab[i][j]=(temp_ab[i][j]+a[i][l]*a[l][j]%p)%p;

  memcpy(a,temp_ab,sizeof(a));

}

inline void Multi_Six(){

  memset(temp_ab,,sizeof(temp_ab));

  for(int i=;i<=;i++)

    for(int j=;j<=;j++)

      for(int l=;l<=;l++)

        temp_ab[i][j]=(temp_ab[i][j]+S[i][l]*b[l][j]%p+p)%p;

  memcpy(S,temp_ab,sizeof(S));

}

inline void Multi_Seven(){

  memset(temp_F,,sizeof(temp_F));

  for(int i=;i<=;i++)

    for(int j=;j<=;j++)

      temp_F[i]=(temp_F[i]+F[j]*S[j][i]%p+p)%p;

  memcpy(F,temp_F,sizeof(F));

}

inline void Multi_E(){

  memset(temp_ab,,sizeof(temp_ab));

  for(int i=;i<=;i++)

    for(int j=;j<=;j++)

      for(int l=;l<=;l++)

        temp_ab[i][j]=(temp_ab[i][j]+S[i][l]*S[l][j]%p+p)%p;

  memcpy(S,temp_ab,sizeof(S));

}

//*********************Multi**********************//

inline LL Pow(LL x,LL y,LL P){

  LL ans=;

  while(y){

    if(y&)ans=ans*x%P;

    y>>=,x=x*x%P;

  }

  return ans;

}

inline void POW(int step){

  while(step){

    if(step&)Multi_Seven();

    step>>=,Multi_E();

  }

}

//**********************POW***********************//

inline void Stop_Forever(){

  LL now=,step=;

  while(){

    if(step>=n){

      Stop=n;

      break;

    }

    if(pos[now]){

      L=pos[now],R=step-;

      break;

    }

    pos[now]=step;

    if(huzhi[now]==){

      Stop=step-;break;

    }

    LL Now=Pow(now,Ola-,k);

    if(vis[Now]==){

      Stop=step-;break;

    }

    step+=vis[Now];

    now=f[vis[Now]-]*now%k;

  }

}

//*********************Judge*********************//

inline void F_H(){

  f[]=,f[]=;

  for(int i=;i<=*k;i++)

    f[i]=(f[i-]+f[i-])%k,vis[f[i]]=vis[f[i]]==?i:vis[f[i]];

  for(int i=;i<k;i++)

    if(GCD(i,k)==)huzhi[i]=;

}

inline void Pre(){

  b[][]=;

  b[][]=;

  b[][]=-,b[][]=;

  F[]=,F[]=F[]=;

}

inline void Init(){

  scanf("%lld%lld%lld",&n,&k,&p);

  F_H();

  get_Ola();

  Stop_Forever();

  Pre();

}

//***********************Pre**********************//

inline void GO(LL step){

  memset(a,,sizeof(a));

  a[][]=;

  a[][]=,a[][]=;

  a[][]=;

  while(step){

    if(step&)Multi_One();

    step>>=,Multi_Two();

  }

}

inline void GO_ON(int step){

  memset(a,,sizeof(a));

  a[][]=;

  a[][]=,a[][]=;

  a[][]=;

  while(step){

    if(step&)Multi_Four();

    step>>=,Multi_Five();

  }

}

inline void Get_Boss(LL &now,LL &step){

  S[][]=;

  S[][]=;

  S[][]=;

  while(step<R){

    LL Now=Pow(now,Ola-,k);

    LL y=vis[Now];

    if(!step)y--;

    GO_ON(y);

    if(!step)y++;

    step+=y;

    Multi_Six();

    now=f[vis[Now]-]*now%k;

  }

}

//****************Carry On******************//

inline void Work_Stop(){

  LL now=,step=;

  while(step<Stop){

    LL Now=Pow(now,Ola-,k);

    LL y=Min(n-step,vis[Now]);

    if(!step)y--;

    GO(y);

    if(!step)y++;

    step+=y;

    if(y==vis[Now])Multi_Three();

    now=f[vis[Now]-]*now%k;

  }

  GO(n-step);

  printf("%lld",F[]);

}

inline void Work_Forever(){

  LL now=,step=;

  while(step<L-){

    LL Now=Pow(now,Ola-,k);

    LL y=vis[Now];

    if(!step)y--;

    GO(y);

    if(!step)y++;

    step+=y;

    Multi_Three();

    now=f[vis[Now]-]*now%k;

  }

  Get_Boss(now,step);

  POW((n-L+)/(R-L+));

  step=(n-L+)/(R-L+)*(R-L+)+L-;

  while(step<n){

    LL Now=Pow(now,Ola-,k);

    LL y=Min(n-step,vis[Now]);

    GO(y);

    step+=y;

    if(y==vis[Now])Multi_Three();

    now=f[vis[Now]-]*now%k;

  }

  printf("%lld",F[]);

}

//*********************War*****************//

int main(){

  Init();

  if(Stop)Work_Stop();

  else Work_Forever();

  return ;

}