题解 P5110 【块速递推】

tktp_AK · 2018-12-22 23:11:59 · 题解

这道题是真的恶心（尤其是16MB的内存限制）

虽然一看就知道是矩阵乘法

方法一

直接暴力枚举

这是最先想到的，时间复杂度最大为O(T\times(10^{9}+7))

#include<cstdio>
#define UL unsigned long long
using namespace std;
namespace Mker
{
    UL SA,SB,SC;
    inline void init(){scanf("%llu%llu%llu",&SA,&SB,&SC);}
    inline UL rand()
    {
        SA^=SA<<32,SA^=SA>>13,SA^=SA<<1;
        UL t=SA;
        SA=SB,SB=SC,SC^=t^SA;return SC;
    }
}
UL ans,t,n,inf=1e9+7;
int main()
{
    scanf("%llu",&t);Mker::init();
    while(t--)
    {
        n=Mker::rand()%inf;
        if(n==0)continue;
        UL a=0,b=1,c;
        for(int i=2;i<=n;++i)c=(666*a+b*233)%inf,a=b,b=c;
        ans^=b;
    }
    printf("llu\n",ans);
}

期待得分0分

方法二

利用普通的矩阵乘法求斐波那契数列

时间复杂度最大为O(T\times(10^{9}+6))

好像和方法一并没有多大的不同

但还是有所改进

#include<cstdio>
#define UL unsigned long long
using namespace std;
namespace Mker
{
    UL SA,SB,SC;
    inline void init(){scanf("%llu%llu%llu",&SA,&SB,&SC);}
    inline UL rand()
    {
        SA^=SA<<32,SA^=SA>>13,SA^=SA<<1;
        UL t=SA;
        SA=SB,SB=SC,SC^=t^SA;return SC;
    }
}
struct node
{
    UL a[2][2];
}A={233,666,1,0},T={1,0,0,1};
UL ans,t,n,inf=1e9+7;
inline node operator*(node a,node b)//重载运算符
{
    return (node)
    {
        (1UL*a.a[0][0]*b.a[0][0]+a.a[0][1]*b.a[1][0])%inf,
        (1UL*a.a[0][0]*b.a[0][1]+a.a[0][1]*b.a[1][1])%inf,
        (1UL*a.a[1][0]*b.a[0][0]+a.a[1][1]*b.a[1][0])%inf,
        (1UL*a.a[1][0]*b.a[0][1]+a.a[1][1]*b.a[1][1])%inf
    };
}
int main()
{
    scanf("%llu",&t);Mker::init();
    while(t--)
    {
        n=Mker::rand()%(inf-1);
        if(n==0)continue;
        node sum=T;
        for(int i=1;i<=n;++i)sum=sum*A;
        ans^=sum.a[0][0];
    }
    printf("llu\n",ans);
}

期待得分0分

方法三

矩阵乘法+快速幂

时间复杂度最大为O(T\times log_2(10^{9}+6))

#include<cstdio>
#define UL unsigned long long
using namespace std;
namespace Mker
{
    UL SA,SB,SC;
    inline void init(){scanf("%llu%llu%llu",&SA,&SB,&SC);}
    inline UL rand()
    {
        SA^=SA<<32,SA^=SA>>13,SA^=SA<<1;
        UL t=SA;
        SA=SB,SB=SC,SC^=t^SA;return SC;
    }
}
struct node
{
    UL a[2][2];
}A={233,666,1,0},T={1,0,0,1};
UL ans,t,n,inf=1e9+7;
inline node operator*(node a,node b)//重载运算符
{
    return (node)
    {
        (1UL*a.a[0][0]*b.a[0][0]+a.a[0][1]*b.a[1][0])%inf,
        (1UL*a.a[0][0]*b.a[0][1]+a.a[0][1]*b.a[1][1])%inf,
        (1UL*a.a[1][0]*b.a[0][0]+a.a[1][1]*b.a[1][0])%inf,
        (1UL*a.a[1][0]*b.a[0][1]+a.a[1][1]*b.a[1][1])%inf
    };
}
inline node ksm(node a,UL b)//求a的b次方
{
    node s=T;
    while(b)
    {
        if(b&1/*b%2==1*/)s=s*a;
        a=a*a;b>>=1/*b/=2*/;
    }
    return s;
}
int main()
{
    scanf("%llu",&t);Mker::init();
    while(t--)
    {
        n=Mker::rand()%(inf-1);
        if(n==0)continue;
        node sum=T;
        for(int i=1;i<=n;++i)sum=sum*A;
        ans^=sum.a[0][0];
    }
    printf("llu\n",ans);
}

期待得分6分（谁叫前6个个点都是1分）

方法四

利用2进制的思想将数进行分治

就是说如果n为465213

转化为二进制就是1110001100100111101

