20231116题解

发表于 分类于 ， 阅读次数：

又双叒叕打脸了。一场感冒很通人性地帮我赶走了期中考，于是我又去机房了。

mex

mex 这种东西好像比较典，建议大家区学习学习一些模板题，类似区间求 mex 之类的。

不过这个题跟上面说的没啥关系。定义 \(f_i\) 表示强制第一个数取 \(a_i\)，从 \(i\) 开始向后匹配，保证能匹配的最长长度。比如对于 \(a\) 数组 1 2 3 4 5 6 7 8 9 1，对应的 \(f\) 数组是 2 1 1 1 1 1 1 1 1 1。

这个东西暴力 \(\mathcal{O}(n^2)\) 转移就好了。关键是怎么构造。

我们来考虑第一位：我们肯定是希望构造出的长度越短越好，所以应该选 \(f\) 最小的数字。如果 \(f\) 相同，就再选最小的数字。之后是可以递归的。

细节看代码吧，讲不清楚。

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>
using namespace std;

const int maxn = 2e2 + 5;
int n;
char a[maxn];

namespace AC { //美好的希冀
    int b[15], c[15], dp[maxn];
    void solve() {
        if (![&]() { 
            for (int i = 1; i <= n; i++) if (a[i] == '0') return true;
            return false;
        }()) {
            printf("0\n");
            return;
        }
        for (int i = n; i >= 1; i--) {
            memset(b, 0, sizeof b);
            for (int j = i + 1; j <= n; j++) {
                b[a[j] - '0'] = max(b[a[j] - '0'], dp[j]);
            }
            dp[i] = 0x3f3f3f3f;
            for (int j = 0; j < 10; j++) dp[i] = min(dp[i], b[j] + 1);
        }
        int id = 0;
        while (true) {
            memset(b, 0, sizeof b); memset(c, 0x3f, sizeof c);
            for (int i = id + 1; i <= n; i++) {
                b[a[i] - '0'] = max(b[a[i] - '0'], dp[i]);
                c[a[i] - '0'] = min(c[a[i] - '0'], i);
            }
            int v = -1;
            for (int i = 0; i < 10; i++) {
                if (id == 0 && i == 0) continue;
                if (v == -1 || (b[i] < b[v])) v = i;
            }
            putchar('0' + v);
            if (!b[v]) {
                putchar('\n');
                break;
            }
            else id = c[v];
        }
    }
}

int main() {
    freopen("mex.in", "r", stdin);
    freopen("mex.out", "w", stdout);
    scanf("%d", &n);
    scanf("%s", a + 1);
    AC::solve();
    // test::work();

    return 0;
}

permutation

一开始毫无思路，先打一个暴力：

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
namespace brute_force {
    int a[maxn], cnt;
    bool check() {
        int sum = 0, tot = 0;
        for (int i = 1; i <= n; i++) {
            sum += a[i]; 
            if (i < n && sum == i * (i + 1) / 2) return false;
            for (int j = i + 1; j <= n; j++) {
                tot += (a[i] > a[j]);
            }
        }
        return tot == n - 1;
    }
    void solve() {
        for (int i = 1; i <= n; i++) a[i] = i;
        do {
            if (check()) {
                cnt++;
                for (int i = 1; i <= n; i++) {
                    //if (a[i] < 8) continue;
                    cerr << a[i] << " ";
                }
                cerr << endl;
                if (cnt == k) {
                    for (int i = 1; i <= n; i++) printf("%d%c", a[i], " \n"[i == n]);
                    break;
                }
            }
        } while (next_permutation(a + 1, a + n + 1));
    }
}

把 \(n=9\) 的所有合法序列都打出来看一看：

好像很乱啊。但是注意看 1：

很有规律！

这启发我们考虑每个数的位置。但如果你看看另一些数，比如 4：

右半段还是有规律的，但是左半段不容易看出。我们不妨换个视角：我们把 1、2、3 出现位置全部删掉，再看一看：

