本场摘要

传送门：

这场总体难度较小，没有很难的题目。但是会在刁钻的地方恶心人，也许是出题的印度老哥故意设计的。。。总之题目出得非常奇怪，不过作为复健场来说也还算有练习的价值。

总体做下来体验有点差——特别是最后的F题。幸好只是拿来训练，不然参赛的话可能会一直WA。

D. Good Trip

题目大意：

在 $n$ 个元素中等可能地选取两个元素，选完后放回，等可能地选 $m$ 轮。每对元素可能是朋友或不是朋友，如果是朋友则对应的“友好值”为一个整数。每当一对元素被选中后，如果这对元素是“朋友”，则会将该友好值加到 $sum$ 中，并且其“友好值”会 $+1$ 。问最终 $sum$ 期望多大。

题解：

将 $sum$ 分成两部分，即「基础部分」和「增加的部分」。

「基础部分」是很显然的：

$k * \frac{\sum_{i=1}^m f_i}{C_n^2}$

「增加部分」稍微有些棘手。可以注意到，如果只考虑增加值的话，每对朋友都是等价的，所以只要算出一对朋友的贡献，最后乘以朋友对数就行了。
而在增加值中，一对朋友的贡献仅与其被抽到的次数有关，对于每一对朋友，遍历其被抽到1…k次时产生的贡献然后加起来即可：

$m * \sum_{i=1}^k C_k^i * \frac{i *(i-1)}{2} *\left(\frac{1}{C_n^2}\right)^i *\left(1-\frac{1}{C_n^2}\right)^{k-i}$

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const ll mod = 1e9 + 7;
const int maxn = 2e5 + 5;
const double eps = 1e-10;
ll factorial[maxn];
ll n, m, k;
ll friendshipSum, N, K, invN;

ll quikPow(ll x, ll y) {
    ll res = 1;
    while (y) {
        if (y & 1)
            res *= x, res %= mod;
        x *= x, x %= mod;
        y >>= 1;
    }
    return res;
}

ll inv(ll x) {
    return quikPow(x, mod - 2);
}

ll C(int all, int select) {
    return factorial[all] * inv(factorial[select]) % mod *
           inv(factorial[all - select]) % mod;
}

