P3747 [六省联考 2017] 相逢是问候

, ,

Description

https://www.luogu.com.cn/problem/P3747

Solution

前置芝士

对于上面这题。考虑根据扩展欧拉定理计算。记 $F(x,n,p)$ 表示 $2^x$ 叠 $n$ 次的值之后模 $p$ 的值。则有 $F(x,n,p)=2^{F(x,n+1,\phi(p))+\phi (p)}$。因为上面是无穷大 $\ge \phi (p)$，所以要加上 $\phi (p)$。

递归边界是 $p=1$，此时返回 $0$。

现在计算递归的次数。我们基于如下事实：

  • 对于 $p>1$，$\phi (p)$ 为偶数。
  • 若 $p$ 为偶数，则 $\phi (p)\le p/2$。

所以 $p$ 在 $O(\log p)$ 次会变成 $1$。

回到本题。有 $a_i$ 的变化次数为 $O(\log p)$，所以如果不变了以后就不操作，否则暴力操作。用线段树维护。注意是否 $\ge \phi (p)$ 的判断和 $c=1,a_i=0$ 等特殊情况。

判断是否不变一种比较愚蠢的方法是操作了 $O(\log n)$ 次就不操作。比较优雅的方法是当递归到 $p=1$ 且返回 $1$ 就可以之后都不操作。

而判断这次和上次相同的方法是错误的。有 hack。

对每个可能取到的 $p$ 值预处理快速幂，最后复杂度 $O(n\log w(\log n+\log w))$

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define ull unsigned long long
#define maxn 50005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
// ll power(ll x,int y,int mod) {
// 	ll sum=1;x%=mod;
// 	while (y) {
// 		if (y&1) sum=sum*x%mod;
// 		x=x*x%mod;y>>=1;
// 	}
// 	return sum;
// }
int calc(int n) {
	int ans=n,now=n,i;
	for (i=2;i*i<=n;i++) if (now%i==0) {
		ans=ans/i*(i-1);
		while (now%i==0) now/=i;
	}
	if (now>1) ans=ans/now*(now-1);
	return ans;
}
int n,m,p,c,g[maxn],a[maxn];
struct node {
	int Max,sum,nums;
}f[maxn<<2];
void pushup(int rt) {
	f[rt].Max=max(f[rt<<1].Max,f[rt<<1|1].Max);
	f[rt].sum=(f[rt<<1].sum+f[rt<<1|1].sum)%p;
}
void build(int l,int r,int rt) {
	if (l==r) return f[rt].Max=1,f[rt].sum=a[l],void();
	int mid=l+r>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	pushup(rt);
}
int L,flag=0;
int pw1[105][10005],pw2[105][10005];
const int base=1e4;
int power(int x,int y,int id) {
	return pw1[id][y%base]*pw2[id][y/base]%g[id];
}
int F(int x,int n,int deep,int p) {
	if (p==1) {
		if (n==0&&a[L]==0) return 0;
		return flag=1,1;
	}
	if (n==0) {
		if (a[L]<p) return a[L];
		else return a[L]%p+p;
	}
	int m=g[deep+1];
	if (x==1) return flag=1,x;
	else {
		int tmp=F(x,n-1,deep+1,m),i,res=1;
		for (i=1;i<=tmp;i++) {
			res=res*x;
			if (res>p) return power(x,tmp,deep)+p;
		}
		return res;
	}
}
void Update(int l,int r,int rt,int head,int tail) {
	if (!f[rt].Max) return ;
	if (l==r) {
		L=l;flag=0;
		f[rt].nums++;
		int tmp=F(c,f[rt].nums,0,p)%p;
		if (flag) f[rt].Max=0;
		f[rt].sum=tmp;
		return ;
	}
	int mid=l+r>>1;
	if (head<=mid) Update(l,mid,rt<<1,head,tail);
	if (tail>mid)  Update(mid+1,r,rt<<1|1,head,tail);
	pushup(rt);
}
int Query(int l,int r,int rt,int head,int tail) {
	if (head<=l&&r<=tail) return f[rt].sum;
	int mid=l+r>>1,res=0;
	if (head<=mid) res+=Query(l,mid,rt<<1,head,tail);
	if (tail>mid) res+=Query(mid+1,r,rt<<1|1,head,tail);
	return res%p;
}
signed main(void){
	int i,op,l,r,j;
	read(n);read(m);read(p);read(c);
	g[0]=p;
	for (i=1;i<=100;i++) {
		g[i]=calc(g[i-1]);
	}
	for (j=0;j<=100;j++) {
		for (pw1[j][0]=1%g[j],i=1;i<=base;i++) pw1[j][i]=pw1[j][i-1]*c%g[j];
		for (pw2[j][0]=1%g[j],i=1;i<=base;i++) pw2[j][i]=pw2[j][i-1]*pw1[j][base]%g[j];
	}
	for (i=1;i<=n;i++) read(a[i]);
	build(1,n,1);
	while (m--) {
		read(op);read(l);read(r);
		if (op==0) Update(1,n,1,l,r);
		else printf("%lld\n",Query(1,n,1,l,r));
	}
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<endl;
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i