洛谷 P3747 相逢是问候 题解【树状数组】【欧拉定理】【快速幂】【平衡树】

作者: wjyyy 分类: Treap,分块,分解质因数,数学,树状数组,欧拉函数,筛素数,解题报告 发布时间: 2018-10-10 19:53

点击量:15

 

   一道充分考察了扩展欧拉定理的题目,并且细节要求比较多。

 

题目描述

Informatik verbindet dich und mich.

信息将你我连结。

 

B 君希望以维护一个长度为\(n\)的数组,这个数组的下标为从\(1\)到\(n\)的正整数。

 

一共有\(m\)个操作,可以分为两种:

  • 0 l r 表示将第\(l\)个到第\(r\)个数\((a_l,a_{l+1},…a_r)\)中的每一个数\(a_i\)替换为\(c^{a_i}\),即\(c\)的\(a_i\)次方,其中\(c\)是输入的一个常数,也就是执行赋值\(a_i=c^{a_i}\)
  • 1 l r 求第\(l\)个到第\(r\)个数的和,也就是输出:\(\sum_{i=l}^{r}a_i\)

 

因为这个结果可能会很大,所以你只需要输出结果\(\bmod p\)的值即可。

 

输入输出格式

输入格式:

第一行有四个整数\(n,m,p,c\),所有整数含义见问题描述。

接下来一行\(n\)个整数,表示\(a\)数组的初始值。

接下来\(m\)行,每行三个整数,其中第一个整数表示了操作的类型。

 

  • 如果是\(0\)的话,表示这是一个修改操作,操作的参数为\(l,r\)。
  • 如果是\(1\)的话,表示这是一个询问操作,操作的参数为\(l,r\)。

 

输出格式:

对于每个询问操作,输出一行,包括一个整数表示答案\(\bmod p\)的值。

输入输出样例

输入样例#1:

4 4 7 2
1 2 3 4
0 1 4
1 2 4
0 1 4
1 1 3
输出样例#1:

0
3

说明

  • 对于\(0\%\)的测试点,和样例一模一样;
  • 对于另外\(10\%\)的测试点,没有修改;
  • 对于另外\(20\%\)的测试点,每次修改操作只会修改一个位置(也就是\(l=r\)),并且每个位置至多被修改一次;
  • 对于另外\(10\%\)的测试点,\(p=2\);
  • 对于另外\(10\%\)的测试点,\(p=3\);
  • 对于另外\(10\%\)的测试点,\(p=4\);
  • 对于另外\(20\%\)的测试点,\(n\le 100,m\le 100\);
  • 对于\(100\%\)的测试点,\(1\le n\le 50000,\ 1\le m\le 50000,\ 1\le p\le 100000000,\ 0 <c<p,\ 0\le a_i<p\)。

题解:

   这个题涉及到区间取指数,而且需要取模。即使是暴力也要\(O(nq\log^2n)\),因为我们需要注意到指数是不能直接取模的。因此在计算时仍然要一步一步地回溯,先算指数,然后算幂;唯一可以防止爆范围的方式是用扩展欧拉定理,对指数进行相应的取模

 

   不过有一个优化,可以把上面的一个\(n\)换成\(\log n\),复杂度变成\(O(q\log^3n)\)。如果做过P4139/bzoj3884就知道,模数是不停收敛的,当指数越高阶时,欧拉函数越高阶,欧拉函数值就越小。欧拉函数\(\varphi(x)\)的值会在\(O(\log x)\)次左右收敛到\(1\)(设为\(k\)),此时得到某一阶的指数为\(0\),停止回溯。那么我们预处理出每个数在取指数\(t\)次后,需要\(\text{mod}\)的值,这个可以在\(O(\log p)\)的时间内完成。

 

   因此我们维护一个可以删点的数据结构,如set等平衡树。每次从平衡树中取出一段区间,暴力更改它们现在的值,更新它们已经被更改过的次数。一旦有一段被更改次数达到上述收敛值,那么就把这一段从平衡树里删去,之后这个点的答案就确定为此时的数值,前缀和用树状数组维护。每个点最多会被修改\(k\)次,\(k\)是\(O(\log n)\)级别的,那么每个点被操作的次数就是\(O(n\log n)\)。

 

   此时就要算快速幂了,因为快速幂的二进制分解是\(O(\log n)\),回溯指数是\(O(\log n)\),那么一次快速幂的时间复杂度是\(O(\log^2n)\),总体来说就是\(O(n\log^3n)\)。我们先不讨论优化,这个题还要注意的是欧拉定理的适用条件,对于\(\gcd(a,p)\not=1\)来说,有