void prepareArrays() {
    factorial[0] = 1;
    for (int i = 1; i < maxn; ++i) {
        factorial[i] = factorial[i - 1] * i % mod;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    prepareArrays();

    int T = 1;
    cin >> T;
    while (T--) {
        cin >> n >> m >> k;
        N = n * (n - 1) / 2 % mod;
        K = k * (k - 1) / 2 % mod;
        invN = inv(N);
        friendshipSum = 0;
        for (int i = 1; i <= m; ++i) {
            int a, b, f;
            cin >> a >> b >> f;
            friendshipSum += f;
            friendshipSum %= mod;
        }
        ll first = friendshipSum * invN % mod * k % mod;
        ll second = 0;

        for (int i = 1; i <= k; ++i) {
            second += C(k, i) * quikPow(invN, i) % mod *
                      quikPow(1 - invN + mod, k - i) % mod *
                      (1ll * i * (i - 1) / 2 % mod) % mod;
            second %= mod;
        }
        second = second * m % mod;
        cout << (first + second) % mod << '\n';
    }

    return 0;
}

E. Space Harbour

题目大意：

在数轴上有 1…n 总共 $n$ 个点，每个点上都有一艘飞船。在数轴中一些harbour，分散在数轴的 $m$ 个位置上，每个harbour有一个对应的value。一个飞船的弹射起飞的花销是其「左边最近的harbour的value」乘以「右侧最近harbour与当前飞船的距离」。

有两种操作，一种操作是在数轴中一个地方增加一个harbour；另一种操作是查询一段区间内所有飞船起飞花销的总和。

题解：

一眼线段树，带加法和乘法两种操作，然后记得带上懒标记即可。虽然思路十分清晰，但是写起来还是蛮麻烦的，个人觉得出题人的方法写起来更简单，不过他的代码风格相当难绷。。。

注意不要爆int32。其他的细节看代码实现和注释即可。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#define all(x) x.begin(), x.end()
typedef int64_t ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const int maxn = 3e5 + 5;
int n, m, q;
struct Harbour {
    int position, value;
    Harbour() {
        position = 0;
        value = 0;
    }
    Harbour(int position, int value) {
        this->position = position;
        this->value = value;
    }
    bool isEmpty() { return this->position == 0; }
    void destroy() { position = value = 0; }
} harbours[maxn];
bool operator<(const Harbour& lhs, const Harbour& rhs) {
    return lhs.position < rhs.position;
}
std::set<Harbour> harbourSet;
struct Tree {
    int left, right;
    ll sum, coast;
    ll lazyDelta, lazyValue;
    int middle() { return (left + right) / 2; }
    // 只有子树内所有节点的右侧harbour相同才可以调该方法
    void updateCoast() { coast = sum * lazyValue; }
    void replaceValue(int newValue) {
        lazyValue = newValue;
        updateCoast();
    }
    void subtractSum(int dec) {
        // warning：wa2 爆int
        sum -= 1ll * (right - left + 1) * dec;
        lazyDelta += dec;
        updateCoast();
    }
} tree[maxn << 2];

void pushUp(int root) {
    tree[root].coast = tree[root << 1].coast + tree[root << 1 | 1].coast;
    tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum;
    // 只有两个子节点的lazyValue相同时，root的lazyValue才有意义
    tree[root].lazyValue =
        tree[root << 1].lazyValue == tree[root << 1 | 1].lazyValue
            ? tree[root << 1].lazyValue
            : 0;
}
void pushDown(int root) {
    if (tree[root].lazyDelta) {
        tree[root << 1].subtractSum(tree[root].lazyDelta);
        tree[root << 1 | 1].subtractSum(tree[root].lazyDelta);
        tree[root].lazyDelta = 0;
    }
    if (tree[root].lazyValue) {
        tree[root << 1].replaceValue(tree[root].lazyValue);
        tree[root << 1 | 1].replaceValue(tree[root].lazyValue);
    }
}
int getLeftValue(int position) {
    if (position == 1)
        return 0;
    auto it = harbourSet.lower_bound(Harbour(position, 0));
    --it;
    return it->value;
}
int getRightDistance(int position) {
    auto it = harbourSet.lower_bound(Harbour(position, 0));
    return it->position - position;
}
void build(int root, int left, int right) {
    tree[root].left = left;
    tree[root].right = right;
    if (left == right) {
        tree[root].lazyValue = getLeftValue(left);
        tree[root].sum = getRightDistance(left);
        tree[root].updateCoast();
        return;
    }
    int middle = (left + right) / 2;
    build(root << 1, left, middle);
    build(root << 1 | 1, middle + 1, right);
    pushUp(root);
}
void updateSum(int root,
               int left,
               int right,
               int queryLeft,
               int queryRight,
               int delta) {
    int middle = (left + right) / 2;
    if (left == queryLeft && right == queryRight) {
        tree[root].subtractSum(delta);
        tree[root].updateCoast();
        return;
    }
    pushDown(root);
    if (queryLeft <= middle)
        updateSum(root << 1, left, middle, queryLeft,
                  std::min(middle, queryRight), delta);
    if (queryRight > middle)
        updateSum(root << 1 | 1, middle + 1, right,
                  std::max(middle + 1, queryLeft), queryRight, delta);
    pushUp(root);
}
void updateValue(int root,
                 int left,
                 int right,
                 int queryLeft,
                 int queryRight,
                 int newValue) {
    int middle = (left + right) / 2;
    if (left == queryLeft && right == queryRight) {
        tree[root].replaceValue(newValue);
        tree[root].updateCoast();
        return;
    }
    pushDown(root);
    if (queryLeft <= middle)
        updateValue(root << 1, left, middle, queryLeft,
                    std::min(middle, queryRight), newValue);
    if (queryRight > middle)
        updateValue(root << 1 | 1, middle + 1, right,
                    std::max(middle + 1, queryLeft), queryRight, newValue);
    pushUp(root);
}

// warning: int -> ll
ll query(int root, int left, int right, int queryLeft, int queryRight) {
    int middle = (left + right) / 2;
    if (left == queryLeft && right == queryRight)
        return tree[root].coast;
    pushDown(root);
    ll result = 0;
    if (queryLeft <= middle)
        result += query(root << 1, left, middle, queryLeft,
                        std::min(middle, queryRight));
    if (queryRight > middle)
        result += query(root << 1 | 1, middle + 1, right,
                        std::max(middle + 1, queryLeft), queryRight);
    return result;
}
void addHarbour(Harbour newHarbour) {
    auto frontHarbour = harbourSet.lower_bound(newHarbour);
    auto nextHarbour = frontHarbour;
    --frontHarbour;
    int left = frontHarbour->position + 1, right = newHarbour.position;
    if (left <= right)
        updateSum(1, 1, n, left, right, nextHarbour->position - right);
    left = newHarbour.position + 1, right = nextHarbour->position;
    if (left <= right)
        updateValue(1, 1, n, left, right, newHarbour.value);
    harbourSet.insert(newHarbour);
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T = 1;
    // std::cin >> T;
    while (T--) {
        std::cin >> n >> m >> q;
        for (int i = 1; i <= m; ++i) {
            std::cin >> harbours[i].position;
        }
        for (int i = 1; i <= m; ++i) {
            std::cin >> harbours[i].value;
        }
        for (int i = 1; i <= m; ++i) {
            harbourSet.insert(harbours[i]);
        }
        build(1, 1, n);
        while (q--) {
            int t, x, v;
            std::cin >> t >> x >> v;
            if (t == 1) {
                addHarbour(Harbour(x, v));
            } else {
                std::cout << query(1, 1, n, x, v) << '\n';
            }
        }
    }

    return 0;
}
/*
8 3 4
1 3 8
3 24 10
2 2 5
1 5 15
2 5 5
2 7 8
*/

F. Fractal Origami

题目大意：

有一张边长为 $1$ 的正方形折纸，将对其进行 $N$ 次操作。

每次操作为：首先选择每条边的中点，并顺次将其连起来，得到四条边。分别沿着这四条边，将正方形的每个角折起来。每经过一次操作后，会得到一个新的正方形，其边长为原来的 $\frac{1}{\sqrt{2}}$

操作完后，重新展开这张折纸，折痕中有凸起来（“峰”）的也有凹下去（“谷”）的。

求“峰”的长度除以“谷”的长度的结果中， $\sqrt{2}$ 的系数。

题解：

假设一张纸朝上的是正面，朝下的是反面。显然，纸张朝上的时候对折起来，折痕是凹的；纸张朝下时对折起来，折痕的凸的。

在第一次对折的时候，可以注意到底部依然是一个正面朝上的边长为 $\frac{1}{\sqrt{2}}$ 的纸，上方的四个角我们可以把它看作一个整体，形成了一个边长同样为 $\frac{1}{\sqrt{2}}$ 的正方形。

第二次对折后，整张纸变成了四层。下面的两层是一反一正的，上面的两层同样是一反一正。

第三次对折后，整张纸变成了八层。下面的四层是一反一正一反一正的，上面的四层同样是一反一正一反一正。

etc…

用式子总结一下，设“峰”的总长度为 $Sum_{peak}$ ，

$\begin{aligned} \operatorname{Sum}_{peak} & =4 * \sum_{i=2}^n \frac{1}{(\sqrt{2})^2} * 2^{n-2} \\ & =4 * \sum_{i=2}^n(\sqrt{2})^{n-4} \\ & =\frac{1-(\sqrt{2})^{n-1}}{1-\sqrt{2}} * 2 \end{aligned}$

设“谷”的总长度为 $Sum_{valley}$ ，则：

$\begin{aligned} \operatorname{Sum}_{valley} & =4 *\left(\sum_{i=2}^n \frac{1}{(\sqrt{2})^n} * 2^{n-2}+\frac{1}{\sqrt{2}}\right) \\ & =4 *\left[\sum_{i=2}^n(\sqrt{2})^{n-4}+\frac{1}{\sqrt{2}}\right] \\ & =\frac{1-(\sqrt{2})^{n-1}}{1-\sqrt{2}} * 2+2 \sqrt{2} \end{aligned}$

由于直接算“峰”除以”谷“有点难算——因为”谷“包含了更多的项，于是我们先用”谷“除以”峰“，得到

$\frac{\sqrt{2}-1-(\sqrt{2})^{n-1}}{1-(\sqrt{2})^{n-1}}$

分母有理化，得到

$\frac{\sqrt{2}+(\sqrt{2})^n-1-(\sqrt{2})^{n+1}-2^{n-1}}{1-2^{n-1}}$

这个式子可以写成如下形式

$A+B \sqrt{2}$

这个式子显然是我们期望式子的倒数，即

$\frac{1}{A+B \sqrt{2}}=\frac{A-B \sqrt{2}}{A^2-2 B^2}$

所以我们需要的 $\sqrt{2}$ 的系数即为

$\frac{-B}{A^2-2 B^2}$

这道题目还有一个极其恶心的地方，就是其中的一个计算步骤中出现了 $\frac{1}{2^{n-1}-1}$ ，如果对 $2^{n-1}-1$ 求逆元的话，由于模数是 $999999893$ ，根据费马小定理，这个式子会在 $n = 999999893$ 的时候变成 $0$ ，导致结果出错。所以得对这种情况特判断，换一下计算方式。不得不说,如果在比赛的途中遇到这个问题，真的很让人心态爆炸。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#define all(x) x.begin(), x.end()
typedef int64_t ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const ll mod = 999999893;
const int maxn = 2e5 + 5;
const double eps = 1e-10;
int N;
ll quickPow(ll x, ll y) {
    ll res = 1;
    x = (x % mod + mod) % mod;
    while (y) {
        if (y & 1)
            res *= x, res %= mod;
        x *= x, x %= mod;
        y /= 2;
    }
    return res;
}
ll inv(ll x) {
    return quickPow(x, mod - 2);
}
int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T = 1;
    std::cin >> T;
    while (T--) {
        std::cin >> N;
        ll bottom = inv((1 - quickPow(2, N - 1) + mod) % mod);
        ll A, B;
        if (N == mod) {
            // 当 N == mod 时，会导致bottom为0，这时要换一种算法。
            bottom = inv((1 - quickPow(2, N / 2) + mod) % mod);
            A = (1 - 2 * bottom) % mod;
            B = bottom;
        } else if (N % 2) {
            A = (-quickPow(2, N / 2 + 1) - 1 - quickPow(2, N - 1) + mod * 2) %
                mod * bottom % mod;
            B = (quickPow(2, N / 2) + 1) % mod * bottom % mod;
        } else {
            A = (quickPow(2, N / 2) - 1 - quickPow(2, N - 1) + mod * 2) %
                mod * bottom % mod;
            B = (-quickPow(2, N / 2) + 1 + mod) % mod * bottom % mod;
        }
        ll res =
            (-B * inv(A * A % mod - 2 * B * B % mod) % mod + mod) % mod;
        std::cout << res << '\n';
    }

    return 0;
}