[BZOJ 4809] 相逢是问候

时间：2020-12-29 21:31:48

Link:

传送门

Solution:

以前没见过的套路题……

1、使用EXT欧拉定理降幂的套路：

$a^{x}=a^{xmod\phi(P)+\phi(P)} mod P$，且$x\ge P$

这样对于$c^{c^{c^x}}modP$就能递推/递归得套用上述定理计算，每层模数多套一层$\phi$即可

注意每次在快速幂时要判断当前指数是否大于当前模数才能用EXT！

2、能证明一个数最多求$log$次$\phi$就会变成1

这样在$log$次内暴力更新，否则不管，就能保证$O(n*log^3)$

3、复杂度中的3个$log$分别是：

更新$log$次，每次更新迭代$log$层，每层要算一次快速幂

明显只能优化快速幂。由于底不变，模数只有$log$种，想到分数的前后两部分预处理！

分块预处理出$[1,(1<<16)]$和$[1*(1<<16),(1<<16)*(1<<16)]$的答案以及与模数的大小关系

这样每次拆出指数的前16位和后16位$O(1)$计算答案和大小关系就能做到$O(n*log^2)$

4、听说原题数据锅了……

虽然$\phi(2)$和$\phi(1)$都为1，但要更新到$\phi(1)$！

否则在最顶层指数为0时最终会迭代出$cmod2$而非$cmod1$，不一定为0！

Code:

#include <bits/stdc++.h>

using namespace std;

#define X first

#define Y second

#define pb push_back

typedef double db;

typedef long long ll;

typedef pair<int,int> P;

const int MAXN=1e5+;

ll pre[][<<][];

bool f[][<<][];

int n,m,p,c,dat[MAXN],phi[],cnt;

int getphi(int x)

{

    int ret=x;

    for(int i=;i*i<=x;i++)

        if(x%i==)

        {

            ret=ret/i*(i-);

            while(x%i==) x/=i;

        }

    if(x!=) ret=ret/x*(x-);

    return ret;

}

ll quick_pow(ll a,ll b,ll MOD,bool &f)

{

    ll ret=;

    for(;b;b>>=,a=a*a%MOD)

    {

        //判断是否大于某个数两个地方都要判！

        if(b&) f|=(ret*a>=MOD),ret=ret*a%MOD;

        f|=(a*a>=MOD&&b!=);

    }

    return ret;

}

int QP(int x,int num,bool &flag)

{

    int a=x&((<<)-),b=x>>;

    ll ret=1ll*pre[num][a][]*pre[num][b][];

    flag=f[num][a][]|f[num][b][]|(ret>=phi[num]);

    return ret%phi[num];

}

int cal(int x,int st)

{

    int ret=x;

    if(ret>=phi[st])

        ret=ret%phi[st]+phi[st];

    while(st--)

    {

        bool f=;

        ret=QP(ret,st,f);

        //注意特判，仅在指数>模数时可使用EXT欧拉定理

        if(f&&st) ret+=phi[st];

    }

    return ret%p;

}

void PRE()

{

    //分块预处理

    for(int i=;i<=cnt;i++)

    {

        pre[i][][]=pre[i][][]=;

        if(phi[i]==) f[i][][]=f[i][][]=;

        pre[i][][]=quick_pow(c,,phi[i],f[i][][]);

        int tmp=pre[i][][]=quick_pow(c,<<,phi[i],f[i][][]);

        for(int j=;j<<<;j++)

        {

            f[i][j][]=f[i][j-][]|(pre[i][j-][]*c>=phi[i]);

            pre[i][j][]=pre[i][j-][]*c%phi[i];

            f[i][j][]=f[i][j-][]|(pre[i][j-][]*tmp>=phi[i]);

            pre[i][j][]=pre[i][j-][]*tmp%phi[i];

        }

    }

}

namespace SegmentTree

{

    #define mid ((l+r)>>1)

    #define ls k<<1

    #define rs k<<1|1

    #define lc ls,l,mid

    #define rc rs,mid+1,r

    int sum[MAXN<<],tag[MAXN<<];

    void pushup(int k)

    {

        tag[k]=min(tag[ls],tag[rs]);

        sum[k]=(sum[ls]+sum[rs])%p;

    }

    void build(int k,int l,int r)

    {

        if(l==r)

        {sum[k]=dat[l]%p;tag[k]=;return;}

        build(lc);build(rc);pushup(k);

    }

    void modify(int a,int b,int k,int l,int r)

    {

        if(tag[k]>=cnt) return;

        if(l==r)

        {sum[k]=cal(dat[l],++tag[k]);return;}

        if(a<=mid) modify(a,b,lc);

        if(b>mid) modify(a,b,rc);

        pushup(k);

    }

    int query(int a,int b,int k,int l,int r)

    {

        if(a<=l&&r<=b) return sum[k];

        int ret=;

        if(a<=mid) (ret+=query(a,b,lc))%=p;

        if(b>mid) (ret+=query(a,b,rc))%=p;

        return ret;

    }

}

using namespace SegmentTree;

int main()

{

    scanf("%d%d%d%d",&n,&m,&p,&c);

    for(int i=;i<=n;i++)

        scanf("%d",&dat[i]);

    phi[]=p;

    while(phi[cnt]!=)

        cnt++,phi[cnt]=getphi(phi[cnt-]);

    //要迭代到phi(1)=1，而不能仅迭代到phi(2)=1

    //否则在x=0时最后一层会出现c%2

    phi[++cnt]=;PRE();

    build(,,n);

    while(m--)

    {

        int op,l,r;

        scanf("%d%d%d",&op,&l,&r);

        if(!op) modify(l,r,,,n);

        else printf("%d\n",query(l,r,,,n));

    }

    return ;

}

相关文章