牛客周赛60

A 困难数学题

小歪正在计算数学题： $y = x xor x xor x xor x$ 。多难啊，帮帮小歪吧。

直接输出 0 即可。

B 构造序列

给你 $n$ 个正数和 $m$ 个负数，请你使用这些数字，构造一个序列。
序列需要满足：正数不能和正数相邻，负数不能和负数相邻。
那么，最多能构造多长的序列？

void solve() {
    int n, m;cin >> n >> m;
    int x = min(n, m);
    cout << x + (n == m ? x : x + 1) << '\n';
}

C 连点成线

小红有一个 $n \times n$ 大小的格子棋盘，我们使用 $(i, j)$ 表示棋盘中从上往下数第 $i$ 行和从左往右数第 $j$ 列的单元格。棋盘上有 $m$ 个棋子，第 $i$ 个棋子的坐标是 $(x_{i}, y_{i})$ 。
对于一对棋子 $i$ 和 $j$ ，如果满足 $x_{i} = x_{j}$ 或者 $y_{i} = y_{j}$ ，则两个棋子之间可以连线。
小红有点无聊，于是她把能连的线都连上了。现在，她想知道，最长的那条线，长度是多少。
特别地，如果连线数量为 $0$ ，则输出 $0$ 。

void solve() {
    int n, m;cin >> n >> m;
    vector<pair<int, int>> a(m + 1);

    for (int i = 1;i <= m;i++)cin >> a[i].first >> a[i].second;
    sort(a.begin() + 1, a.end(), [](auto x, auto y) {
        if (x.first == y.first)return x.second < y.second;
        return x.first < y.first;
        });
    map<int, int> mp;
    int ans = 0;
    for (int i = 1;i <= m;i++) {
        auto [x, y] = a[i];
        if (!mp.count(x)) {
            mp[x] = y;
        } else {
            ans = max(ans, y - mp[x]);
        }
    }
    mp.clear();
    for (int i = 1;i <= m;i++) {
        auto [x, y] = a[i];
        if (!mp.count(y)) {
            mp[y] = x;
        } else {
            ans = max(ans, x - mp[y]);
        }
    }
    cout << ans << '\n';
}

D 我们 N 个真是太厉害了

这天， $n$ 位小朋友聚在一起吹牛，他们每个人手里都有一定数量的小星星，为了方便统计，我们使用 $a_{1}, a_{2}, \dots, a_{n}$ 来表示。
小小歪吹牛到，从我们几个人中挑出几个来，手里的小星星数量全部加起来，可以表示出 $n$ 以内的任意一个正整数！
小小龙认为小歪错了，但是他是小朋友，他不会计算。

所以小小龙来求助你，他想让你找到最小的整数证明小小歪是错误的。

Solution

DP 的思想

bitset 优化 01 背包(和之前 swpuOj 里面的散兵几乎一样)

时间复杂度： $O (\frac{n^{2}}{w}) \approx 1.5 e 8$ 勉强能过

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    bitset<100010> b;

    b[0] = 1;
    for (int i = 1;i <= n;i++) {
        b |= (b << a[i]);
    }
    for (int i = 1;i <= n;i++) {
        if (!b[i]) {
            cout << i << '\n';return;
        }
    }
    cout << "Cool!\n";
}

若已经能组成 $[1, x]$ 中的任何数，则下一个数 $a_{i}$ 需要达到什么要求能使得组成 $[1, x + a_{i}]$ 的所有数呢？

条件： $a_{i} \leq x + 1$ ，当 $a_{i} > x + 1$ 时，则 $x + 1$ 这个数一定无法组成，否则 $a_{i}$ 一定能和前面的数构成 $[x + 1, x + a_{i}]$ 区间的数

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    sort(a.begin() + 1, a.end());
    int x = 0;
    for (int i = 1;i <= n;i++) {
        if (a[i] > x + 1 && x < n) {
            cout << x + 1 << '\n';return;
        }
        x += a[i];
    }
    cout << "Cool!\n";
}

E 折返跑

上体育课了！今天的项目是折返跑，笔直的跑道可以看作是一条数轴。跑道上有 $n$ 个点位，其中，老师在 $1$ 点和 $n$ 点处各放了两根杆子，称为左杆和右杆，作为折返跑的折返点。
老师规定，今天一共需要跑 $m$ 趟。我们认为，从一根杆子开始，跑到另一根杆子结束为一趟，显然，一共需要进行 $m - 1$ 次折返。 $Z a o l y$ 偶然发现，杆子是可推动的，所以他有了一个大胆的想法——
$∙$ 每次跑至右杆折返后，都需要把右杆向左推动一段距离（大于 $0$ ），但仍保证右杆位于整数点，且在左杆的右边（不能与左杆重合）；
$∙$ 每次跑至左杆折返后，都需要把左杆向右推动一段距离（大于 $0$ ），但仍保证左杆位于整数点，且在右杆的左边（不能与右杆重合）；
现在，给出整数 $n$ 和 $m$ 的值，请问 $Z a o l y$ 一共有多少种不同的推杆方法？由于答案可能很大，请将答案对 $(10^{9} + 7)$ 取模后输出。注意，每次折返时都需要推杆，如果某一轮无法推动，则这一轮推杆非法。

