LOJ2142 [SHOI2017]相逢是问候

神秘扩展欧拉定理 + 均摊线段树。

题意:维护一个长度为 n 的序列 a,修改是对 [l,r]ai 变为 cai,或者询问 i=lrai,输出 modp 的答案就可。n,c 开始给定,n,q×5×104p108

显然 ai 的值仅和 ai 的初始值以及修改操作覆盖的次数有关。看到如此庞大的数,考虑扩展欧拉定理:ananmodφ(p)+φ(p)(modp),这时需要保证 nφ(p)

如果不操作,那么和 aimodp 的值有关;如果操作一次,和 aimodφ(p) 有关;如果操作两次,即 caimodφ(p) 有关,即 aimodφ(φ(p)) 有关……这样下去,当 φ(φ(p))=1 的时候,这个答案和 ai 和操作次数都没有关了,它变成了一个定值(和操作次数无关是因为再操作相当于修改 ai,没有什么用了)。

这样我们只需要维护前几次操作。大概是多少次呢?

结论:该深度为 O(logp) 级别。

证明:对于偶数来说,φ(p)p2;对于奇数来说,2|φ(p),可以由 φ(p) 的定义式得到。

这样我们就只需要暴力计算前 O(logn) 项即可。计算由于是暴力计算,而且不能利用前面的信息,只能依次按照原式计算。时间复杂度 O(nlog3n+qlogn),不太能过。

注意到我们的一个 log 是来自于快速幂的,但是容易发现底数只有一种,模数只有 O(logp) 种,于是光速幂预处理,可以做到 O(nlog2n+qlogn+qlogp),可以通过。

注意扩展欧拉定理只能在 nφ(p) 时才能使用,所以需要判断指数是否 φ(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
struct LPow {
static const int B = 32768;
int sk[B], bk[B], Mod;
LPow() : Mod(1) {}

void init(int _Mod)
{
Mod = _Mod;
sk[0] = bk[0] = 1;
for (int i = 1; i < B; ++ i) sk[i] = (LL) sk[i - 1] * c % Mod;
bk[1] = (LL) sk[B - 1] * c % Mod;
for (int i = 2; i < B; ++ i) bk[i] = (LL) bk[i - 1] * bk[1] % Mod;
}

int lpow(int x) { return bk[x >> 15] * (LL) sk[x & (B - 1)] % Mod; }
} lp[70];

int phi(int n)
{
int res = n;
for (int i = 2; i <= n / i; ++ i)
if (n % i == 0) {
res /= i, res *= (i - 1);
while (n % i == 0) n /= i;
}
if (n ^ 1) res /= n, res *= (n - 1);
return res;
}

struct Node {
int l, r, cnt, sum;
} tr[N << 2];

void pushup(int x)
{
adj(tr[x].sum = tr[x << 1].sum + tr[x << 1 | 1].sum - Mod);
tr[x].cnt = std::min(tr[x << 1].cnt, tr[x << 1 | 1].cnt);
}

void build(int x, int l, int r)
{
tr[x] = {l, r, 0, a[l]};
if (l == r) return;
int mid = (l + r) >> 1;
build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
pushup(x);
}

void modify(int x, int l, int r)
{
if (tr[x].cnt > lim || tr[x].l > r || tr[x].r < l) return;
if (tr[x].l == tr[x].r) {
tr[x].cnt ++;
int cur = a[tr[x].l];
bool flag = false;
for (int i = tr[x].cnt; i; -- i)
{
int tmp = cur;
LL res = 1;
while (tmp -- && !flag) {
res *= c;
if (res >= lp[i].Mod) {
flag = true;
break;
}
}
cur = lp[i].lpow(cur);
if (flag || lp[i].Mod == 1) cur += lp[i].Mod;
}
tr[x].sum = cur % Mod;
return;
}
modify(x << 1, l, r), modify(x << 1 | 1, l, r);
pushup(x);
}

int query(int x, int l, int r)
{
if (tr[x].l > r || tr[x].r < l) return 0;
if (tr[x].l >= l && tr[x].r <= r) return tr[x].sum;
int tmp;
return adj(tmp = query(x << 1, l, r) + query(x << 1 | 1, l, r) - Mod);
}

Related Issues not found

Please contact @mydcwfy to initialize the comment