现在就有统一的规律了。修一修写出代码：

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

    int a[maxn];
    int get_pos(int x) {
        //共 1<<(n-2) 次
        //循环节长度为 1<<(n-x)
        //特别的，1没有潜伏期，n直接返回1
        if (x == n) return 1;
        if (x == 1) {
            if (__builtin_popcountll(k) > 1) return n - (64 - __builtin_clzll(k) + 1) + 1;
            else return n - (64 - __builtin_clzll(k)) + 1;
        }
        else {
            long long tk = (k - 1) % (1LL << (n - x)) + 1;
            if (tk <= (1LL << (n - x - 1))) return 1;
            else {
                tk -= (1LL << (n - x - 1));
                if (__builtin_popcountll(tk) > 1) return (n - x + 1) - (64 - __builtin_clzll(tk) + 1) + 1;
                else return (n - x + 1) - (64 - __builtin_clzll(tk)) + 1;
            }
        }
    }
    void solve() {
        for (int i = 1; i <= n; i++) {
            int p = get_pos(i);
            // cerr << p << endl;
            for (int j = 1; j <= n; j++) {
                if (!a[j]) {
                    p--;
                    if (!p) a[j] = i;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            printf("%d%c", a[i], " \n"[i == n]);
        }
    }
}

这样有 40 pts。

剩下的是讨厌的高精度。但我们发现实际上对 \(k\) 进行的都是位运算，所以考虑 bitset 高精度。

1
2
3
4
5
6
7
8
9
typedef bitset<maxn> bint;
bint operator + (bint a, bint b) {
    bool c = false; bint res;
    for (int i = 0; i < maxn; i++) {
        res[i] = (a[i] ^ b[i] ^ c);
        c = ((a[i] + b[i] + c) > 1);
    }
    return res;
}

只要实现加法能输入就好了。

AC 代码：

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
84
85
86
87
#include <bits/stdc++.h>
using namespace std;

template <class T>
void read(T &r) {
    r = 0; int ch = getchar(), f = 0;
    while (!isdigit(ch)) f ^= (ch == 45), ch = getchar();
    while (isdigit(ch)) (r *= 10) += ch - 48, ch = getchar();
    if (f) r = -r;
}

const int maxn = 5e3 + 5;

typedef bitset<maxn> bint;
bint operator + (bint a, bint b) {
    bool c = false; bint res;
    for (int i = 0; i < maxn; i++) {
        res[i] = (a[i] ^ b[i] ^ c);
        c = ((a[i] + b[i] + c) > 1);
    }
    return res;
}

void read(bint &r) {
    r.reset(); int ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) {
        r = (r << 1) + (r << 3) + bint(ch - 48);
        ch = getchar();
    }
}

long long n;
bint k;

