20231108题解

发表于 2023-11-08 分类于信奥，题解阅读次数：

eattt

高妙结论题。考场最多就 20 pts。

如果 \(a_{i+1}\) 被 \(a_i\) 吃，我们就在 \(i\) 与 \(i+1\) 之间连一条边。容易发现，最终的局面一定是几段不交的链。

考虑统计每一条鱼的贡献。一条鱼吃到最后要么是 \(a_i\) 要么是 \(-a_i\)。我们尝试统计 \(a_i\) 和 \(-a_i\) 分别出现的次数。

对于 \(a_i\) 之前连续的边有几条进行分类讨论：

0 条，此时 \(a_i\) 压根就没有被吃。贡献为 \(a_i\prod_{i=n-k-2}^{n-2}i\)。
1 条，此时 \(a_i\) 被吃了一次。贡献为 \(-a_ik\prod_{i=n-k-1}^{n-2}i\)。乘 \(k\) 是因为 \(a_i\) 中被吃的那一次可以是任何一次。
2 条，此时有两种可能：\(a_{i-1}\) 先被吃，然后 \(a_i\) 再被吃；\(a_i\) 先被吃，然后 \(a_{i-1}\) 再被吃。贡献一正一负。显然 \(a_i\) 和 \(a_{i-1}\) 的地位相等，所以两种情况的出现次数也一定相同，总贡献就是 0。
\(k\) 条（\(k>2\)），容易发现 \(a_i\) 的正负与 \(a_{i-1}\) 的正负可能相同，也可能相反，但是两种可能仍然是次数相同。既然 \(a_{i-1}\) 贡献是 0，\(a_i\) 贡献也是 0。对 \(k\) 归纳即可。

所以大于 1 条边的链是无意义的。我们只要讨论前两种就好了。注意对于第一条和第二条鱼特判。

#include <bits/stdc++.h>
using namespace std;

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

const int maxn = 1e6 + 5;
const long long mod = 1e9 + 7;
int n, k, a[maxn];
long long p[maxn], ans;

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;
}

int main() {
    freopen("eattt.in", "r", stdin), freopen("eattt.out", "w", stdout);
    read(n); read(k);
    for (int i = 1; i <= n; i++) read(a[i]);
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = (p[i - 1] * i) % mod;
    }
    for (int i = 1; i <= n; i++) {
        if (i == 1) (ans += a[i] * p[n - 1] % mod * quick_pow(p[n - k - 1], mod - 2)) %= mod;
        else if (i == 2) {
            if (k < n - 1) (ans += a[i] * p[n - 2] % mod * quick_pow(p[n - k - 2], mod - 2)) %= mod;
            (ans += (mod - a[i]) * p[n - 2] % mod * quick_pow(p[n - k - 1], mod - 2) % mod * k) %= mod;
        } else {
            if (k < n - 1) {
                (ans += a[i] * p[n - 2] % mod * quick_pow(p[n - k - 2], mod - 2)) %= mod;
                (ans += (mod - a[i]) * p[n - 3] % mod * quick_pow(p[n - k - 2], mod - 2) % mod * k) %= mod;
            }
        }
    }
    printf("%lld\n", ans * quick_pow(p[n - 1] * quick_pow(p[n - k - 1], mod - 2) % mod, mod - 2) % mod);
    return 0;
}

gcd

形式化来说，我们要求 \(\sum_{i=l}^{r}{[\operatorname{gcd}(a_i, G)=1]}\)，支持区间修改。

后面那个东西很眼熟啊，考虑莫反：

\[ \begin{aligned} &\sum_{i=l}^{r}{[\operatorname{gcd}(a_i, G)=1]} \\ =&\sum_{i=l}^{r}{\sum_{d \mid \operatorname{gcd}(a_i, G)}{\mu(d)}} \\ =&\sum_{d \mid G} \mu(d) \sum_{i = l}^{r}{[d \mid a_i]} \end{aligned} \]

前面一个求和是 \(\mathcal{O}(\sqrt{G})\) 的。后面一段是区间为 \(d\) 的倍数的个数。（想一想 \(\mu\) 的定义，其实和容斥是一个道理）。所以我们要在一个可接受的复杂度内求出区间为 \(d\) 的倍数的个数，还要支持修改。

由于值域很小，容易想到对于值域内的每一个数都记录它的倍数在哪里出现过，空间复杂度 \(\mathcal{O}(W \sqrt{W})\)。如果用 vector 加二分实现，无法快速处理修改。考虑用平衡树维护。这样询问复杂度是 \(\mathcal{O}(\sqrt{G}\log n)\)，修改时要把 \(a_i\) 的所有因数对应的平衡树也修改，复杂度是 \(\mathcal{O}(\sqrt{a_i}\log n)\)。

这个东西好像单点修和无修的复杂度是相同的。

code

#include <bits/stdc++.h>
using namespace std;

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