只用求出各个位的二进制，然后相乘

时间复杂度最大为O(T\times log_2(10^{9}+6)\div2)

#icnlude<cmath>
#include<cstdio>
#define UL unsigned long long
using namespace std;
namespace Mker
{
    UL SA,SB,SC;
    inline void init(){scanf("%llu%llu%llu",&SA,&SB,&SC);}
    inline UL rand()
    {
        SA^=SA<<32,SA^=SA>>13,SA^=SA<<1;
        UL t=SA;
        SA=SB,SB=SC,SC^=t^SA;return SC;
    }
}
struct node
{
    UL a[2][2];
}A={233,666,1,0},T={1,0,0,1};
UL ans,t,n,inf=1e9+7;
inline node operator*(node a,node b)//重载运算符
{
    return (node)
    {
        (1UL*a.a[0][0]*b.a[0][0]+a.a[0][1]*b.a[1][0])%inf,
        (1UL*a.a[0][0]*b.a[0][1]+a.a[0][1]*b.a[1][1])%inf,
        (1UL*a.a[1][0]*b.a[0][0]+a.a[1][1]*b.a[1][0])%inf,
        (1UL*a.a[1][0]*b.a[0][1]+a.a[1][1]*b.a[1][1])%inf
    };
}
inline node ksm(node a,UL b)//求a的b次方
{
    node s=T;
    while(b)
    {
        if(b&1/*b%2==1*/)s=s*a;
        a=a*a;b>>=1/*b/=2*/;
    }
    return s;
}
node a[32];
int main()
{
    a[0]=A;a[1]=A*A
    for(int i=1;i<=31;++i)a[i]=a[i-1]*a[1];//预处理
    scanf("%llu",&t);Mker::init();
    while(t--)
    {
        n=Mker::rand()%(inf-1);
        if(n==0)continue;
        node sum=T;
        while(n)
        {
            sum=sum*a[int(log2(n&-n))];//log2(n)求n为2的多少次方，n&-n求最近的二进制
//例如n等于465213，二进制为1110001100100111101，那么n&-n就返回1因为二进制第一位是1
            n=n-(n&-n);//减去那一位，下一次就是下一位
        }
        ans^=sum.a[0][0];
    }
    printf("llu\n",ans);
}

期待得分6分（最后4个点太坑了）

方法五

还是用分治的思想

但不是分成二进制，可以分成两部分

除去一个10^{9}+7,那么最大就只能是0 \sim 10^{9}+6

将它开方就可以得到31622.7766965521

尽量取整，但要比较接近（反正我是取了32000的）

定义两个数组s[32000],v[32000],v_{i}表示A^{i}\times T,s_{i}表示v_{32000}^{i}\times T

给一个n，就把它分成n\div 32000和n\mod32000两部分，然后把两部分相乘再乘T就是结果

时间复杂度最大为O(32000+T\times 2)

#include<cstdio>
#define UL unsigned long long
namespace Mker
{
    UL SA,SB,SC;
    inline void init(){scanf("%llu%llu%llu",&SA,&SB,&SC);}
    inline UL rand()
    {
        SA^=SA<<32,SA^=SA>>13,SA^=SA<<1;
        UL t=SA;
        SA=SB,SB=SC,SC^=t^SA;return SC;
    }
}
struct node
{
    UL a[2][2];
};
const node A={233,666,1,0},T={1,0,0,1};
UL n,ans=0;
const int inf=1e9+7,mod=32000;
li node operator*(node a,node b){return (node){(1UL*a.a[0][0]*b.a[0][0]+a.a[0][1]*b.a[1][0])%inf,(1UL*a.a[0][0]*b.a[0][1]+a.a[0][1]*b.a[1][1])%inf,(1UL*a.a[1][0]*b.a[0][0]+a.a[1][1]*b.a[1][0])%inf,(1UL*a.a[1][0]*b.a[0][1]+a.a[1][1]*b.a[1][1])%inf};}
inline node ksm(node a,UL b)
{
    node sum=T;
    while(b)
    {
        if(b&1)sum=sum*a;
        a=a*a,b>>=1;
    }
    return sum;
}
node a[32000],v[32000];
int main()
{
    v[1]=ksm(A,mod);a[1]=A;
    for(int i=2;i<=31999;++i)
    {
        if(inf/mod>=i)v[i]=v[i-1]*v[1];
        a[i]=a[i-1]*A;
    }   
    int t;scanf("%d",&t);
    Mker::init();
    while(t--)
    {
        n=(Mker::rand()-1)%(inf-1);
        if(n==0)continue;
        node sum=T;
        if(n/mod)sum=sum*v[n/mod];
        if(n%mod)sum=sum*a[n%mod];
        ans^=sum.a[0][0];
    }
    printf("%llu\n",ans);
    return 0;
}

期待得分100分