题解 P5110 【块速递推】

SSerxhs · 2018-12-22 21:53:27 · 题解

题目给出的递推式明显要矩阵加速，不会的转模板

但常规矩阵加速效率logn，此题t非常大立刻就超时

考虑预处理i<=k的所有矩阵a[i]以及ki的所有矩阵b[i]，则第n项可以直接由a[n%k]b[n/k]求得，复杂度O(t+k+n/k)，当k取sqrt(n)时复杂度最优，为O(t+sqrt(n))

然而此题n范围极大，sqrt(n)一个点都过不去。斐波那契数列对p取模时有不超过4p的循环节(证明见4000)，可以猜想，对于此题也有O(p)的循环节

暴力递推可以发现循环节长度为(p-1)，故直接对(p-1)取模，复杂度O(t+sqrt(p))，可以通过此题。

码风极丑，矩乘循环展开了

#include <stdio.h>
#include <string.h>
typedef long long ll;
const int p=1e9+7,N=4e4;
int t,i,ans,n,a,b,c,d;
int ycl1[N+2][2][2],ycl2[N+2][2][2];
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%(p-1);
    }
}
int main()
{
    scanf("%d",&t);
    Mker::init();
    ycl1[1][0][0]=233;ycl1[1][1][0]=666;ycl1[1][0][1]=1;
    for (i=2;i<=N;i++)
    {
        ycl1[i][0][0]=((ll)ycl1[i-1][0][0]*ycl1[1][0][0]+(ll)ycl1[i-1][0][1]*ycl1[1][1][0])%p;
        ycl1[i][1][0]=((ll)ycl1[i-1][1][0]*ycl1[1][0][0]+(ll)ycl1[i-1][1][1]*ycl1[1][1][0])%p;
        ycl1[i][0][1]=((ll)ycl1[i-1][0][0]*ycl1[1][0][1]+(ll)ycl1[i-1][0][1]*ycl1[1][1][1])%p;
        ycl1[i][1][1]=((ll)ycl1[i-1][1][0]*ycl1[1][0][1]+(ll)ycl1[i-1][1][1]*ycl1[1][1][1])%p;
    }
    ycl2[1][0][0]=ycl1[N][0][0];
    ycl2[1][1][0]=ycl1[N][1][0];
    ycl2[1][0][1]=ycl1[N][0][1];
    ycl2[1][1][1]=ycl1[N][1][1];
    for (i=2;i<=N;i++)
    {
        ycl2[i][0][0]=((ll)ycl2[i-1][0][0]*ycl2[1][0][0]+(ll)ycl2[i-1][0][1]*ycl2[1][1][0])%p;
        ycl2[i][1][0]=((ll)ycl2[i-1][1][0]*ycl2[1][0][0]+(ll)ycl2[i-1][1][1]*ycl2[1][1][0])%p;
        ycl2[i][0][1]=((ll)ycl2[i-1][0][0]*ycl2[1][0][1]+(ll)ycl2[i-1][0][1]*ycl2[1][1][1])%p;
        ycl2[i][1][1]=((ll)ycl2[i-1][1][0]*ycl2[1][0][1]+(ll)ycl2[i-1][1][1]*ycl2[1][1][1])%p;
    }
    ycl1[0][0][0]=ycl1[0][1][1]=1;
    ycl2[0][0][0]=ycl2[0][1][1]=1;
    while (t--)
    {
        n=Mker::rand();
        if (n==0) continue;
        a=ycl1[n%N][0][0];b=ycl1[n%N][0][1];
        ans^=((ll)a*ycl2[n/N][0][1]+(ll)b*ycl2[n/N][1][1])%p;
    }
    printf("%d",ans);
}