【题解】P3747 相逢是问候

麻烦得很

Posted by ethan-zhou on February 20, 2021

题意

定义函数 $f(x)=c^x$

维护给定序列 $a_i$,支持两种操作(p,c 由输入给定):

  • 将数列第 l 到 r 项中的每一项 $a_i$,赋值为 $f(a_i)$

  • 查询 $\sum_{i=l}^{i\leq r}a_i\ \pmod p$

分析

计算方法

首先考虑一项如何计算,由扩展欧拉定理(详见 OI-wiki

\[a^b\equiv \begin{cases} a^{b\bmod\varphi(p)},\,&\gcd(a,\,p)=1\\ a^b,&\gcd(a,\,p)\ne1,\,b<\varphi(p)\\ a^{b\bmod\varphi(p)+\varphi(p)},&\gcd(a,\,p)\ne1,\,b\ge\varphi(p) \end{cases} \pmod p\]

可以转化问题为:

\[\begin{align} &f^x(a_i) \pmod p\\ =&\begin{cases} f(f^{x-1}(a_i))&(f^{x-1}(a_i)<\varphi(p))\\ f(f^{x-1}(a_i)\bmod \varphi(p)+\varphi(p))&(f^{x-1}(a_i)\ge\varphi(p)) \end{cases} \end{align}\]

以此类推,就能递归求解答案,不妨设 $\varphi ^t (p)=1$ 当且仅当 $t\ge z$,则递归的边界为:

\[\begin{cases} a_i &\pmod {\varphi^{z-x}(p)}&(x<z)\\ f^{x-z}(a_i) &\pmod 1&(x\ge z) \end{cases}\]

又因为 z 的大小是 $\log p$ 量级的,所以递归次数也是 log 量级的,每次计算需要调用一次快速幂(可以优化),所以算法复杂度为两个 log。

关于 z 大小的证明:

  • p 为偶数时,$\varphi(p)\leq \frac p 2$
  • p为奇数时,$\varphi(p)$ 为偶数

计算次数

通过刚才的计算方法,我们发现:若 $x\ge z$,则函数在边界处的返回值为 0,接下来整个计算过程都与 x 无关。也即:每个元素 $a_i$ 在操作了 z 次之后,其值就不再变化

所以,我们可以用一个线段树来维护区间和,以及区间内操作次数最少的元素操作了多少次,修改时,如果区间内的最少操作次数小于 z,那么就暴力计算之,并更新线段树。这样就能实现一个 $O(n\log n \log p^2+m\log n)$ 的做法,得到 90 分的好成绩。

小优化

考虑如何优化前文所述的快速幂,因为底数 c 是已知的,而指数小于等于 p,于是我们可预处理出 $c^i\ (i\in[1, \sqrt p] )$ 以及 $c^{i \times \sqrt p}\ (i\in[1, \sqrt p])$,每次求快速幂直接把 $c^{i\ \bmod \sqrt p}$ 与 $c^{\lfloor\frac i {\sqrt p }\rfloor\times \sqrt p}$ 拼接即可。

代码

(还挺快的)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MXN=5e4+5;
const ll MXD=65;
const ll LG=14;
ll n,m,P,c;
ll arr[MXN];
ll phip[MXD],phic;
ll powc1[MXD][(1<<LG)+5],powc2[MXD][(1<<LG)+5];
inline ll phi(ll x){
	ll res=x;
	for(int i=2;i*i<=x;i++)
		if(x%i==0){
			while(x%i==0)x/=i;
			res-=res/i;
		}
	if(x!=1)res-=res/x;
	return res;
}
//方便处理扩展欧拉定理
inline ll eulermod(ll x,ll mod){return x<=mod?x:(x%mod+mod);}
inline ll qmod(ll x,ll mod){return x<mod?x:x-mod;}
inline ll qpow(ll y,ll modi){return eulermod(powc1[modi][y&((1<<LG)-1)]*powc2[modi][y>>LG],phip[modi]);}
//第 0 层的数,当前剩下的嵌套层数,当前模数的下标
inline ll cal(ll va,ll cflr,ll cphi){
	if(!cflr)return eulermod(va,phip[cphi]);
	if(cphi==phic)return c?1:0;
	return qpow(cal(va,cflr-1,cphi+1),cphi);
}
inline void init(){
	/*
	 * 初始化 p 进行嵌套 phi 的结果
	 * p 经过 log 层 phi 嵌套变为 1
	 * i 为偶数,phi(i) < i/2
	 * i 为奇数,phi(i) 为偶数
	 */
	phip[0]=P;
	while(phip[phic]!=1){
		phip[phic+1]=phi(phip[phic]);
		phic++;
	}
	//初始化快速幂
	for(int i=0;i<=phic;i++){
		powc1[i][0]=powc2[i][0]=1;
		for(int j=1;j<=(1<<LG);j++)
			powc1[i][j]=eulermod(powc1[i][j-1]*c,phip[i]);
		for(int j=1;j<=(1<<LG);j++)
			powc2[i][j]=eulermod(powc2[i][j-1]*powc1[i][1<<LG],phip[i]); 
	}
}
namespace segt{
	struct node{
		ll sum,mnfl;//和,区间最少嵌套次数
	}t[MXN<<2];
#define ls (p<<1)
#define rs (p<<1|1)
	inline void pushu(ll p){
		t[p].sum=qmod(t[ls].sum+t[rs].sum,P);
		t[p].mnfl=min(t[ls].mnfl,t[rs].mnfl);
	}
	void build(ll p,ll l,ll r){
		if(l==r){
			t[p].mnfl=0;
			t[p].sum=arr[l];
			return;
		}
		ll mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		pushu(p);
	}
	void upd(ll p,ll l,ll r,ll ul,ll ur){
		if(l==r){
			t[p].sum=qmod(cal(arr[l],++t[p].mnfl,0),P);
			return;
		}
		//mnfl>phic就不用更新了
		//注意边界
		ll mid=(l+r)>>1;
		if(ul<=mid && t[ls].mnfl<=phic)upd(ls,l,mid,ul,ur);
		if(ur>mid && t[rs].mnfl<=phic)upd(rs,mid+1,r,ul,ur);
		pushu(p);
	}
	ll que(ll p,ll l,ll r,ll ql,ll qr){
		if(ql<=l && r<=qr)return t[p].sum;
		ll mid=(l+r)>>1,res=0;
		if(ql<=mid)res=que(ls,l,mid,ql,qr);
		if(qr>mid)res=qmod(res+que(rs,mid+1,r,ql,qr),P);
		return res;
	}
}
int main(){
	scanf("%lld%lld%lld%lld",&n,&m,&P,&c);
	for(int i=1;i<=n;i++)scanf("%lld",arr+i);
	init();segt::build(1,1,n);
	while(m--){
		ll op,l,r;
		scanf("%lld%lld%lld",&op,&l,&r);
		if(op)printf("%lld\n",segt::que(1,1,n,l,r));
		else segt::upd(1,1,n,l,r);
	}
	return 0;
}

实现细节

  • 代码中,我用 phip[i] 预处理出了 $\varphi^i(p)$ 的值,其中 phic+1 则对应前文中 $z$ 的定义。

  • 我还定义了一个函数 eulermod(x,y),表示以欧拉定理中的形式处理 x 模 y 的结果,这样我们就可以在计算欧拉函数的过程中免于讨论的烦恼。
    inline ll eulermod(ll x,ll mod){return x<=mod?x:(x%mod+mod);}
    
  • 可能有人会问:在计算 $f^x(a_i)\ (eulermod\ p)$ 时,会不会出现本来 $f^x(a_i)$ 是大于等于 p 的, 但是由于计算 $f^{x-1}(a_i)$ 函数返回的结果是 $eulermod\ \varphi(p)$ 意义下的,从而导致算出来的 $f((f^{x-1}(a_i)\ (eulermod\ p)) < p$?

  • 答案是否定的,证明如下:

    • 若 $c=0/1$,显然 $f^x(a_i)<p$,没有上述问题
    • 若 $c\ge 2$:
      • 如果 $f^{x-1}(a_i)< \varphi(p)$:则 $f^{x-1}(a_i)=f^{x-1}(a_i)\ (eulermod\ p)$ 没有上述问题
      • 如果 $f^{x-1}(a_i)\ge \varphi(p)$:则因为 $\log_2p \le \varphi(p)$,所以 $p \le f(\varphi (p)) \le f((f^{x-1}(a_i)\ (eulermod\ p))$,上述问题同样不存在,证毕。

作者:@ethan-enhe
本文为作者原创,转载请注明出处:本文链接



icon