26牛客暑假多校3

点击查看题面

K题 Turn-by-Turn Navigation

题目大意

给定 $n$ 个整数点 $p_1,\dots ,p_n$，沿着路径 $p_1\to p_2\to \cdots \to p_n$ 前进。在每个中间点 $p_i(2\le i\le n-1)$，比较到达方向 $\overrightarrow{p_{i-1}{p}_i}$ 和离开方向 $\overrightarrow{p_i{p}_{i+1}}$，输出左转（LEFT）、右转（RIGHT）或直行（STRAIGHT）。保证路线中不包含 ${180}^{\circ }$ 掉头（U-turn）。

数据范围：

• $1\le T\le 500$
• $3\le n\le {10}^5$，$\sum n\le 2\cdot {10}^5$
• $-{10}^9\le x_i,y_i\le {10}^9$

---

思路

相关算法：二维叉积

对于连续的三点 $P_{i-1},P_i,P_{i+1}(2\le i\le n-1)$：

1. 构造转向向量：

   • 到达向量：$\mathit{u}=P_i-P_{i-1}=(x_i-x_{i-1},y_i-y_{i-1})$
   • 离开向量：$\mathit{v}=P_{i+1}-P_i=(x_{i+1}-x_i,y_{i+1}-y_i)$

2. 计算二维叉积：

   $$\mathrm{cross}(\mathit{u},\mathit{v})=u_x{v}_y-u_y{v}_x$$

   注：叉积结果最大可达 $8\cdot {10}^{18}$，必须使用 64 位有符号整数（long long）计算。

3. 判定法则：

   • $\mathrm{cross}(\mathit{u},\mathit{v})>0$：$\mathit{v}$ 在 $\mathit{u}$ 的逆时针方向，判定为 LEFT。
   • $\mathrm{cross}(\mathit{u},\mathit{v})<0$：$\mathit{v}$ 在 $\mathit{u}$ 的顺时针方向，判定为 RIGHT。
   • $\mathrm{cross}(\mathit{u},\mathit{v})=0$：两向量共线。因无掉头，判定为 STRAIGHT。

---

参考代码

参考代码

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

