题解 P5110 【块速递推】

Adove · 2018-12-23 13:44:26 · 题解

这题用到了矩阵快速幂+分块打表+扩展欧拉定理

矩阵的扩展欧拉定理:

然后我们将\phi(p)分块，打出中继矩阵和转移矩阵

这样就可以\Theta(1)出解了

#include"cstdio"
#include"cstring"
#include"iostream"
#include"algorithm"
#include"cmath"
#include"map"
using namespace std;

const int siz=3;
const int MOD=1e9+7;
const int cur=30005;
const int blk=(MOD<<1)/cur+5;

int T,base;

namespace Mker
{
    unsigned long long SA,SB,SC;
    void init(){scanf("%llu%llu%llu",&SA,&SB,&SC);}
    inline 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 v[siz][siz];
    int x,y;

    void Mmul(Matrix a,Matrix b)
    {
        x=a.x,y=b.y;
        v[1][1]=((long long)a.v[1][1]*b.v[1][1]+(long long)a.v[1][2]*b.v[2][1])%MOD;
        v[1][2]=((long long)a.v[1][1]*b.v[1][2]+(long long)a.v[1][2]*b.v[2][2])%MOD;
        v[2][1]=((long long)a.v[2][1]*b.v[1][1]+(long long)a.v[2][2]*b.v[2][1])%MOD;
        v[2][2]=((long long)a.v[2][1]*b.v[1][2]+(long long)a.v[2][2]*b.v[2][2])%MOD;
        return;
    }
}A[cur+5],B,C[blk];

void get(int p,int x)
{
    B.Mmul(A[x-1],C[p]);
    return;
}

int main()
{
    A[0].x=A[0].y=2;A[0].v[1][1]=A[0].v[2][2]=1;
    A[1].x=A[1].y=2;A[1].v[1][1]=233,A[1].v[1][2]=666,A[1].v[2][1]=1;
    C[0].x=2,C[0].y=1;C[0].v[1][1]=1;
    for(int i=2;i<=cur;++i) A[i].Mmul(A[i-1],A[1]);
    for(int i=1;i*cur<=MOD<<1;++i) get(i-1,cur+1),C[i]=B;
    scanf("%d",&T);Mker::init();
    while(T--){
        int tmp=Mker::rand()%(MOD-1)+MOD-2,tmp1=tmp/cur,tmp2=tmp%cur;
        base^=((long long)A[tmp2].v[1][1]*C[tmp1].v[1][1]+(long long)A[tmp2].v[1][2]*C[tmp1].v[2][1])%MOD;
    }printf("%d\n",base);
    return 0;
}