洛谷 P3747 相逢是问候 题解【树状数组】【欧拉定理】【快速幂】【平衡树】
点击量：187
一道充分考察了扩展欧拉定理的题目，并且细节要求比较多。
题目描述
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;
}
… [Trackback]
[…] Here you will find 65191 additional Info to that Topic: wjyyy.top/1843.html […]