void fc() {
    int n;
    cin >> n;

    ll x0, y0, x1, y1, x2, y2;
    cin >> x0 >> y0 >> x1 >> y1;

    for (int i = 2; i < n; ++i) {
        cin >> x2 >> y2;

        ll ux = x1 - x0, uy = y1 - y0;
        ll vx = x2 - x1, vy = y2 - y1;
        ll k = ux * vy - uy * vx;

        if (k > 0) cout << "LEFT";
        else if (k < 0) cout << "RIGHT";
        else cout << "STRAIGHT";

        cout << (i == n - 1 ? "" : " ");

        x0 = x1; y0 = y1;
        x1 = x2; y1 = y2;
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    if (cin >> t) {
        while (t--) fc();
    }
    return 0;
}

复杂度分析

• 时间复杂度：$\mathcal{O}(N)$。在线读取并处理每个点，单次计算为 $\mathcal{O}(1)$，总复杂度为 $\mathcal{O}(\sum n)$。
• 空间复杂度：$\mathcal{O}(1)$。消除了原代码中存储所有节点的 vector，实现常数级内存开销。

L题 Uphill Duel

题目大意

给定一个 $n\times m$ 的网格，每个格子包含互不相同的高度 $h_{i,j}$。两名玩家轮流移动单枚棋子，每次只能将棋子移动到四连通相邻且高度严格大于当前格子的位置。无法移动者判负。 给出 $q$ 次独立查询，每次给定棋子起始坐标 $(r,c)$，判断最优博弈下先手胜（First）还是后手胜（Second）。

数据范围： $T\le 500$，$1\le n,m\le {10}^5$，$\sum (n\cdot m)\le {10}^5$$1\le h_{i,j}\le {10}^9$$1\le q\le {10}^5$，$\sum q\le {10}^5$

---

思路

1. 博弈模型抽象

• 模型映射：本题属于单棋子在有限 DAG 上的常态博弈（Normal Play）。
• 状态退化：游戏不存在多个独立子游戏的组合，无需计算 Sprague-Grundy (SG) 函数，仅需判定每个状态的二值胜负性（必胜态 / 必败态）。

2. 状态转移法则

定义 $\mathrm{win}[u]$ 表示棋子位于节点 $u$ 时当前行动方的胜负状态（$\mathrm{true}$ 为必胜态，$\mathrm{false}$ 为必败态）：

• 必败态（Loss / P-state）：节点 $u$ 无任何相邻更高格子；或其所有相邻的更高格子均为必胜态。
• 必胜态（Win / N-state）：节点 $u$ 存在至少一个相邻更高格子 $v$，满足 $v$ 为必败态。

转移方程：

$$\mathrm{win}[u]=\underset{v\in \mathrm{Adj}(u),h_v>h_u}{\bigvee }(\mathrm{\neg }\mathrm{win}[v])$$

3. 隐式拓扑序 DP

由于棋子只能向严格更高处移动，边方向为低高度指向高高度，图无环。

• 拓扑序：高度严格递减序列即为 DAG 的逆向拓扑序。
• 实现技巧：直接对所有节点按高度 $h$ 降序排序，无需显式建立邻接表。按排序后的顺序遍历更新，可确保计算 $u$ 时，所有更高的相邻节点 $v$ 的状态 $\mathrm{win}[v]$ 已确定。
• 转移剪枝：在检查四个方向时，一旦发现任意 $\mathrm{\neg }\mathrm{win}[v]$ 为真，立刻置 $\mathrm{win}[u]=\mathrm{true}$ 并 break，无需继续扫描其他邻居。

---

参考代码

代码

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

const int N = 1e5 + 5;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

int a[N];
bool win[N];
int b[N];
int n, m;

void fc() {
    cin >> n >> m;
    int sz = n * m;
    for (int i = 0; i < sz; i++) {
        cin >> a[i];
        b[i] = i;
        win[i] = false;
    }

    sort(b, b + sz, [&](int x, int y) {
        return a[x] > a[y];
    });

    for (int idx = 0; idx < sz; idx++) {
        int u = b[idx];
        int x = u / m, y = u % m;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            
            int v = nx * m + ny;
            if (a[u] >= a[v]) continue;
            if (!win[v]) {
                win[u] = true;
                break;
            }
        }
    }

    int k;
    cin >> k;
    while (k--) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        cout << (win[x * m + y] ? "First\n" : "Second\n");
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    if (cin >> t) {
        while (t--) fc();
    }
    return 0;
}

---

复杂度分析

• 时间复杂度：

  • 节点排序：$\mathcal{O}(nm\log (nm))$
  • 状态转移：每个节点最多检查 $4$ 个邻居，为 $\mathcal{O}(nm)$
  • 单次查询：$\mathcal{O}(1)$，总查询 $\mathcal{O}(q)$
  • 总时间复杂度：$\mathcal{O}(\sum (nm\log (nm)+q))$，可通过。

• 空间复杂度：

  • 静态数组存储高度、状态与拓扑索引，空间开销为 $\mathcal{O}(nm)$。

A题 Bitmask

---

题目大意

给定一个长度为 $n$ 的非负整数数组 $a_1,a_2,\dots ,a_n$，其中 $a_i<2^{30}$。定义 $f(x)$ 为 $x$ 的二进制表示中极长连续 $1$ 段的数量。需要处理 $m$ 次全局按位操作（按位与 &、按位或 |、按位异或 ^）。每次操作后，求出并输出：$\sum _{i=1}^{n}f(a_i)$

数据范围：$1\le n\le 3\times {10}^5,0\le a_i<2^{30}(1\le i\le n),$$1\le m\le 3\times {10}^5,1\le \text{type}\le 3,0\le x<2^{30}$

---

思路

