[bzoj 4869] [Shoi2017]相逢是问候

Informatik verbindet dich und mich. 信息将你我连结。

一个长度为n的数组a, m个操作, 常数c, p. 操作分为两种: - 区间赋值 把ai替换为c^ai - 区间求和 结果模p

(1≤n,m≤5*10^4, 1≤p≤10^8, 0<c<p, 0≤ai<p) 这个毕老师肯定有什么感情故事......

Po姐说: "这不是上帝与集合的正确用法吗? " 于是先去做了一下那题.

处理底数和模数不互质的情况, 我用的是中国剩余定理. 从题解中学到了一个扩展欧拉定理:

发现正好可以用来解决本题 - 对于任何, 上式均给出. 而.

ai可以等于0, 所以需要将再展开一层, 才能变成上面所述的情形:

phi[++K] = 1;

我以为只是为了保证算法的效率, 然后WA了. 找了一下这个推论的证明, 发现这个条件是不容忽视的.

下面用于判断这个条件的代码其实是错误的......它只是一个充分条件. 不过错误暴露出来的机会比较少. 见 Sengxian's Blog Orz

要做到绝对正确, 我的想法是, 保留取模前的幂和n的min. 这样做常数又有所增大. QAQ

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a), i##_end = (b); i < i##_end; ++i)
#define per(i, a, b) for (int i = (a), i##_end = (b); i >= i##_end; --i)
#define ALL 1, 1, n

using namespace std;

typedef long long ll;

const int N = 50000;

int c, p, K, a[N+1], phi[100];

ll fpm(ll x, ll n, ll m, bool& b)
{
	ll y = 1;
	b = false;
	for (; n; n >>= 1, b |= (x *= x) >= m && n, x %= m)
		if (n & 1)
			b |= (y *= x) >= m, y %= m;
	return y;
}

int cal(int a, int k)
{
	bool b;
	a = a < phi[k] ? a : a % phi[k] + phi[k];
	per (i, k-1, 0) {
		a = fpm(c, a, phi[i], b);
		a += b ? phi[i] : 0;
	}
	return a % p;
}

struct Seg {
	int v[N*4], x[N*4];

	void up(int o)
	{
		v[o] = (v[o*2] + v[o*2+1]) % p;
		x[o] = min(x[o*2], x[o*2+1]);
	}
	
	void build(int o, int l, int r)
	{
		if (l == r) {
			v[o] = a[l];
			return;
		}
		int m = (l+r)/2;
		build(o*2, l, m);
		build(o*2+1, m+1, r);
		up(o);
	}
	
	void modify(int L, int R, int o, int l, int r)
	{
		if (x[o] >= K) return;
		if (l == r) {
			v[o] = cal(a[l], ++x[o]);
			return;
		}
		int m = (l+r)/2;
		if (L <= m) modify(L, R, o*2, l, m);
		if (R > m) modify(L, R, o*2+1, m+1, r);
		up(o);
	}

	int query(int L, int R, int o, int l, int r)
	{
		if (L <= l && r <= R) return v[o];
		int m = (l+r)/2, s = 0;
		if (L <= m) s = query(L, R, o*2, l, m);
		if (R > m) (s += query(L, R, o*2+1, m+1, r)) %= p;
		return s;
	}
} T;

int getPhi(int n)
{
	int r = n;
	for (int d = 2; d*d <= n; ++d)
		if (n % d == 0) {
			r = r/d*(d-1);
			do {
				n /= d;
			} while (n % d == 0);
		}
	if (n > 1) r = r/n*(n-1);
	return r;
}

int main()
{
	int n, m;
	scanf("%d%d%d%d", &n, &m, &p, &c);
	rep (i, 1, n+1) scanf("%d", a+i);
	phi[0] = p;
	while (phi[K] > 1) {
		phi[K+1] = getPhi(phi[K]);
		++K;
	}
	phi[++K] = 1;
	T.build(ALL);
	while (m--) {
		int o, l, r;
		scanf("%d%d%d", &o, &l, &r);
		if (o) printf("%d\n", T.query(l, r, ALL));
		else T.modify(l, r, ALL);
	}
	return 0;
}