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

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

0%

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

发表于 更新于 分类于 Valine：

题目大意

    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;
}
相关文章
姥爷们赏瓶冰阔落吧~