$$\left\{\begin{align}
& a^b\equiv a^{b\bmod \varphi(p)+\varphi(p)}&,b\ge \varphi(p)\\
& a^b\equiv a^b\ &,b<\varphi(p)
\end{align}\right.$$

   因此每次取模之前都要判断是否达到了\(\varphi(p)\),如果达到了,取模之后还要加上一个\(\varphi(p)\)。这就是这个题的坑点,有两个\(0\)比较多的点就是这样被卡WA的。注意求欧拉函数是要\(O(\sqrt{n})\)的时间来筛素数和计算的,利用欧拉筛和\(\varphi()\)的计算式就可以了。

 

   说完细节,我们接着来看如何在\(O(n\log^2n)\)的时间内完成这个题。我们发现快速幂的底数永远是\(c\),那么我们需要预处理出\(c\)的所有次幂。但是因为指数\(\pmod \varphi(p)\)之后的范围仍然很大,也能达到\(10^8\)的数量级。因此我们可以分块打表。也就是说,预处理出\(c^i,i\in[0,10000]\),以及\(c^{10000\cdot j},j\in[0,10000]\)。此时快速幂在经过\(O(\sqrt{p})\)的预处理后,做到了\(O(1)\)求;此时求值过程和快速幂调用都不要忘了欧拉定理的分段范围。同时对于每一阶都要分别处理出它们的幂,因为模数不同,此时时间复杂度变为\(O(n\log^2n+\sqrt{n}\log n)\Rightarrow O(n\log^2n)\)。

 

   代码结构很简单,只不过套用了两个手写的数据结构就显得很长了。

 

Code:

#include<cstdio>
#include<cstdlib>
#include<cstring>
struct node//平衡树部分
{
    int key,sz,rdm;
    //key存的是位置编号
    node *ls,*rs;
    node(int key)
    {
        this->key=key;
        sz=1;
        rdm=rand();
        ls=NULL;
        rs=NULL;
    }
    node(){}
    void maintain()
    {
        sz=(ls?ls->sz:0)+1+(rs?rs->sz:0);
    }
}*root=NULL;
node *Merge(node *a,node *b)
{
    if(!a||!b)
        return a?a:b;
    if(a->rdm<b->rdm)
    {
        a->rs=Merge(a->rs,b);
        a->maintain();
        return a;
    }
    b->ls=Merge(a,b->ls);
    b->maintain();
    return b;
}
void split(node *rt,int x,node *&a,node *&b)
{
    if(!rt)
    {
        a=NULL;
        b=NULL;
        return;
    }
    if(rt->key<=x)
    {
        a=rt;
        split(a->rs,x,a->rs,b);
    }
    else
    {
        b=rt;
        split(b->ls,x,a,b->ls);
    }
    rt->maintain();
    return;
}
void Insert(int x)
{
    node *a,*b;
    split(root,x,a,b);
    root=Merge(Merge(a,new node(x)),b);
}
void Delete(node *&rt,int x)
{
    node *a,*b,*c;
    split(rt,x-1,a,b);
    split(b,x,b,c);
    b=Merge(b->ls,b->rs);
    rt=Merge(Merge(a,b),c);
}
//O(\sqrt{n})求欧拉函数
int pri[10000],cnt=0;
int phi(int p)
{
    int ans=p;
    for(int i=1;i<=cnt;++i)
    {
        if(p%pri[i]==0)
            ans=ans/pri[i]*(pri[i]-1);
        while(p%pri[i]==0)
            p/=pri[i];
    }
    if(p>1)
        ans=ans/p*(p-1);
    return ans;
}
int changed[50005],a[50005];//每个位置改变了几次、初始值
int mxcnt=0,n,c;
int stk[50005],top=0;
long long C[50005];
int lowbit(int x)//树状数组部分
{
    return x&(-x);
}
void change(int p,int x)
{
    while(p<=n)
    {
        C[p]+=x;
        p+=lowbit(p);
    }
}
long long ask(int p)
{
    long long ans=0;
    while(p)
    {
        ans=ans+C[p];
        p-=lowbit(p);
    }
    return ans;
}
int Phi[1000];//第几阶的模数
bool is[10050];
long long Pow[50][10001],Pow10000[50][10000];
int qpow(int x,int y,int k,int p)//x是c,y是原a[i],k是需要几阶,p是当前处于第几阶
{
    if(k)
        y=qpow(c,y,k-1,p+1);
    return Pow[p][y%10000]*Pow10000[p][y/10000]>=Phi[p]
            ?Pow[p][y%10000]*Pow10000[p][y/10000]%Phi[p]+Phi[p]:Pow[p][y%10000]*Pow10000[p][y/10000];
}
void dfs(node *rt)//对平衡树分出来的一棵子树全部遍历一遍
{
    int now=qpow(c,a[rt->key],changed[rt->key],0);
    changed[rt->key]++;
    change(rt->key,now-ask(rt->key)+ask(rt->key-1));
    if(changed[rt->key]==mxcnt+1)
    {
        stk[++top]=rt->key;
        a[rt->key]=now;
    }
    if(rt->ls)
        dfs(rt->ls);
    if(rt->rs)
        dfs(rt->rs);
}
void init(int p)//线筛
{
    memset(is,1,sizeof(is));
    for(int i=2;i*i<=p;++i)
    {
        if(is[i])
            pri[++cnt]=i;
        for(int j=1;j<=cnt&&(i*pri[j])*(i*pri[j])<=p;++j)
        {
            is[i*pri[j]]=0;
            if(i%pri[j]==0)
                break;
        }
    }
}
int main()
{
    int m,p;
    scanf("%d%d%d%d",&n,&m,&p,&c);
    init(p);
    Phi[0]=p;
    while(p>1)
    {
        ++mxcnt;
        p=phi(p);
        Phi[mxcnt]=p;
    }
    Pow[0][0]=1;
    for(int j=1;j<=10000;++j)
        Pow[0][j]=Pow[0][j-1]*c%Phi[0];//第一阶不用+Phi[i],可以特判,不过加上也没有错
    for(int i=1;i<=mxcnt;++i)
    {
        Pow[i][0]=1;
        for(int j=1;j<=10000;++j)
            if(Pow[i][j-1]*c>=Phi[i])
                Pow[i][j]=Pow[i][j-1]*c%Phi[i]+Phi[i];
            else
                Pow[i][j]=Pow[i][j-1]*c;
    }
    Pow10000[0][0]=1;
    for(int j=1;j<=10000;++j)
        Pow10000[0][j]=Pow10000[0][j-1]*Pow[0][10000]%Phi[0];
    for(int i=1;i<=mxcnt;++i)
    {
        Pow10000[i][0]=1;
        for(int j=1;j<=10000;++j)
            if(Pow10000[i][j-1]*Pow[i][10000]>=Phi[i])
                Pow10000[i][j]=Pow10000[i][j-1]*Pow[i][10000]%Phi[i]+Phi[i];
            else
                Pow10000[i][j]=Pow10000[i][j-1]*Pow[i][10000];
    }
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        Insert(i);
        change(i,a[i]);
    }
    int op,l,r;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&op,&l,&r);
        if(op==0)
        {
            node *a,*b,*c;
            split(root,l-1,a,b);
            split(b,r,b,c);
            top=0;
            if(b)
                dfs(b);
            for(int j=1;j<=top;++j)
                Delete(b,stk[j]);
            root=Merge(Merge(a,b),c);
        }
        else
            printf("%lld\n",(ask(r)-ask(l-1))%Phi[0]);
    }
    return 0;
}

说点什么

avatar
  Subscribe  
提醒
/* */