Solution

实际上是要在 $m - 1$ 次折返中每次至少推 1，一共不能超过 $n - 2$ 即 $\in [m - 1, n - 2]$ 。

1931(925div3)：组合数学的复习

相当于一共有 $x (m - 1 \leq x \leq n - 2)$ 个球分别放入 $m - 1$ 个盒子中(每个盒子至少有一个球)。即 $C (x - 1, m - 2)$

即答案是 $C (n - 3, m - 2) + C (n - 2, m - 2) + \dots + C (m - 2, m - 2) = \sum_{i = m - 1}^{n - 2} C (i - 1, m - 2)$

时间复杂度是 $O (T n \log n)$ 的，复杂度过高了。所以需要换一种方式解决。

引入一个 $a_{m}$ ，代表有多少个"球"没有用上，所以有：

$x_{1} + x_{2} + \dots + x_{m - 1} + x_{m} = n - 2, x_{i} \geq 1 \cap x_{m} \geq 0$

所以：

$(x_{1} - 1) + (x_{2} - 1) + \dots + (x_{m - 1} - 1) + x_{m} = n - 2, x_{i} \geq 0$

$⟹ x_{1} + x_{2} + \dots + x_{m} = n - 2 - m + 1, x_{i} \geq 0$

即有 $n - m - 1$ 个球，放入 $m$ 个盒子内(盒子内可以没有球)，有多少种方式？

$\to C (n - 2 - m - 1 + m - 1, m - 1) = C (n - 2, m - 1)$

$⟹ C (n - 2, m - 1)$

时间复杂度 $O (T \log n)$

证明

\sum_{i = m - 1}^{n - 2} C (i - 1, m - 2) = C (n - 2, m - 1)

成立

考虑组合数的性质，我们知道：

(\binom{i}{j}) = (\binom{i - 1}{j}) + (\binom{i - 1}{j - 1})

利用这个性质，将原等式视为累加，从而它等价于：

\sum_{i = m - 1}^{n - 2} (\binom{i - 1}{m - 2}) = \sum_{i = m - 1}^{n - 2} (\binom{i - 1}{i - m + 1})

从而，这个和可以被重新组合并逐渐结合利用 Pascal’s 恒等式化简到：

\sum_{i = m - 1}^{n - 2} (\binom{i - 1}{m - 2}) = (\binom{n - 2}{m - 1})

这个是给定组合的性质。从组合意义上来讲，右边的组合数 $(\binom{n - 2}{m - 1})$ 表示从 $n - 2$ 个元素选择出 $m - 1$ 个的方案数，而等式左边逐渐累加到这个上限，反映了选择某个特定点作为其余选择的开端，通过累积实现满足条件的排列。

综上所述，这个等式成立。

void solve() {
    int n, m;cin >> n >> m;
    cout << C(n - 2, m - 1) << '\n';
}

F 口吃

$Z a o l y$ 要讲一句话，这句话有 $n$ 个字，他要一个字一个字讲出来。奈何 $Z a o l y$ 口吃：
讲到第 $1$ 个字时，下一个要讲的字有 $\frac{a_{1}}{a_{1} + b_{1}}$ 的概率前进到第 $2$ 个字，有 $\frac{b_{1}}{a_{1} + b_{1}}$ 的概率仍是第 $1$ 个字。
讲到第 $i$ （ $2 \leq i \leq n - 1$ ）个字时，下一个要讲的字有 $\frac{a_{i}^{2}}{a_{i}^{2} + 2 a_{i} \cdot b_{i} + b_{i}^{2}}$ 的概率前进到第 $i + 1$ 个字，有 $\frac{2 a_{i} \cdot b_{i}}{a_{i}^{2} + 2 a_{i} \cdot b_{i} + b_{i}^{2}}$ 的概率仍是第 $i$ 个字，有 $\frac{b_{i}^{2}}{a_{i}^{2} + 2 a_{i} \cdot b_{i} + b_{i}^{2}}$ 的概率倒退到第 $i - 1$ 个字。

讲到第 $n$ 个字时，讲话完毕，停止讲话。

直到讲话完毕， $Z a o l y$ 总共讲出的字数的期望是多少？

Solution

设 $e_{u, u + 1}$ 代表从 $u \to u + 1$ 的期望步数，根据题意有：(将题目的三个概率设为 $p_{1 i, 2 i, 3 i}$ )

$e_{u, u + 1} = p_{1 u} \times e_{u + 1, u + 1} + p_{2 u} \times e_{u, u + 1} + p_{3 u} \times e_{u - 1, u + 1} + 1$