直接对每个数维护其二进制表示复杂度过高。注意到以下两个核心性质：

1. 连续 $1$ 段的判别条件

在二进制表示中，一个极长连续 $1$ 段的结尾必然对应一对相邻位：高位为 $0$，低位为 $1$。

• 考虑到数值范围 $a_i<2^{30}$，数值的有效位数为 $0\sim 29$ 位（共 30 位）。
• 定义第 $30$ 位恒为 $0$。
• 那么，对于任意数 $x$，$f(x)$ 等价于在二进制下满足“第 $j$ 位为 $1$ 且第 $j+1$ 位为 $0$”的位对 $(j,j+1)$ 的数量：$$f(x)=\sum _{j=0}^{29}[\text{get}(x,j)=1\wedge \text{get}(x,j+1)=0]$$

2. 按位操作的独立性

所有按位操作（&, |, ^）对二进制的每一位都是独立且并行的。

• 全局对所有 $a_i$ 作用参数 $x$ 时，第 $j$ 位的新值仅取决于原数组在第 $j$ 位的值以及 $x$ 的第 $j$ 位。
• 因此，我们可以拆分维护原数组在 相邻两位 $(j,j+1)$ 上的频次分布。

---

实现

1. 状态定义： 维护三维数组 cnt[j][v1][v2]，表示当前数组中有多少个数满足：

   • 第 $j$ 位的值为 $v_1\in \{0,1\}$
   • 第 $j+1$ 位的值为 $v_2\in \{0,1\}$ 其中 $j\in [0,29]$。

2. 初始化： 遍历输入数组 $a$，将所有 $a_i$ 的每对相邻位 $(j,j+1)$ 的值统计入 cnt 数组。

3. 转移维护： 对于每次操作 $(op,x)$：

   • 提取 $x$ 在第 $j$ 位的值 $q=\text{get}(x,j)$，在第 $j+1$ 位的值 $p=\text{get}(x,j+1)$。
   • 根据操作类型定义映射函数 $f(val,bit)$：
     • $op=1$ (AND): $val\mathrm{\&}bit$
     • $op=2$ (OR): $val\mid bit$
     • $op=3$ (XOR): $val\oplus bit$
   • 枚举旧状态 $(j_0,k_0)\in \{0,1\}\times \{0,1\}$，更新至新状态 $(f(j_0,q),f(k_0,p))$。

4. 答案统计： 每次修改后，所有 $a_i$ 的 $f(a_i)$ 之和即为所有满足“低位为 $1$、高位为 $0$”的计数之和：

   $$\text{Ans}=\sum _{j=0}^{29}cnt[j][1][0]$$

---

复杂度分析

• 时间复杂度：
  • 初始化预处理：$O(30\cdot n)$
  • 单次修改与统计：$O(30\cdot 2\times 2)=O(120)=O(1)$
  • 总时间复杂度：$O(30(n+m))$，对于 $n,m\le 3\cdot {10}^5$，运算次数约为 $1.8\cdot {10}^7$，可轻松通过。
• 空间复杂度：
  • 辅助状态空间 $30\times 2\times 2$ 为常数级别，总空间复杂度 $O(n)$。

---

参考代码

参考代码

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

const int N = 3e5 + 5;
int cnt[31][2][2];
int n, m;
int a[N];

inline int get(int x, int p) { 
    return (x >> p) & 1; 
}

void fc() {
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        for (int j = 0; j < 30; j++) {
            cnt[j][get(a[i], j)][get(a[i], j + 1)]++;
        }
    }

    std::cin >> m;
    while (m--) {
        int o, x;
        std::cin >> o >> x;

        auto f = [&](int val, int bit) -> int {
            if (o == 1) return val & bit;
            if (o == 2) return val | bit;
            return val ^ bit;
        };

        for (int i = 0; i < 30; i++) {
            int nxt[2][2] = {0};
            int q = get(x, i), p = get(x, i + 1);

            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    nxt[f(j, q)][f(k, p)] += cnt[i][j][k];
                }
            }

            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    cnt[i][j][k] = nxt[j][k];
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < 30; i++) {
            ans += cnt[i][1][0];
        }
        std::cout << ans << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t = 1;
    while (t--) fc();
    return 0;
}

