BZOJ4471 : 随机数生成器Ⅱ

\[\begin{eqnarray*}
x_i&=&x_{i-1}+x_{i-2}\\
x_i^2&=&x_{i-2}^2+x_{i-1}^2+2x_{i-2}x_{i-1}\\
x_{i-1}x_i&=&x_{i-1}^2+x_{i-2}x_{i-1}
\end{eqnarray*}\]

故可以构造转移矩阵$A$进行递推。

不妨设$n\geq m$，则可以预处理出$A^0,A^1,...,A^n$以及$A^n,A^{2n},...,A^{nn}$。

那么查询某个数的复杂度为$4^2$。

总时间复杂度为$O(4^3n)$。

#include<cstdio>

#include<algorithm>

#include<tr1/unordered_map>

#define rep(i) for(int i=0;i<4;i++)

using namespace std;

using namespace std::tr1;

typedef long long ll;

const int N=4,M=100005;

int n,m,lim,q,P,C1,C2,i,j,x,y,d,r,o;

int B[N],A[M][N][N],pA[M][N][N];

unordered_map<ll,int>T;

inline void read(ll&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}

inline void mul(int a[][N],int b[][N],int c[][N]){

  rep(k)rep(j)if(b[k][j])rep(i)if(a[i][k])c[i][j]=(1LL*a[i][k]*b[k][j]+c[i][j])%P;

}

inline int get(ll t){

  int x=0,*a=pA[t/lim][3],(*b)[N]=A[t%lim];

  rep(i){

    int y=0;

    rep(j)y=(1LL*a[j]*b[j][i]+y)%P;

    x=(1LL*y*B[i]+x)%P;

  }

  return x;

}

inline int ask(int x,int y){

  if(x>n||y>m)return P;

  ll t=1LL*(x-1)*m+y;

  if(T.find(t)!=T.end())return T[t];

  return get(t);

}

void write(int x){

  if(x>=10)write(x/10);

  putchar(x%10+'0');

}

int main(){

  rep(i)A[0][i][i]=pA[0][i][i]=1;

  A[1][0][1]=1;

  A[1][1][0]=A[1][1][1]=1,A[1][1][2]=2;

  A[1][2][1]=A[1][2][2]=1;

  A[1][3][1]=A[1][3][3]=1;

  scanf("%d%d%d%d%d%d",&n,&m,&q,&P,&C1,&C2);

  B[0]=B[3]=1LL*C1*C1%P;

  B[1]=1LL*C2*C2%P;

  B[2]=1LL*C1*C2%P;

  lim=n>m?n:m;

  for(i=2;i<=lim;i++)mul(A[i-1],A[1],A[i]);

  for(i=1;i<=lim;i++)mul(pA[i-1],A[lim],pA[i]);

  for(i=1;i<=q;i++){

    ll x,y;

    read(x),read(y);

    if(T.find(x)==T.end())T[x]=get(x);

    if(T.find(y)==T.end())T[y]=get(y);

    swap(T[x],T[y]);

  }

  for(i=x=y=1,o=ask(1,1);i<n+m-1;i++){

    write(o),putchar(' ');

    d=ask(x+1,y),r=ask(x,y+1);

    if(d<=r)x++,o=d;else y++,o=r;

  }

  return write(o),0;

}

巴特西

BZOJ4471 : 随机数生成器Ⅱ

最新文章

热门文章