P5110 块速递推

传送门

为啥我就没看出来有循环节呢……

打表可得，这个数列是有循环节的，循环节为\(10^9+6\)，然后分块预处理，即取\(k=sqrt(10^9+6)\)，然后分别预处理出转移矩阵\(A\)的\(A^1,A^2,...,A^{k-1}\)和\(A^k,A^{2k},...\)，那么每一次就能\(O(1)\)回答询问了

注意常数问题……这份代码勉强卡过……建议矩阵里的元素别开数组直接用四个变量存会快一点……

//minamoto

#include<bits/stdc++.h>

#define R register

#define ull unsigned long long

#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

using namespace std;

const int N=4e4+5,P=1e9+7;

inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}

namespace Mker

{

    unsigned long long SA,SB,SC;

    void init(){scanf("%llu%llu%llu",&SA,&SB,&SC);}

    unsigned long long rand()

    {

        SA^=SA<<32,SA^=SA>>13,SA^=SA<<1;

        unsigned long long t=SA;

        SA=SB,SB=SC,SC^=t^SA;return SC;

    }

}

struct Matrix{

    int a[2][2];

    Matrix(){a[0][0]=a[0][1]=a[1][0]=a[1][1]=0;}

    int* operator [](const int &x){return a[x];}

    Matrix operator *(Matrix b){

        Matrix res;

        res[0][0]=add(1ll*a[0][0]*b[0][0]%P,1ll*a[0][1]*b[1][0]%P);

        res[0][1]=add(1ll*a[0][0]*b[0][1]%P,1ll*a[0][1]*b[1][1]%P);

        res[1][0]=add(1ll*a[1][0]*b[0][0]%P,1ll*a[1][1]*b[1][0]%P);

        res[1][1]=add(1ll*a[1][0]*b[0][1]%P,1ll*a[1][1]*b[1][1]%P);

        return res;

    }

}bin1[N],bin2[N],res;int ans,T,n,len;

void init(){

    res[0][0]=233,res[0][1]=1,res[1][0]=666,bin1[1]=res;

    len=sqrt(1e9+6),bin1[0][0][0]=bin1[0][1][1]=bin2[0][0][0]=bin2[0][1][1]=1;

    fp(i,2,len-1)bin1[i]=bin1[i-1]*res;bin2[1]=bin1[len-1]*res;

    fp(i,2,len+1)bin2[i]=bin2[i-1]*bin2[1];

}

int main(){

//	freopen("testdata.in","r",stdin);

    init(),scanf("%d",&T);Mker::init();

    while(T--){

        Matrix res;n=Mker::rand()%(P-1);

        res[0][0]=1;

        if(n<=1)ans^=n;

        else res=res*bin2[(n-1)/len]*bin1[(n-1)%len],ans^=res[0][0];

    }printf("%d\n",ans);return 0;

}

P5110 块速递推的相关教程结束。