题解 P5110 【块速递推】

· · 题解

没人写正解出题人很伤心啊qwq……

为什么循环节是10^9+6啊？因为出题人给你凑好了模数才是有这个循环节的

考试时候为了避免大家自闭所以没有去卡分段矩乘的做法，其实分段矩乘的空间占用是标算的二倍，根据这一点我们可以通过卡空间的方式来吧矩乘卡下去

(天呐上面都是什么duliu东西)

本题题解

让我们把这个数列的通项公式手玩出来，这里用生成函数给出了一种推导，如果您会特征方程可以用特征方程推

设这个数列的生成函数为G(z)

G(z)=233zG(z)+666z^{2}G(z)+z (1-233z-666z^2)G(z)=z G(z)=\frac{z}{1-233z-666z^2}

设x_{1},x_{2}为方程1-233x-666x^2=0的两个根

G(z)=\frac{z}{-666(x_{1}-z)(x_{2}-z)} G(z)=\frac{z}{-666}×\frac{1}{(x_{1}-z)(x_{2}-z)} G(z)=\frac{z}{-666(x_{1}-x_{2})}×\frac{x_{1}-z+z-x_{2}}{(x_{1}-z)(x_{2}-z)} G(z)=\frac{z}{-666(x_{1}-x_{2})}×(\frac{1}{x_{2}-z}-\frac{1}{x_{1}-z}) G(z)=\frac{1}{-666(x_{1}-x_{2})}×(\frac{1}{x_{2}}×\frac{z}{1-\frac{z}{x_{2}}}-\frac{1}{x_{1}}×\frac{z}{1-\frac{z}{x_{1}}})

根据\frac{z}{1-\lambda z}是数列0,1,\lambda^{1},\lambda^{2},\lambda^{3}的生成函数可知

a(n)=\frac{1}{-666(x_{1}-x_{2})}×((\frac{1}{x_{2}})^{n}-(\frac{1}{x_{1}})^{n})

将x_{1,2}=\frac{233\pm \sqrt{56953}}{-1332}带入得

a(n)=\frac{1}{\sqrt{56953}}((\frac{233+\sqrt{56953}}{2})^{n}-(\frac{233-\sqrt{56953}}{2})^{n})

好了看起来我们发现通项公式里面有一个\sqrt{56953}这该怎么办呢？

通过暴力for循环我们可以知道这样一个事实

188305837^2 \equiv 56953 \mod 10^9+7

好了此时我们就可以将公式里面的\sqrt{56953}全部换成188305837就行了

现在我们就是要求O(1)的实现定底数的快速幂

这个其实相当的好办我们将每个数字的n次幂表示成32769k+r的形式

这样的话我们需要打两个表，f1(n)=x^{32768n},f2(n)=x^{n}而且这两个表的长度范围都是32768之内的，复杂度可以接受

那么此时

x^{p}=f1(p/32768)f2(p \mod 32768)

就可以支持O(1)的快速幂了,由于费马小定理的存在我们可以将指数取个膜这样指数就是10^9级别的了

这里将块长定为32768主要是除法和膜法都可以用右移运算和按位与运算来代替，可以降低一些常数

如此这般我们就将算法的复杂度由O(Tlogn)优化到了O(T)无需卡常数就可以轻松的通过本题啦~

不知道为什么很多人宁愿去卡矩乘的常也不愿意静下心来掏出一支铅笔和一张草稿纸推个通项公式

上代码~

#pragma GCC optimize(Ofast)
#pragma GCC optimize(3)
#include<cstdio>
#include<algorithm>
using namespace std;typedef long long ll;const ll mod=1e9+7;const ll sqr=188305837;
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;
    }
}
const ll x1=94153035;const ll x2=905847205;const ll K=233230706;
const ll x3=64353223;const ll x4=847809841;
ll mi1[65536+10];ll mi2[65536+10];ll mi3[65536+10];ll mi4[65536+10];
inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;}
# define pw1(x) (mi3[x>>16]*mi1[x&65535]%mod)
# define pw2(x) (mi4[x>>16]*mi2[x&65535]%mod)
int T;int ans;
int main()
{
    //freopen("tst10.in","r",stdin);freopen("tst10.out","w",stdout);
    mi1[0]=1;for(int i=1;i<65536;i++)mi1[i]=mi1[i-1]*x1%mod;
    mi2[0]=1;for(int i=1;i<65536;i++)mi2[i]=mi2[i-1]*x2%mod;
    mi3[0]=1;for(int i=1;i<65536;i++)mi3[i]=mi3[i-1]*x3%mod;
    mi4[0]=1;for(int i=1;i<65536;i++)mi4[i]=mi4[i-1]*x4%mod;
    scanf("%d",&T);Mker::init();unsigned long long n;
    for(int i=1;i<=T;i++)n=Mker::rand(),n%=(mod-1),ans^=K*(pw1(n)+mod-pw2(n))%mod;
    printf("%d",ans);return 0;
}