XJOI200727 题解

NTT优化, 容斥原理, 思维, 模拟赛

只订了 A B，题真好（nán）啊 ~

A

答案是 $\sum (ai + k - a[i] mod k)$

考虑 a[i] < k 的时候，这段长度就是 k

所以我们可以将 k 从小到大排序，对于每个 k 删掉 < k 的 a[i]，对于剩下的点做前缀和、二分，边界特殊处理

为什么这样复杂度是对的呢？每个 a[i] 被计算它的大小次，所以是 O(n + Qlogn) 的（瓶颈在于二分）

太妙了！

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
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int N = 5e6 + 10, M = 2e5 + 10;
typedef long long ll;
ll n, Q, tot;
ll cur[N], a[N], b[N], pos[N], pre[N], ans[M];
char s[N];
struct que { ll l, r, k, id; }q[M];

bool cmp(que a, que b) { return a.k < b.k; }

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    rep(i, 1, n) {
        if (s[i] == 'T') {
            pos[++tot] = i;
            a[tot] = i - 1 - pos[tot - 1];
            b[tot] = tot;
        }
        cur[i] = tot;
    }

    cin >> Q;
    rep(i, 1, Q) {
        scanf("%lld%lld%lld", &q[i].l, &q[i].r, &q[i].k);
        q[i].id = i;
    }
    sort(q + 1, q + Q + 1, cmp);
    rep(i, 1, Q) {
        ll l = q[i].l, r = q[i].r, k = q[i].k;
        if (k != q[i - 1].k) {
            int cnt = 0;
            rep(j, 1, tot)
                if (a[j] >= k) a[++cnt] = a[j], b[cnt] = b[j];
            tot = cnt;
            rep(j, 1, tot) pre[j] = pre[j - 1] + a[j] / k;
        }
        if (cur[l - 1] == cur[r]) {
            ans[q[i].id] = r - l + 1; continue;
        }
        int x = lower_bound(b + 1, b + tot + 1, cur[l - 1] + 2) - b;
        int y = upper_bound(b + 1, b + tot + 1, cur[r]) - b - 1;
        ans[q[i].id] = (r - pos[cur[r]]) + k * (cur[r] - cur[l - 1] + (pre[y] - pre[x - 1]) + (pos[cur[l - 1] + 1] - l) / k);
    }
    rep(i, 1, Q) printf("%lld\n", ans[i]);
    return 0;
}

B

容易列出 dp 柿子 $f[i, j] = \sum\limits_k f[i - 1, j - a_k]$，答案就是 $fl, i$

容易想到矩阵快速幂，但是复杂度太高会爆炸

从生成函数的视角出发，设 $g(x) = \sum\limits_i x^{a_i}$，则 $[j + a_k] f^i = \sum [j]f^{i - 1} \times [a_k] g$，这是循环卷积的形式。所以说我们平时写的 fft/ntt 其实就是忽视了 2^? 的循环卷积！本题 n 是 2^?，若不是，则需要做任意长度fft了。（我不会

卷积快速幂其实就是转化成点值形式，点对点直接做快速幂。

m 个限制可以分段做再乘起来，每做完一个限制就把下一个限制位置的方案数置为 0，复杂度是 O(mnlog^2n)

据说还能容斥？？？咕咕

code（分段做）：

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
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

typedef long long ll;
const int mod = 998244353, N = 66000 * 2, G = 3, G1 = (mod + 1) / G;
ll n, L, m, Q, lim = 1;
ll r[N], f[N], g[N];
struct limits { ll x, y; }li[20];

bool cmp(limits a, limits b) { return a.x < b.x; }

ll quick_pow(ll a, ll b) {
    ll ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
    } return ret;
}

void ntt(ll a[], int op) {
    rep(i, 0, lim - 1)
        if (i < r[i]) swap(a[i], a[r[i]]);
    for (int mid = 1; mid < lim; mid <<= 1) {
        ll W = quick_pow(op == 1 ? G : G1, (mod - 1) / (mid << 1));
        for (int j = 0; j < lim; j += (mid << 1)) {
            ll w = 1;
            for (int k = 0; k < mid; k++, w = w * W % mod) {
                ll x = a[j + k], y = w * a[j + k + mid] % mod;
                a[j + k] = (x + y) % mod, a[j + k + mid] = (x - y + mod) % mod;
            }
        }
    }
    if (op == -1) {
        ll inv = quick_pow(lim, mod - 2);
        rep(i, 0, lim - 1) a[i] = a[i] * inv % mod;
    }
}

int main() {
    cin >> n >> L >> m;
    rep(i, 1, m) scanf("%lld%lld", &li[i].x, &li[i].y);
    cin >> Q;
    rep(i, 1, Q) {
        int x; scanf("%d", &x); f[x]++;
    }
    
    li[++m] = (limits){L, 0};
    sort(li + 1, li + m + 1, cmp);

    int l = 0;
    while (lim < n) lim <<= 1, ++l;  // < n 哦，是循环卷积
    rep(i, 0, lim - 1) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    ntt(f, 1);

    g[0] = 1;
    rep(i, 1, m) {
        ntt(g, 1);
        rep(j, 0, n - 1) g[j] = g[j] * quick_pow(f[j], li[i].x - li[i - 1].x) % mod;  // 点值直接做快速幂
        ntt(g, -1);
        if (i < m) g[li[i].x] = 0;
    }
    printf("%lld\n", g[0]);
    return 0;
}

C

看了 Flying2018大佬博客 来订正了。。。

本题所有思考基于一个性质：对于 $gcd(a, b) = 1$，$l = a \times b$, $len(l) = lcm(len(a), len(b))$

所以只要考虑所有 = 质数的 m 就好了。

考虑 f(n) 怎么算，显然 $f(n) = x \times a^n + \sum\limits_{i < n} c \times a^i$

那么就是要求 $x \times a^n + \sum\limits_{i < n} c \times a^i \equiv x (mod m)$ 的最小 n

即 $\frac{a^n - 1}{a - 1} \equiv x(1 - a^n) (mod m)$

然后开始分讨：

  • a = 0：循环节为 1
  • a = 1：