20231108题解

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

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 条边的链是无意义的。我们只要讨论前两种就好了。注意对于第一条和第二条鱼特判。

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
#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)\)。

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

var

? pts

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

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
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}\)。

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
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\) 又是单调降的，所以肯定不优。

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

所以对峰值模拟退火。