namespace AC { //打表打出来的
    int a[maxn];
    int get_pos(int x) {
        //共 1<<(n-2) 次
        //循环节长度为 1<<(n-x)
        //特别的，1没有潜伏期，n直接返回1
        if (x == n) return 1;
        if (x == 1) {
            int p = 0;
            for (int i = 0; i < maxn; i++) if (k[i]) p = i + 1;
            if (k.count() > 1) return n - (p + 1) + 1;
            else return n - p + 1;
        }
        else {
            bint tk = k;
            for (int i = n - x; i < maxn; i++) tk.reset(i);
            if (!tk.count()) return 2;
            else if ((!tk[(n - x - 1)]) || tk.count() == 1) return 1;
            else {
                tk.reset(n - x - 1);
                int p = 0;
                for (int i = 0; i < maxn; i++) if (tk[i]) p = i + 1;
                if (tk.count() > 1) return (n - x + 1) - (p + 1) + 1;
                else return (n - x + 1) - p + 1;
            }
        }
    }
    void solve() {
        for (int i = 1; i <= n; i++) {
            int p = get_pos(i);
            // cerr << p << endl;
            for (int j = 1; j <= n; j++) {
                if (!a[j]) {
                    p--;
                    if (!p) a[j] = i;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            printf("%d%c", a[i], " \n"[i == n]);
        }
    }
}

int main() {
    freopen("permutation.in", "r", stdin);
    freopen("permutation.out", "w", stdout);
    read(n); read(k);
    // brute_force::solve();
    AC::solve();
    return 0;
}

lovelorn

lovelorn

威廉怎么会失恋呢？

容易发现，可以把一个数拆成连续的它的本质不同的质因数（比如 30 拆成 2、3、5）。这样一来，询问就变成了区间去重，即所有出现过的数的乘积。

这个东西基本等价于HH的项链。用离线树状数组。右端点从小到大排序之后，每一个数肯定是由最靠右的那一个来提供贡献。用树状数组维护贡献即可。

另外注意质因数分解：用欧拉筛筛质数的时候，我们其实会得到每个数的最小质因子，用这个东西来分解最快。

细节看代码。

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>
using namespace std;

char st;

#define FILE_IO
namespace io {...};
using namespace io;

const int maxn = 1e6 + 5, maxv = 1e7 + 5;
const long long mod = 998244353;
int n, a[maxn], t;

long long quick_pow(long long x, long long p) {
    long long res = 1; while (p) {
        if (p & 1LL) (res *= x) %= mod;
        (x *= x) %= mod, p >>= 1;
    } return res;
}

namespace HH {
    struct node {
        int l, r, id;
    } q[maxn];
    int l[maxn], r[maxn];
    int b[maxn * 10];
    int from[maxv], vis[maxv];
    long long inv[maxv], ans[maxn], c[maxn * 10];
    bitset<maxv> np;
    vector<int> primes;
    void init() {
        np[1] = true;
        for (int i = 2; i <= 1e7; i++) {
            if (!np[i]) {
                primes.emplace_back(i);
                from[i] = i;
            }
            for (int j : primes) {
                if (i * j > 1e7) break;
                np[i * j] = true;
                from[i * j] = j;
                if (i % j == 0) break;
            }
        }
        int bcnt = 0;
        for (int i = 1; i <= n; i++) {
            int v = a[i]; l[i] = 0x3f3f3f3f;
            if (v == 1) l[i] = r[i] = bcnt;
            while (v > 1) {
                int tmp = from[v];
                while (v % tmp == 0) v /= tmp;
                b[++bcnt] = tmp;
                l[i] = min(l[i], bcnt);
                r[i] = max(r[i], bcnt);
            }
        }
        n = bcnt;
        for (int p : primes) inv[p] = quick_pow(p, mod - 2);
        for (int i = 1; i <= n; i++) c[i] = 1;
    }
    void update(int pos, long long x) {
        while (pos <= n) {
            (c[pos] *= x) %= mod;
            pos += (pos & -pos);
        }
    }
    long long ask(int pos) {
        long long res = 1; while (pos) {
            (res *= c[pos]) %= mod;
            pos -= (pos & -pos);
        } return res;
    }
    void solve() {
        init();
        for (int i = 1; i <= t; i++) {
            read(q[i].l), read(q[i].r), q[i].id = i;
            q[i].l = l[q[i].l], q[i].r = r[q[i].r];
        }
        sort(q + 1, q + t + 1, [&](node &a, node &b) { return a.r < b.r; });
        int j = 0;
        for (int i = 1; i <= n; i++) {
            if (vis[b[i]]) update(vis[b[i]], inv[b[i]]);
            update(vis[b[i]] = i, b[i]);
            while (q[j + 1].r == i) {
                j++;
                ans[q[j].id] = ask(q[j].r) * quick_pow(ask(q[j].l - 1), mod - 2) % mod;
            }
        }
        for (int i = 1; i <= t; i++) write(ans[i]);
    }
}

char ed;

int main() {
    freopen("lovelorn.in", "r", stdin);
    freopen("lovelorn.out", "w", stdout);
    // cerr << (&ed - &st) / 1024.0 / 1024.0 << endl;
    // auto t1 = clock();
    read(n);
    for (int i = 1; i <= n; i++) {
        read(a[i]);
    }
    read(t);
    HH::solve();
    // cerr << clock() - t1 << endl;
    return 0;
}