「LibreOJ NOI Round 2」部分题目【题解】

题目列表

  • D1T1. 单枪匹马
  • D1T2. 黄金矿工
  • D1T3. 不等关系
  • D2T1. 签到游戏
  • D2T2. 简单算术
  • D2T3. 小球进洞

简要题解

D1T1. 单枪匹马

题目大意:给定一个序列 {an}\{a_n\}。有 mm 次操作,操作分为两类:

  • 1 x1\ x:在序列末尾添加元素 xx
  • 2 l r2\ l\ r:将 f(al,al+1,,ar)f(a_l, a_{l + 1}, \cdots, a_r) 化为最简分数 xy\small \dfrac{x}{y},输出 x,yx, y

其中 f(x)=x,f(x) = x, f(a0,a1,,an)=a0+1f(a1,a2,,an)f(a_0, a_1, \cdots, a_n) = a_0 + \small \dfrac{1}{f(a_1, a_2, \cdots, a_n)}

保证 n,m5×105n, m \leqslant 5 \times 10^5,强制在线。

思路分析:线段树上维护线性变换。时间复杂度为 O(n+mlogn)O(n + m \log 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
#include <bits/stdc++.h>
#define mid (l + r >> 1)
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;

const int maxn = 1000010, P = 998244353;
int n, m, type, cur, a[maxn];
struct node { int p1, p2, x1, x2; } t[maxn << 2];

node merge(int l, int m, int r, node x, node y) {
if (r > cur) return x; node z;
int t1 = (1LL * x.p1 * a[m] + x.x1) % P;
int t2 = (1LL * x.p2 * a[m] + x.x2) % P;
z.p1 = (1LL * t1 * y.p1 + 1LL * x.p1 * y.p2) % P;
z.x1 = (1LL * t1 * y.x1 + 1LL * x.p1 * y.x2) % P;
z.p2 = (1LL * t2 * y.p1 + 1LL * x.p2 * y.p2) % P;
z.x2 = (1LL * t2 * y.x1 + 1LL * x.p2 * y.x2) % P;
return z;
}

void build(int k, int l, int r) {
if (l == r) { t[k].p1 = t[k].x2 = 1; return; }
build(ls, l, mid), build(rs, mid + 1, r);
t[k] = merge(l, mid, r, t[ls], t[rs]);
}

void upd(int k, int l, int r, int p) {
if (l == r) return;
if (mid >= p) upd(ls, l, mid, p);
else upd(rs, mid + 1, r, p);
t[k] = merge(l, mid, r, t[ls], t[rs]);
}

node F(int k, int l, int r, int ql, int qr) {
if (l >= ql && r <= qr) return t[k];
if (mid >= qr) return F(ls, l, mid, ql, qr);
if (mid < ql) return F(rs, mid + 1, r, ql, qr);
return merge(max(l, ql), mid, min(r, qr),
F(ls, l, mid, ql, qr), F(rs, mid + 1, r, ql, qr));
}

int main() {
scanf("%d %d %d", &n, &m, &type);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
cur = n, build(1, 1, n + m);
for (int i = 1, lst = 0, op, x, y; i <= m; i++) {
scanf("%d %d", &op, &x), x ^= type * lst;
if (op == 1) {
a[++cur] = x, upd(1, 1, n + m, cur);
} else {
scanf("%d", &y), y ^= type * lst;
node ans = F(1, 1, n + m, x, y);
int fx = (1LL * ans.p1 * a[y] + ans.x1) % P;
int fy = (1LL * ans.p2 * a[y] + ans.x2) % P;
printf("%d %d\n", fx, fy), lst = fx ^ fy;
}
}
return 0;
}

D1T3. 不等关系

题目大意:给出仅包含 <> 的字符串 SS (S=n)(\lvert S \rvert = n),求「使得 pi<pi+1p_i < p_{i + 1} 当且仅当 SiS_i< 的排列 p1,p2,,pn+1p_1, p_2, \cdots, p_{n + 1}」的数量模 998 244 353998\ 244\ 353 的值。保证 n105n \leqslant 10^5

思路分析:考虑固定所有 <,容斥 >。设 f(i)f(i) 表示长度为 ii 的前缀的合法排列数除以 i!i!cnti\text{cnt}_i 表示 S[1:i]S[1: i]> 的数量,具体地 ((初值为 f(0)=1)f(0) = 1)

f(i)=j=0i1[Sj<](1)cnti1cntjf(j)(ij)!f(i) = \sum_{j = 0}^{i - 1} [S_j \neq <] (-1)^{\text{cnt}_{i - 1} - \text{cnt}_j} \frac{f(j)}{(i - j)!}

DP 式可以变成卷积形式,分治 NTT。时间复杂度为 O(nlog2n)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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 262144, P = 998244353;
int n, f[maxn], g[maxn], cnt[maxn], fact[maxn], inv[maxn];
int l, lim, a[maxn], b[maxn], r[maxn];
char s[maxn];

int qp(int x, int y) {
int z = 1;
for (; y; y >>= 1, x = 1LL * x * x % P) {
if (y & 1) z = 1LL * z * x % P;
}
return z;
}

void init(int len) {
for (l = 0, lim = 1; lim <= len; lim <<= 1) l++;
for (int i = 0; i < lim; i++) {
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
}
}

void ntt(int *c, int tp) {
for (int i = 0; i < lim; i++) {
if (i < r[i]) swap(c[i], c[r[i]]);
}
for (int i = 1; i < lim; i <<= 1) {
int x = qp(3, (P - 1) / (i << 1));
for (int j = 0; j < lim; j += i << 1) {
for (int k = 0, y = 1; k < i; k++, y = 1LL * y * x % P) {
int p = c[j + k], q = 1LL * y * c[i + j + k] % P;
c[j + k] = (p + q) % P, c[i + j + k] = (p - q) % P;
}
}
}
if (tp == -1) {
reverse(c + 1, c + lim);
for (int i = 0, t = qp(lim, P - 2); i < lim; i++) {
c[i] = 1LL * c[i] * t % P;
}
}
}

void solve(int l, int r) {
if (l == r) {
if (l) f[l] = 1LL * (cnt[l - 1] & 1 ? -1 : 1) * f[l] % P;
if (s[l] == '>') g[l] = 1LL * (cnt[l] & 1 ? -1 : 1) * f[l] % P; return;
}
int mid = (l + r) >> 1;
solve(l, mid);
int len1 = mid - l + 1, len2 = r - l;
init(r - l + 1);
for (int i = 0; i < lim; i++) a[i] = i < len1 ? g[i + l] : 0;
for (int i = 0; i < lim; i++) b[i] = i < len2 ? inv[i + 1] : 0;
ntt(a, 1), ntt(b, 1);
for (int i = 0; i < lim; i++) a[i] = 1LL * a[i] * b[i] % P;
ntt(a, -1);
for (int i = mid + 1; i <= r; i++) (f[i] += a[i - l - 1]) %= P;
solve(mid + 1, r);
}

int main() {
scanf("%s", s + 1), n = strlen(s + 1) + 1;
fact[0] = inv[0] = f[0] = g[0] = 1;
for (int i = 1; i <= n; i++) {
cnt[i] = cnt[i - 1] + (s[i] == '>');
inv[i] = qp(fact[i] = 1LL * fact[i - 1] * i % P, P - 2);
}
solve(0, n), printf("%d\n", (1LL * f[n] * fact[n] % P + P) % P);
return 0;
}

D2T1. 签到游戏

题目大意:有一个序列 {Bn}\{B_n\}。有 qq 个操作,每次给出 p,vp, v,将 BpB_p 改为 vv,并回答:

有一个未知的序列 {An}\{A_n\}1lrn\forall 1 \leqslant l \leqslant r \leqslant n,可花费 gcdi=lrBi\gcd_{i = l}^r B_i 的代价求出 i=lrAi\sum_{i = l}^r A_i。目标是求出每个 AiA_i 的具体数值,输出达到目标的最小代价。

保证 n,q105,n, q \leqslant 10^5, Bi109B_i \leqslant 10^9

思路分析:先给出一个结论及简要证明:

存在转折点 pp 使得最优方案构成如下:

  • [1,i][1, i] (pin)(p \leqslant i \leqslant n)

  • [j,n][j, n] (1<jp)(1 < j \leqslant p)

显然每个点 ii 都会选择 [1,i][1, i][i,n][i, n] 中的较优者。由于前缀 gcd\gcd 由前往后单调递减,后缀 gcd\gcd 由前往后单调递增,所以一定存在点 pp

gcd\gcd 的变化次数是 O(logBi)O(\log B_i) 的,所有操作都可以在线段树上二分完成。

时间复杂度为 O(qlog2n)O(q \log^2 n)O(qlog3n)O(q \log^3 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
#include <bits/stdc++.h>
#define mid (l + r >> 1)
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;

typedef long long ll;
const int maxn = 100010;
int n, q, b[maxn], t[maxn << 2];

void build(int k, int l, int r) {
if (l == r) { scanf("%d", &t[k]); return; }
build(ls, l, mid), build(rs, mid + 1, r);
t[k] = __gcd(t[ls], t[rs]);
}

void upd(int k, int l, int r, int p, int v) {
if (l == r) { t[k] = v; return; }
if (mid >= p) upd(ls, l, mid, p, v);
else upd(rs, mid + 1, r, p, v);
t[k] = __gcd(t[ls], t[rs]);
}

int find(int k, int l, int r, int x, int y) {
if (l == r) return l;
int a = __gcd(x, t[ls]), b = __gcd(y, t[rs]);
if (a <= b) return find(ls, l, mid, x, b);
return find(rs, mid + 1, r, a, y);
}

ll pre(int k, int l, int r, int p, int v) {
if (l == r) return __gcd(v, t[k]);
int g = __gcd(v, t[ls]);
if (mid < p) return pre(rs, mid + 1, r, p, g);
ll a = pre(ls, l, mid, p, v);
if (!(t[rs] % g)) return 1LL * (r - mid) * g + a;
return pre(rs, mid + 1, r, p, g) + a;
}

ll suf(int k, int l, int r, int p, int v) {
if (l == r) return __gcd(v, t[k]);
int g = __gcd(v, t[rs]);
if (mid >= p) return suf(ls, l, mid, p, g);
ll a = suf(rs, mid + 1, r, p, v);
if (!(t[ls] % g)) return 1LL * (mid - l + 1) * g + a;
return suf(ls, l, mid, p, g) + a;
}

int main() {
scanf("%d %d", &n, &q), build(1, 1, n);
for (int i = 1, p, v; i <= q; i++) {
scanf("%d %d", &p, &v);
upd(1, 1, n, p, v), p = find(1, 1, n, 0, 0);
printf("%lld\n", pre(1, 1, n, p, 0) + suf(1, 1, n, p, 0) - t[1]);
}
return 0;
}

D2T2. 简单算术

题目大意:给定一个 nn 次多项式 P(x)P(x) 和质数 pp。有 TT 个询问,每次给定 m,km, k,求 [xk]P(x)m[x^k] P(x)^mpp 的值。保证 n,p50,n, p \leqslant 50, m,k1018,m, k \leqslant 10^{18}, T103T \leqslant 10^3

思路分析:设 F(m,k)F(m, k) 表示询问 m,km, k 的答案。若 pmp \mid m

F(m,k)={F(m/p,k/p)(pk)0(pk)F(m, k) = \begin{cases} F(m / p, k / p) & (p \mid k) \\ 0 & (p \nmid k) \end{cases}

否则,枚举 P(x)m mod pP(x)^{m \text{ mod } p} 的项,递归至若干个 F(m/p,)F(\lfloor m / p \rfloor, *)。需要预处理出 P(x)P(x)0(p1)0 \sim (p - 1) 次幂。暴力递归并记忆化即可,注意不要访问 pkp \nmid k 的无用状态。

时间复杂度为 Ω(n2p2+Tn2logpm)\Omega \big( n^2 p^2 + T n^2 \log_p m \big)

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
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;

typedef long long ll;
const int maxn = 55;
int n, P, T, a[maxn], b[maxn][maxn * maxn], len[maxn];
unordered_map<ll, int> mp;

ll F(ll m, ll k) {
if (!m) return !k;
if (mp.count(m * 19260817 + k)) return mp[m * 19260817 + k];
int ans = 0;
for (int i = k % P; i < len[m % P] && i <= k; i += P) {
if (b[m % P][i]) {
ans += F(m / P, (k - i) / P) * b[m % P][i];
}
}
return mp[m * 19260817 + k] = ans % P;
}

int main() {
scanf("%d %d", &n, &P);
for (int i = 0; i <= n; i++) {
scanf("%d", &a[i]);
}
b[0][0] = len[0] = 1;
for (int i = 1; i < P; i++) {
len[i] = len[i - 1] + n + 1;
for (int j = 0; j < len[i - 1]; j++) {
for (int k = 0; k <= n; k++) {
b[i][j + k] = (b[i][j + k] + b[i - 1][j] * a[k]) % P;
}
}
}
scanf("%d", &T);
while (T--) {
ll m, k;
scanf("%lld %lld", &m, &k);
printf("%lld\n", F(m, k));
}
return 0;
}