隐藏
「SHOI2017」相逢是问候 - 线段树+扩展欧拉定理 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「SHOI2017」相逢是问候 - 线段树+扩展欧拉定理

题目大意

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

    一共有$m$个操作,可以分为两种:

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

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


题目分析

第一眼:又是类似「THUSC2015」平方运算的强行题,找循环节。
第二眼:好像不是。。。
想法一:那就是线段树瞎搞一波强行$\log n$了。
第三眼:好像不能取模啊。。。
想法二:$p$应该是素数,欧拉函数强行取模。
第四眼:好像不是素数。。。搞毛啊。。。

冷静分析一波。

嗯,好像以前用过一个不需要$a,p$互素的降幂方法。
没错,上扩展欧拉定理

其中$x\ge\varphi(m)$。

嗯,很不错。
然后我们套用到$0$操作上。

再来一层:

发现还可以继续套公式(建议放大食用):

这样不断嵌套,在$O(\log n)$次嵌套后$\varphi(\varphi(\cdots (p)))$就会变成$1$(见这里的证明),因此原式的值就不会变了。
若出现上述情况,在线段树中就不必要再次修改,直接返回即可。

接下来我们考虑快速修改维护答案。
原式中中括号部分是没法进行取模操作的,因此无法对答案直接维护。转而考虑维护嵌套次数。
因为有上述公式,因此给定初值与嵌套次数,就可以在$O(\log n)$的时间内计算出当前的值。
故每次修改,若未超过阈值,增加一下嵌套次数,重算一下答案即可。

考虑时间复杂度,每次修改的时间是$O(\log^3 n)$的,因为需要进行快速幂。
这会被卡常卡得很惨,可以采取一些奇奇怪怪的技巧来避免快速幂。
要求的是$c^x\bmod p(x\le 2^{32})$,利用meet-in-the-middle的思想,先预处理出$pow_1(n)=c^n\bmod p(n\le 2^{16})$以及$pow_2(n)=c^n(n\le 2^{16})$平方$16$次$\bmod p$的值,然后询问$c^x\bmod p$可以通过分两段查表解决:

1
pow1[b&65535]*pow2[b>>16]%mod

另外,根据Sengxian大佬的验证:

指数循环节公式只在$x\ge \varphi(n)$时成立,在 UVa 10692 中,用试乘来判断是否$\ge \varphi(n)$,我们在试乘的时候,是以上一层返回的取模后结果作为幂试乘,这样并不准确,应该使用上一层的答案进行试乘。但是放心,经过验证,这样做没有任何问题。因为如果$x\ge \varphi(n)$,那么$a^x\ge n$只在$n=6$时不成立,经过验证,这个带来的一系列后续影响不会造成答案的错误,所以大可放心使用。

分析时间复杂度,每个数在$O(\log n)$次修改后会不变,消耗$O(n\log^2 n)$的时间。故总时间复杂度为:

可能有点小卡常。


代码

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
#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}

int Cal_Phi(int x) {
int ans=x;
for(int i=2; i<=sqrt(x); i++)
if(x%i==0) {
ans-=ans/i;
while(x%i==0)x/=i;
}
if(x>1)ans-=ans/x;
return ans;
}

const int maxn=50005;

vector<int> mods;
int n,m,p,c,a[maxn],cnt[35],pow1[35][1<<16],pow2[35][1<<16];

int Pow(int b,int id,int mod) {
if(b<cnt[id])return pow1[id][b];
return 1ll*pow1[id][b&65535]*pow2[id][b>>16]%mod+mod;
}

int Cal(int a,int cnt,int times) {
int mod=times>0?mods[times]:1;
if(c==1)return c%mod;
if(cnt==0)return a<mod?a:a%mod+mod;
return Pow(Cal(a,cnt-1,times-1),times,mod);
}

struct Segment_Tree {
struct Tree {
int left,right;
int sum,cnt;
} tree[maxn<<2];
#define ls index<<1
#define rs index<<1|1
void build(int index,int Left,int Right) {
tree[index].left=Left,tree[index].right=Right;
if(Left==Right) {tree[index].sum=a[Left];return;}
int mid=(Left+Right)>>1;
build(ls,Left,mid);
build(rs,mid+1,Right);
push_up(index);
}
void push_up(int index) {
tree[index].sum=(tree[ls].sum+tree[rs].sum)%p;
tree[index].cnt=min(tree[ls].cnt,tree[rs].cnt);
}
void modify(int index,int Left,int Right) {
if(Right<tree[index].left||Left>tree[index].right||tree[index].cnt>=mods.size())return;
if(tree[index].left==tree[index].right) {tree[index].sum=Cal(a[tree[index].left],++tree[index].cnt,mods.size()-1)%p;return;}
modify(ls,Left,Right);
modify(rs,Left,Right);
push_up(index);
}
int query(int index,int Left,int Right) {
if(Right<tree[index].left||Left>tree[index].right)return 0;
if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index].sum;
return (query(ls,Left,Right)+query(rs,Left,Right))%p;
}
} st;

int main() {
n=Get_Int();
m=Get_Int();
p=Get_Int();
c=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
int now=p;
while(now>1)mods.push_back(now),now=Cal_Phi(now);
mods.push_back(now);
reverse(mods.begin(),mods.end());
for(int i=0; i<mods.size(); i++) {
pow1[i][0]=1;
for(int j=1; j<(1<<16); j++)pow1[i][j]=1ll*pow1[i][j-1]*c%mods[i];
for(int j=0; j<(1<<16); j++) {
pow2[i][j]=pow1[i][j];
for(int k=1; k<=16; k++)pow2[i][j]=1ll*pow2[i][j]*pow2[i][j]%mods[i];
}
if(c>1) {
int now=1;
while(now<mods[i])now*=c,cnt[i]++;
}
}
st.build(1,1,n);
while(m--) {
int opt=Get_Int(),x=Get_Int(),y=Get_Int();
if(opt==0)st.modify(1,x,y);
else printf("%d\n",st.query(1,x,y));
}
return 0;
}
姥爷们赏瓶冰阔落吧~