https://ac.nowcoder.com/acm/contest/7329

E. 子串

 

题意：给出一个长度为 nn 排列 pip_i，规定一个区间 [l,r](l<=r)[l,r] (l<=r) 是 fair 的，当且仅当区间中最小值等于 ll 并且最大值等于 rr，求 fair 区间的个数。

单调栈+二分+扫描线+树状数组

fair区间可以理解为一堆连续的数打乱后放在这个区间里。

对于一对 (x,pos[x])(x,pos[x])，如果一个区间的一端在该范围内，另一端不在，那么这个区间一定不合法。因为这个区间就不能够包含等于下标的所有数。

对于每个左端点，合法的右端点必须满足区间范围内的最小值不能小于左端点位置的下标。

对于每个右端点，合法的左端点必须满足区间范围内的最大值不能大于右端点位置的下标。

以对每个右端点求合法左端点范围为例：从小到大遍历作为右端点，因为我们需要的是恰好不合法的点，所以单调栈中维护从大到小，在单调栈里二分，得到位于边界的位置。

对于一个合法区间，等价于满足左端点在右端点的合法范围内，且右端点在左端点的合法范围内。

动态的点的计数问题可以考虑扫描线。

从小到大遍历，作为左端点，一个右端点仅当遍历到他的合法左端点范围时被激活，用扫描线可以控制激活和关闭。

树状数组维护前缀和，得到位于当前点合法右端点范围内的被激活的点的个数。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;
const ll mod = 998244353;
int n;
int a[N];
struct X
{
	int p, v, op;
	bool operator<(const X& b)const {
		return p > b.p;
	}
};
priority_queue<X>q;
int tp, st[N];
int l[N], r[N];
int sum[N];
void add(int q, int x) {
	for (int i = q; i <= n + 1; i += (i&-i))sum[i] += x;
}
int qry(int r) {
	int res = 0;
	for (int i = r; i > 0; i -= (i&-i))res += sum[i];
	return res;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; i++) {
		while (tp&&a[st[tp]] < a[i])tp--;
		st[++tp] = i;
		int L = 1, R = tp;
		while (L < R) {
			int mid = (L + R) / 2;
			if (a[st[mid]] <= i)R = mid;
			else L = mid + 1;
		}
		if (a[st[L]] > i)l[i] = n + 1;
		else if (L == 1)l[i] = 0;
		else l[i] = st[L - 1] + 1;		//恰好合法的位置是恰好不合法的位置+1
	}
	tp = 0;
	memset(st, 0, sizeof(st));
	for (int i = n; i >= 1; i--) {
		while (tp&&a[st[tp]] > a[i])tp--;
		st[++tp] = i;
		int L = 1, R = tp;
		while (L < R) {
			int mid = (L + R) / 2;
			if (a[st[mid]] >= i)R = mid;
			else L = mid + 1;
		}
		if (a[st[L]] < i)r[i] = 0;
		else if (L == 1)r[i] = n + 1;
		else r[i] = st[L - 1] - 1;		//恰好合法的位置是恰好不合法的位置-1
	}
	for (int i = 1; i <= n; i++) {
		if (l[i] > i)continue;
		q.push({ l[i],i,1 });
		q.push({ i + 1,i,-1 });
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		while (!q.empty() && q.top().p <= i) {
			add(q.top().v, q.top().op);
			q.pop();
		}
		if (r[i] < i)continue;
		ans += qry(r[i]) - qry(i - 1);
	}
	printf("%lld\n", ans);
	return 0;
}

 

F. 解方程

 

题意：有一个函数 f(i)f(i)，使得 ∑i∣nf(i)σp(ni)=σq(n)\sum_{i|n}f(i)\sigma_p(\frac{n}{i})=\sigma_q(n)，其中 σk(n)\sigma_k(n) 表示 nn 的因子的 kk 次方和。输出所有 f(i),1≤i≤nf(i),1\le i\le n 的异或和。

迪利克雷卷积+莫比乌斯反演

以下 “∗*” 表示迪利克雷卷积。

前置知识：σk=IDk∗1\sigma_k=ID_k*1，其中 IDk(n)ID_k(n) 表示 nkn^k。