有 $e_{u - 1, u + 1} = e_{u - 1, u} + e_{u, u + 1}$ 带入得：( $e_{u, u} = 0$ )

$⟹ e_{u, u + 1} = \frac{1 + p_{3 u} \times e_{u - 1, u}}{p_{1 u}} \to \frac{b_{i}^{2} \times e_{i - 1, i} + (a_{i} + b_{i})^{2}}{a_{i}^{2}}$

将 $e_{i, i + 1} \to e_{i}$ 代表从 $i \to i + 1$ 的期望步数。

$e_{0} = 1, e_{1} = \frac{a_{1} + b_{1}}{a_{1}}$

$e_{i} = \frac{b_{i}^{2} \times e_{i - 1} + (a_{i} + b_{i})^{2}}{a_{i}^{2}}$

void solve() {
    int n;cin >> n;
    vector<int> p(n), q(n), e(n);
    for (int i = 1;i < n;i++)cin >> p[i];
    for (int i = 1;i < n;i++)cin >> q[i];
    e[0] = 1;e[1] = (p[1] + q[1]) * inv(p[1]) % mod;
    for (int i = 2;i < n;i++) {
        e[i] = (q[i] * q[i] % mod * e[i - 1] % mod + (p[i] + q[i]) * (p[i] + q[i]) % mod) % mod * inv(p[i]) % mod * inv(p[i]) % mod;
    }
    int ans = 0;
    for (int i = 0;i < n;i++) {
        ans += e[i];ans %= mod;
    }
    cout << ans << '\n';
}

官方题解：

Note

设 $f_{i}$ 代表从第 $i$ 个字开始讲完这句话的期望

$f_{1} = \frac{a_{1}}{a_{1} + b_{1}} f_{2} + \frac{b_{1}}{a_{1} + b_{1}} f_{1} + 1 \to f_{1} = f_{2} + \frac{a_{1} + b_{1}}{a_{1}}$

$P = 1, Q = \frac{a_{1} + b_{1}}{a_{1}} \to f_{1} = P f_{2} + Q$

$f_{2} = \frac{a^{2}}{(a + b)^{2}} f_{3} + \frac{2 a b}{(a + b)^{2}} f_{2} + \frac{b^{2}}{(a + b)^{2}} f_{1} + 1 \to (a + b)^{2} f_{2} = a^{2} f_{3} + b^{2} (f_{2} + \frac{a_{1} + b_{1}}{a_{1}}) + (a + b)^{2}$

$f_{2} = f_{3} + \frac{b_{2}^{2}}{a_{2}^{2}} \times \frac{a_{1} + b_{1}}{a_{1}} + \frac{(a_{2} + b_{2})^{2}}{a_{2}^{2}}$

$(a_{i} + b_{i})^{2} f_{i} = a_{i}^{2} f_{i + 1} + b_{i}^{2} f_{i - 1} + (a_{i} + b_{i})^{2}$ ，这时的 $f_{i - 1} = P f_{i} + Q$ 已经得到了，所以 $f_{i}$ 的式子是可求的了。

所以可以直接推 $f_{i}$ 的通项公式：

$f_{i} = \frac{a^{2} f_{i + 1} + Q b^{2} + (a + b)^{2}}{a^{2} + b^{2} - b^{2} P}$ $(P, Q)$ 由前一项得到，则这一项的 $P^{'} = \frac{a^{2}}{a^{2} + b^{2} - b^{2} P}, Q^{'} = \frac{Q b^{2} + (a + b)^{2}}{a^{2} + b^{2} - b^{2} P}$

处理完所有的 $P_{i}, Q_{i}$ 后，按照公式 $f_{i - 1} = P_{i - 1} f_{i} + Q_{i - 1}$ 递推

#define int long long
constexpr int mod = 1e9 + 7;
void solve() {
    int n;cin >> n;
    vector<int> p(n), q(n);
    for (int i = 1;i < n;i++)cin >> p[i];
    for (int i = 1;i < n;i++)cin >> q[i];
    int P = 1, Q = (p[1] + q[1]) * inv(p[1]) % mod;
    p[1] = P, q[1] = Q;
    for (int i = 2;i < n;i++) {
        int a = p[i], b = q[i];
        int mu = (((a * a % mod + b * b % mod) % mod - b * b % mod * P % mod) + mod) % mod;
        P = a * a % mod * inv(mu) % mod;
        Q = (Q * b % mod * b % mod + (a + b) * (a + b) % mod) % mod * inv(mu) % mod;
        p[i] = P, q[i] = Q;
    }
    vector<int> f(n + 1);
    f[n] = 1;
    for (int i = n - 1;i >= 1;i--) {
        f[i] = p[i] * f[i + 1] % mod + q[i];f[i] %= mod;
    }
    cout << f[1] << '\n';
}