---

B题 Buy One More

---

题目大意

小明初始有 $n$ 元钱，一瓶饮料售价 $1$ 元。每次喝完一瓶饮料，他有 $\frac{a}{b}$ 的概率获得 $c$ 元（即中奖），有 $1-\frac{a}{b}$ 的概率什么也得不到。获得的钱可以继续用来购买饮料，每瓶饮料的获奖事件相互独立。

求小明恰好喝完 $m$ 瓶饮料后花光所有钱的概率，答案对 $998244353$ 取模。

数据范围：

• $T$（测试数据组数）：$1\le T\le 200000$
• $n,m,c$：$1\le n,m,c\le 2000000$
• $a,b$：$0\le a<b<998244353$

---

思路

算法原理

本题本质上是一个有限状态下的随机游走（Random Walk）与停时问题，核心在于通过资金平衡确定中奖次数，并利用 Raney 引理（Raney's Lemma / 循环引理） 求解满足前缀和约束的合法路径数。

1. 资金平衡方程

假设在喝完 $m$ 瓶饮料的过程中，小明一共中奖了 $k$ 次：

• 初始资金为 $n$ 元；
• 喝完 $m$ 瓶饮料共支出 $m$ 元；
• 中奖 $k$ 次共获得 $k\cdot c$ 元。

若恰好在喝完第 $m$ 瓶饮料时花光所有钱，则最终剩余金额必须恰好为 $0$：

$$n+k\cdot c-m=0⟹k=\frac{m-n}{c}$$

因此，中奖次数 $k$ 是唯一确定的：

1. 若 $n>m$、$(m-n)modc\ne 0$、 $k>m$ 或 $k<0$，说明不可能恰好在第 $m$ 瓶时花光钱，概率直接为 $0$。
2. 否则，问题转化为：在 $m$ 次独立重复试验中恰好中奖 $k$ 次，且在前 $1$ 至 $m-1$ 次喝饮料的过程中，小明手中的钱始终严格大于 $0$（即不会提前破产），求该过程发生的概率。

2. 合法路径计数（Raney 引理）

定义第 $i$ 次喝饮料后资金的净变化量为 $X_i$：

• 若中奖，$X_i=c-1$；
• 若未中奖，$X_i=-1$。

前 $i$ 步后小明的资金为 $S_i=n+\sum _{j=1}^i{X}_j$。我们需要满足 $S_i>0(1\le i<m)$ 且 $S_m=0$（即 $\sum _{j=1}^m{X}_j=-n$）。

根据 Raney 引理：对于任意一个总和为 $-n$（$n>0$）的整数序列 $X_1,X_2,\dots ,X_m$，在其所有 $m$ 种循环移位中，恰好有 $n$ 种循环移位满足其所有前缀和加上 $n$ 后在到达第 $m$ 步前严格大于 $0$。

因此，在所有 $(\genfrac{}{}{0ex}{}{m}{k})$ 种中奖序列排列中，满足“中途资金不为 $0$ 且恰好在第 $m$ 步归零”的合法序列所占比例恰好为 $\frac{n}{m}$。

故合法排列方案数为：

$$\text{合法方案数}=\frac{n}{m}(\genfrac{}{}{0ex}{}{m}{k})$$

结合每次中奖概率 $q=\frac{a}{b}(\mathrm{mod}998244353)$ 与未中奖概率 $p=1-q(\mathrm{mod}998244353)$，可得最终概率计算公式：

$$P=\frac{n}{m}\cdot (\genfrac{}{}{0ex}{}{m}{k})\cdot q^k\cdot p^{m-k}(\mathrm{mod}998244353)$$

应用场景