μ∗1=ϵ\mu*1=\epsilon，其中 ϵ(n)\epsilon(n) 表示 [n==1][n==1]。

题中式子为

f∗σp=σq⇓f∗IDp∗1=IDq∗1f*\sigma_p=\sigma_q\\\Downarrow\\f*ID_p*1=ID_q*1\\

两边同时卷积 μ\mu 并化简

f∗IDp∗ϵ=IDq∗ϵf*ID_p*\epsilon = ID_q*\epsilon\\

对于左边，仅当 f∗IDpf*ID_p 对于 n 操作时 ϵ\epsilon 不为 0，对于右边，仅当 IDqID_q 对 n 操作时 ϵ\epsilon 不为 0.

所以

∑i∣nf(i)⋅(ni)p=nq⇓∑i∣nf(i)ip=nq−p\sum_{i|n}f(i)\cdot(\frac{n}{i})^p=n^q\\\Downarrow\\\sum_{i|n}\frac{f(i)}{i^p}=n^{q-p}\\

可以看到变为了莫比乌斯反演的标准形式，对其应用莫比乌斯反演，得到

f(n)np=∑i∣nμ(i)⋅(ni)q−p⇓f(n)nq=∑i∣nμ(i)iq−p\frac{f(n)}{n^p}=\sum_{i|n}\mu(i)\cdot(\frac{n}{i})^{q-p}\\\Downarrow\\\frac{f(n)}{n^q}=\sum_{i|n}\frac{\mu(i)}{i^{q-p}}\\

考虑欧拉筛筛出结果。

所以要先考虑一个质数的幂次 dkd^k 的 f(dk)f(d^k)。

f(dk)dkq=∑i∣dkμ(i)iq−p\frac{f(d^k)}{d^{kq}}=\sum_{i|d^k}\frac{\mu(i)}{i^{q-p}}\\

由于 μ(1)=1,μ(d)=−1\mu(1)=1,\mu(d)=-1，其它因子的 μ\mu 全为 0，所以直接求和

f(dk)dkq=1−dp−q\frac{f(d^k)}{d^{kq}}=1-d^{p-q}\\

令 g(n)=f(n)nqg(n)=\frac{f(n)}{n^q}，由于两个积性函数的迪利克雷卷积得到的仍是积性函数，所以 gg 也是积性函数，可以欧拉筛。

g(n)=∏d∣n⋀is_prime[d](1−dp−q)g(n)=\prod_{d|n\bigwedge is\_prime[d]}(1-d^{p-q})\\

最终有

f(n)=nq⋅g(n)f(n)=n^q\cdot g(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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e7 + 10;
const ll mod = 998244353;
int f[N];
int n, p, q;
ll Pow(ll a, ll b) {
	ll res = 1ll;
	while (b) {
		if (b & 1)res = res * a%mod;
		a = a * a%mod;
		b >>= 1;
	}
	return res;
}
int id1[N], id2[N];
int prime[N], cnt, d;
bool vis[N];
void sieve(int n) {
	cnt = 0; f[1] = 1; id1[1] = id2[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) {
			prime[cnt++] = i;
			id1[i] = Pow(i, q);
			if (p > q)id2[i] = Pow(i, p - q);
			else id2[i] = 1ll * Pow(i, p) * Pow(id1[i], mod - 2) % mod;
			f[i] = (1 - id2[i] + mod) % mod;
		}
		for (int j = 0; j < cnt && (d = i * prime[j]) <= n; j++) {
			vis[d] = 1;
			id1[d] = 1ll * id1[i] * id1[prime[j]] % mod;
			if (i%prime[j] == 0) {
				f[d] = f[i];
				break;
			}
			else {
				f[d] = 1ll * f[i] * f[prime[j]] % mod;
			}
		}
	}
}
int main() {
	scanf("%d%d%d", &n, &p, &q);
	sieve(n);
	ll ans = 0;
	for (int i = 1; i <= n; i++)ans ^= 1ll * f[i] * id1[i] % mod;
	printf("%lld\n", ans);
	return 0;
}