算法

【题解】P3747 相逢是问候

麻烦得很

题意

定义函数 $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{aligned} &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{aligned} $$

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

$$ \begin{cases} a_i &\pmod {\varphi^{z-x}(p)}&(x又因为 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^3 p )$ 的做法，得到 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}$ 拼接即可。

代码

（还挺快的）

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104

#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 的结果，这样我们就可以在计算欧拉函数的过程中免于讨论的烦恼。

1

inline ll eulermod(ll x,ll mod){return x<=mod?x:(x%mod+mod);}

  • 可能有人会问：在计算 $f^x(a_i)\ (\operatorname{eulermod}\ p)$ 时，会不会出现本来 $f^x(a_i)$ 是大于等于 p 的， 但是由于计算 $f^{x-1}(a_i)$ 函数返回的结果是 $\operatorname{eulermod}\ \varphi(p)$ 意义下的，从而导致算出来的 $f((f^{x-1}(a_i)\ (\operatorname{eulermod}\ p)) < p$？

  • 答案是否定的，证明如下：

    • 若 $c=0/1$，显然 $f^x(a_i)
    • 若 $c\ge 2$：
      • 如果 $f^{x-1}(a_i)< \varphi(p)$：则 $f^{x-1}(a_i)=f^{x-1}(a_i)\ (\operatorname{eulermod}\ \varphi (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)\ (\operatorname{eulermod}\ p))$，上述问题同样不存在，证毕。