const int maxn = 1e5 + 5;
int n, m, a[maxn], f[maxn];
bool np[maxn];
vector<int> primes;
mt19937 rd(time(NULL));
struct node; typedef node* pos;
struct node { int siz, val, key; pos ls, rs; node() { ls = rs = this; }}
buf[maxn * 50], *buf_pos = buf;
pos new_node(int val) { pos p = ++buf_pos; p -> ls = p -> rs = buf; p -> siz = 1, p -> key = rd(), p -> val = val; return p; }
void push_up(pos p) { p -> siz = p -> ls -> siz + p -> rs -> siz + 1; }
void split(pos p, int v, pos &pl, pos &pr) { return p == buf ? void(pl = pr = buf) : (p -> val <= v ? (pl = p, split(p -> rs, v, p -> rs, pr), push_up(p)) : (pr = p, split(p -> ls, v, pl, p -> ls), push_up(p))); }
pos merge(pos pl, pos pr) { return (pl == buf || pr == buf) ? (pl + (pr - buf)) : (pl -> key > pr -> key ? (pl -> rs = merge(pl -> rs, pr), push_up(pl), pl) : (pr -> ls = merge(pl, pr -> ls), push_up(pr), pr)); }
pos root[maxn], ls, rs, xs;

int main() {
    f[1] = 1; np[1] = true;
    for (int i = 2; i <= 1e5; i++) {
        if (!np[i]) {
            f[i] = -1;
            primes.emplace_back(i);
        }
        for (int j : primes) {
            if (i * j > 1e5) break;
            np[i * j] = true;
            f[i * j] = -f[i];
            if (i % j == 0) {
                f[i * j] = 0;
                break;
            }
        }
    }
    read(n);
    for (int i = 1; i <= 1e5; i++) root[i] = buf;
    for (int i = 1; i <= n; i++) {
        read(a[i]);
        for (int d = 1; d * d <= a[i]; d++) {
            if (a[i] % d == 0) {
                root[d] = merge(root[d], new_node(i));
                if (d * d != a[i]) root[a[i] / d] = merge(root[a[i] / d], new_node(i));
            }
        }
    }
    read(m);
    while (m--) {
        int op; read(op);
        if (op == 1) {
            int x, y; read(x); read(y);
            for (int d = 1; d * d <= a[x]; d++) {
                if (a[x] % d == 0) {
                    split(root[d], x - 1, ls, rs);
                    split(rs, x, xs, rs);
                    root[d] = merge(ls, rs);
                    if (d * d != a[x]) {
                        split(root[a[x] / d], x - 1, ls, rs);
                        split(rs, x, xs, rs);
                        root[a[x] / d] = merge(ls, rs);
                    }
                }
            }
            a[x] = y;
            for (int d = 1; d * d <= a[x]; d++) {
                if (a[x] % d == 0) {
                    split(root[d], x, ls, rs);
                    root[d] = merge(merge(ls, new_node(x)), rs);
                    if (d * d != a[x]) {
                        split(root[a[x] / d], x, ls, rs);
                        root[a[x] / d] = merge(merge(ls, new_node(x)), rs);
                    }
                }
            }
        } else {
            int l, r, x; read(l); read(r); read(x);
            int ans = 0;
            for (int d = 1; d * d <= x; d++) {
                if (x % d == 0) {
                    if (f[d] != 0) {
                        split(root[d], l - 1, ls, rs);
                        split(rs, r, xs, rs);
                        ans += f[d] * xs -> siz;
                        root[d] = merge(ls, merge(xs, rs));
                    }
                    if (d * d != x && f[x / d] != 0) {
                        split(root[x / d], l - 1, ls, rs);
                        split(rs, r, xs, rs);
                        ans += f[x / d] * xs -> siz;
                        root[x / d] = merge(ls, merge(xs, rs));
                    }
                }
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

var

? pts

模拟退火。每次随机一个位置，然后让这个位置随机改变一个值。卡时退火。期望得分 \(0 \sim 30\)。在 \(A\) 很大的时候基本没戏。

namespace SA {
    const __int128 I = 1;
    long long w[maxn];
    __int128 ans, nans;
    __int128 abs(__int128 x) {
        return x > 0 ? x : -x;
    }
    bool rb(double p) {
        return rand() < p * RAND_MAX;
    }
    void simulate_anneal(double start_temp, double end_temp, double delta_temp) {
        double t = start_temp;
        while (t > end_temp) {
            int id = rand() % n + 1;
            long long dw = ceil(t * (1 - 2.0 * rand() / RAND_MAX));
            if (dw == 0) dw = -1;
            long long tw0 = w[id - 1], tw1 = w[id], tw2 = w[id + 1];
            w[id] += dw;
            w[id] = max(0LL, w[id]);
            w[id] = min({w[id], a[id], a[id - 1]});
            __int128 tans = nans;
            if (id > 1) {
                w[id - 1] = min(a[id - 1] - w[id], a[id - 2] - w[id - 2]);
                tans -= I * tw0 * v[id - 1];
                tans += I * w[id - 1] * v[id - 1];
            }
            if (id < n) {
                w[id + 1] = min(a[id] - w[id], a[id + 1] - w[id + 2]);
                tans -= I * tw2 * v[id + 1];
                tans += I * w[id + 1] * v[id + 1];
            }
            tans -= I * tw1 * v[id];
            tans += I * w[id] * v[id];
            ans = max(ans, tans);
            if (tans > nans) nans = tans;
            else if (!rb(exp(-abs(tans - nans) / t))) w[id - 1] = tw0, w[id] = tw1, w[id + 1] = tw2;
            else nans = tans;
            t *= delta_temp;
        }
    }
    void solve() {
        // srand(19260817);
        for (int tid = 1; tid <= t; tid++) {
            read(n); read(m);
            long long maxa = 0;
            for (int i = 1; i < n; i++) {
                read(a[i]); maxa = max(a[i], maxa);
            }
            a[0] = a[n] = 0x3f3f3f3f3f3f3f3f;
            for (int i = 1; i <= m; i++) read(b[i]), b[i] += b[i - 1];
            int l = n - m + 1;
            for (int i = 1; i <= n; i++) v[i] = b[min(i, m)] - b[max(0, i - l)];
            w[1] = 0; nans = 0;
            for (int i = 2; i <= n; i++) {
                w[i] = min(a[i], a[i - 1] - w[i - 1]);
                nans += I * w[i] * v[i];
            }
            ans = nans;
            while (clock() * 1.0 / CLOCKS_PER_SEC < 0.95 / t * tid) {
                srand(clock());
                simulate_anneal(rand() % maxa + maxa, pow(0.1, rand() % 4 + 4), 0.9997 + 0.0001 * (1 -
                rand() * 2.0 / RAND_MAX));
            }
            write(ans);
        }
    }
}

30pts

考虑 \(\mathcal{O}(nA)\) DP。非常好想，用 \(f_{i, j}\) 表示第 \(i\) 个位置最多放 \(j\) 个糖的最大值，则 \(f_{i, j} \to f_{i+ 1, a_i-j}\)。

namespace brute_force {
    const int maxa = 5e3 + 5;
    __int128 f[maxa], ans;
    void solve() {
        for (int tid = 1; tid <= t; tid++) {
            read(n); read(m); long long ma = 0;
            for (int i = 1; i < n; i++) {
                read(a[i]); ma = max(ma, a[i]);
            } a[n] = 0x3f3f3f3f3f3f3f3f;
            for (int i = 1; i <= m; i++) read(b[i]), b[i] += b[i - 1];
            int l = n - m + 1;
            for (int i = 1; i <= n; i++) v[i] = b[min(i, m)] - b[max(0, i - l)];
            
            ans = 0;
            memset(f, 0, sizeof f);
            for (int i = 1; i <= a[1]; i++) f[i] = v[1];
            for (int i = 2; i <= n; i++) {
                reverse(f + 1, f + a[i - 1] + 1);
                for (int j = 1; j <= a[i - 1]; j++) f[0] += f[j];
                for (int j = 1; j <= a[i - 1]; j++) f[j] = v[i] - f[j];
                for (int j = 1; j <= a[i - 1]; j++) f[j] = max(f[j], __int128(0));
                memset(f + a[i - 1] + 1, 0, sizeof(f) - sizeof(__int128) * (a[i - 1] + 1));
            }
            for (int i = 0; i <= ma; i++) ans += f[i];
            write(ans);
        }
    }
}

80？pts

把 \(f_i\) 看成一个函数，则转移就是把 \(f_i\) 关于 \(x=a_i\) 对称，再整体加上一个一次函数，最后取前缀 \(\max\)。

可以维护差分情况，即区间翻转、区间取负号、区间加、区间对 0 取 \(\max\)。时间复杂度 \(\mathcal{O}(n \log^2 n)\)。

100 pts

可以归纳证明整个函数是一个凸包。据说可以 \(\mathcal{O}(1)\) 维护凸包。我写不出来。

100 pts

把每个位置有多少孩子记为 \(w_i\)。容易发现，\(w\) 是先上升再下降的。如果 \(w\) 的最高的地方对应的糖数确定，则往两边贪心就是最优的。证明：

考虑向右递减的情况。假设遇到了一个可以调整的位置，由于之前都是贪心，所以这个位置肯定 -1,则后面最多是连续 +1,-1,+1……由于第一个是负的，而 \(w\) 又是单调降的，所以肯定不优。

所以只要考虑峰值的糖数。不过我不会证单调性啥的，似乎总和关于峰值糖数是单峰的，但我不会证。

~~所以对峰值模拟退火。~~