• 随机游走与格点路径计数：Raney 引理是处理带前缀和限制的路径计数（如 Catalan 数的推广、不相交路径）的有力工具。
• 概率破产模型：计算金融/博弈模型中资本在特定步数首次归零的概率分布。

---

补题中遇到的问题

1. 问： 为什么是乘以$\frac{a}{b}$?
   答： 乘以 $\frac{n}{m}$ 的本质逻辑在于：利用 Raney 引理（Raney's Lemma / Cycle Lemma） 将非对称的“中途资金时刻大于 $0$”前缀限制，转化为全局对称的“循环移位划分”。
   i. 等价类分割： 将由 $k$ 次中奖（净变化 $c-1$）与 $m-k$ 次未中奖（净变化 $-1$）构成的 $m$ 步序列放在环上，任意序列均可生成大小为 $m$ 的循环等价类。
   ii. 局部比例恒定： 整个序列净下降 $n$ 个单位。根据 Raney 引理，在此等价类的 $m$ 个循环移位中，折线在下降过程中恰好产生 $n$ 个突破历史新低的位置。以这 $n$ 个位置的下一个位置作为起点，均能构造出一个在前 $m-1$ 步资金保持 $>0$、第 $m$ 步刚好降至 $0$ 的合法序列。因此，每个等价类中的合法序列占比恒为 $\frac{n}{m}$。
   iii. 全局线性累加： 合法排列方案数为：

$$\text{Valid Paths}=\frac{n}{m}\times (\genfrac{}{}{0ex}{}{m}{k})$$

---

复杂度分析

时间复杂度：

• 预处理：预处理 $O(N)$ 范围内的阶乘及阶乘逆元，复杂度为 $\mathcal{O}(N)$，其中 $N=2\times {10}^6$。
• 单次查询：对于每组测试数据，仅需进行常数次模逆元与组合数计算，单次复杂度为 $\mathcal{O}(\log \text{MOD})$。
• 总时间复杂度：$\mathcal{O}(N+T\log \text{MOD})$。

空间复杂度：

• 空间复杂度：$\mathcal{O}(N)$，用于存储阶乘与逆元数组。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e6 + 5;
const ll MOD = 998244353;
ll fact[N], inv[N];

// 快速幂计算 (a^b) % MOD
ll qpow(ll a, ll b) {
    ll res = 1;
    for (a %= MOD; b > 0; b >>= 1, a = a * a % MOD) {
        if (b & 1) res = res * a % MOD;
    }
    return res;
}

// 预处理阶乘与逆元，用于快速计算组合数
void init_fac(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i % MOD;
    inv[n] = qpow(fact[n], MOD - 2);
    for (int i = n - 1; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % MOD;
}

// 计算组合数 C(n, k) % MOD
inline ll C(int n, int k) {
    if (n < 0 || k < 0 || k > n) return 0;
    return fact[n] * inv[k] % MOD * inv[n - k] % MOD;
}

ll n, m, c, a, b;
ll q, p; // q 中奖概率, p 不中奖概率

void fc() {
    std::cin >> n >> m >> c >> a >> b;
    
    // 计算满足最终资金归零所必需的中奖次数 k
    ll k = (m - n) / c;
    
    // 边界条件判断：无法恰好在第 m 瓶花光钱
    if (n > m || (m - n) % c || k > m || k < 0) {
        std::cout << "0\n";
        return;
    }
    
    // 计算概率 q 与 p 的模逆元
    q = a * qpow(b, MOD - 2) % MOD;
    p = (b - a) * qpow(b, MOD - 2) % MOD;
    
    // 根据 Raney 引理推导出的最终概率公式计算答案
    ll ans = n * qpow(m, MOD - 2) % MOD * C(m, k) % MOD * qpow(q, k) % MOD * qpow(p, m - k) % MOD;
    std::cout << ans << '\n';
}

int main() {
    // 优化 I/O 读取效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t = 1;
    init_fac(N - 1);
    std::cin >> t;
    while (t--) fc();
    return 0;
}