代码实现原理深度分析：AT_abc310_g

本题要求计算：在 $1$ 到 $K$ 中均匀随机选择操作次数 $x$，执行 $x$ 次“所有高桥君同时将球传给 $A_i$ 指向的人”后，每个高桥君手中球数的期望值（模 $998244353$）。核心难点在于 $K$ 可达 $10^{18}$，无法直接模拟每一步。

代码采用倍增 + 贡献分解 + 反向传播的巧妙技巧，在 $O(N \log K)$ 时间内高效求解。下面分步详解其实现逻辑：

---

一、问题转化：期望 = 路径贡献和 / $K$

• 设 $f(i) = A_i$，$f^x(i)$ 表示从 $i$ 出发走 $x$ 步后的位置。
• 初始球数向量为 $B$，执行 $x$ 次操作后，球分布为：$$\text{球}_j^{(x)} = \sum_{i: f^x(i) = j} B_i$$
• 期望值为：$$E_j = \frac{1}{K} \sum_{x=1}^{K} \text{球}_j^{(x)} = \frac{1}{K} \sum_{i=1}^{N} B_i \cdot \left( \#\{x \in [1,K] \mid f^x(i) = j\} \right)$$
• 目标：对每个 $j$，快速计算所有 $i$ 的 $B_i$ 乘以“从 $i$ 出发在 $1..K$ 步内到达 $j$ 的次数”之和。

---

二、核心思想：二进制分解 + 贡献“播种”与“收割”

1. 倍增表预处理（st 数组）

for (int i = 1; i <= lgm; i++)
    for (int j = 1; j <= n; j++) 
        st[i][j] = st[i-1][st[i-1][j]];

• st[0][i] = A_i：走 $1 = 2^0$ 步后的位置。
• st[j][i]：从 $i$ 出发走 $2^j$ 步后的位置。
• 预处理复杂度 $O(N \log K)$。

2. 贡献“播种”：将 $B_i$ 按 $K$ 的二进制分解分配到倍增路径

for (int i = 1; i <= n; i++) {
    cin >> b;
    int x = st[0][i];  // 先走第1步：i → f(i)
    for (int j = lgm; j >= 0; j--)
        if (m >> j & 1) {
            add(sum[j][x], b);  // 将b“播种”到当前节点x的第j层
            x = st[j][x];       // 继续走2^j步
        }
}

• 关键洞察：
  将 $K$ 二进制分解为 $K = 2^{j_1} + 2^{j_2} + \cdots$。
  从 $i$ 出发走 $K$ 步的路径可拆分为：

  $$i \xrightarrow{1} f(i) \xrightarrow{2^{j_1}} \cdots \xrightarrow{2^{j_2}} \cdots$$

• 播种操作：
  当遇到二进制位 $1$（对应 $2^j$ 步段）时，将 $B_i$ 加到 sum[j][x]，其中 $x$ 是该步段起点（即已走 $t$ 步后的位置）。

  • 物理意义：sum[j][x] 存储了“从 $x$ 开始走 $2^j$ 步过程中，每一步的球数贡献总和”。

• 为何先走1步？
  $x$ 从 $f(i)$ 开始，确保后续处理的是 $x=1..K$ 的步数（而非 $0..K-1$）。结合反向传播，最终覆盖 $1..K$ 所有步数。

3. 反向传播：将高层贡献分解为底层1步贡献

for (int j = lgm; j > 0; j--) {
    for (int i = 1; i <= n; i++) {
        add(sum[j-1][i], sum[j][i]);          // 贡献保留在当前节点
        add(sum[j-1][st[j-1][i]], sum[j][i]); // 贡献传递到下一步节点
    }
}

• 核心机制：
  若 sum[j][v] 有贡献 $c$，表示“从 $v$ 走 $2^j$ 步的路径上，每一步的球数总和为 $c$”。
  将 $2^j$ 步拆分为两个 $2^{j-1}$ 步：

  • 第一段 $2^{j-1}$ 步：终点为 $u = \text{st}[j-1][v]$
  • 第二段 $2^{j-1}$ 步：从 $u$ 继续走
  • 因此，$c$ 应分配到：
    • sum[j-1][v]：第一段路径的贡献
    • sum[j-1][u]：第二段路径的贡献

• 递归分解：
  从 $j = \log K$ 逐层下推至 $j=0$，最终 sum[0][v] 即为 所有 $i$ 的 $B_i$ 乘以“从 $i$ 出发在 $1..K$ 步内到达 $v$ 的次数”之和。

• 正确性验证（以 $K=2$ 为例）：

  • 播种：$B_i$ 加到 sum[1][f(i)]
  • 反向传播：
    • sum[1][x] → sum[0][x]（步1） + sum[0][f(x)]（步2）
  • 完美覆盖 $x=1,2$ 两步。

4. 期望计算：乘以 $K^{-1} \mod 998244353$

ll inv = qp(m % mod, mod - 2);  // 费马小定理求逆元
for (int i = 1; i <= n; i++) 
    cout << sum[0][i] * inv % mod << ' ';

• 由期望公式 $E = \frac{\text{总贡献}}{K}$，模意义下乘 $K$ 的逆元。

---

三、算法正确性关键点

步骤	作用	为何覆盖 $1..K$ 步
播种	将 $B_i$ 按 $K$ 二进制分解分配到路径节点	每个二进制位 $1$ 对应一段 $2^j$ 步，覆盖连续步数区间
反向传播	将 $2^j$ 步贡献分解为 $2^j$ 个 $1$ 步贡献	递归拆分确保每个 $1$ 步都被精确计数
第一步单独处理	起点设为 $f(i)$	结合播种与传播，使步数范围严格为 $1..K$（非 $0..K$ 或 $1..K+1$）

示例验证（样例1）：
$N=5, K=2, A=[3,1,4,1,5], B=[1,1,2,3,5]$

• 播种后：sum[1] = [4,0,1,2,5]（索引1~5）
• 反向传播：
  • sum[1][1]=4 → sum[0][1]+=4, sum[0][3]+=4
  • sum[1][3]=1 → sum[0][3]+=1, sum[0][4]+=1
  • ... → sum[0] = [6,0,5,3,10]
• 期望：$[6/2, 0, 5/2, 3/2, 10/2] = [3,0,2.5,1.5,5]$ → 模 $998244353$ 后与样例一致。

---

四、复杂度分析

步骤	时间复杂度	空间复杂度
倍增表预处理	$O(N \log K)$	$O(N \log K)$
贡献播种		-
反向传播
总计	$O(N \log K)$

• 满足 $N \leq 2 \times 10^5$, $K \leq 10^{18}$ 的约束。

---

五、代码细节亮点

1. 模运算安全

void add(int& a, int b) {
    a += b;
    if (a >= mod) a -= mod;
}

• 避免负数，确保模加正确。

2. 快速幂求逆元

ll qp(ll x, int n) {
    ll ret = 1;
    while (n) {
        if (n & 1) ret = ret * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return ret;
}
inv = qp(K % mod, mod - 2);

• 利用费马小定理（$998244353$ 是质数）求逆元。

3. 高位优先遍历

int lgm = __lg(m);  // 获取 ⌊log₂K⌋

• 确保二进制分解高效。

---

六、总结

该代码通过以下三步实现高效求解：

1. 倍增预处理：将路径查询优化至 $O(\log K)$
2. 贡献播种：利用 $K$ 的二进制分解，将 $B_i$ 分配到倍增路径的关键节点
3. 反向传播：将高层 $2^j$ 步贡献精确分解为 $2^j$ 个 $1$ 步贡献

整个过程避免了直接枚举 $K$ 步，以 $O(N \log K)$ 的复杂度高效求解期望，是处理大规模迭代路径问题的经典范式。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
const ll mod = 998244353;
const int N = 200005;
int st[60][N], sum[60][N];
void add(int& a, int b) {
    a += b;
    if (a >= mod) a -= mod;
}
ll qp(ll x, int n) {
    ll ret = 1;
    while (n) {
        if (n & 1) ret = ret * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return ret;
}
void solve() {
    int n, b;
    ll m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> st[0][i];
    int lgm = __lg(m);//__lg(m) 等同 log2(m)
    for (int i = 1; i <= lgm; i++)
        for (int j = 1; j <= n; j++) st[i][j] = st[i - 1][st[i - 1][j]];
    for (int i = 1; i <= n; i++) {
        cin >> b;
        int x = st[0][i];
        for (int j = lgm; j >= 0; j--)
            if (m >> j & 1) {
                add(sum[j][x], b);
                x = st[j][x];
            }
    }
    for (int j = lgm; j > 0; j--) {
        for (int i = 1; i <= n; i++) {
            add(sum[j - 1][i], sum[j][i]);
            add(sum[j - 1][st[j - 1][i]], sum[j][i]);
        }
    }
    ll inv = qp(m % mod, mod - 2);
    for (int i = 1; i <= n; i++) cout << sum[0][i] * inv % mod << ' ';
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    solve();
    return 0;
}

Preface

有点小套路的一道题目，但是如果你能熟练使用倍增的话本题会很简单。

Problem

给你一个 $n$ 个点的内向基环树森林，每个点有点权。
Alice 会随机选一个 $1$ 到 $k$ 之间的数 $x$（$k$ 给定）。

然后在 $x$ 秒内，每秒每个点会将其点权贡献给父亲（父亲的点权加上了这个点的点权），然后这个点减去自身的点权。
这些点的操作是同时做的。

问每个点最后的期望权值是多少,模 $998244353$。
$n\leq 2\times 10^5,k\leq 10^{18}$。
保证 $k$ 不是模数的倍数。

Solution

容易发现这个期望是假的，题目实际上是要我们求出所有 $k$ 种情况下某个点的权值的加和。
那么显然地，每个点会向 $k$ 步之内的每个点做贡献。

然后你看到了基环树。
我会分讨！先对每个子树开深度桶，差分，然后贡献挂环再处理环的差分！

好想法，但是这太麻烦了，题目给的不止一个基环树，而且分类讨论会写的非常难看，也不好调，我们来想一个更加聪明的简单做法。

有一个很显然，但是大多数人不会注意到的事实，就是倍增的适用性。
当然，树和序列是倍增最常用的场景，但是观察倍增的过程，我们可以得出一个结论，即每个元素的后继不多于一个的图或序列是可以倍增的。

所以，理所当然地，环和基环树也可以进行倍增。

考虑这个题的倍增，我们要求的是某个点被贡献的权值总和，显然倍增的意义是通过 $2^i$ 步内可贡献给点 $u$ 的权值和，这个可以简单实现，然后将数层倍增组合。

在实现上，我们对 $k$ 的二进制从下到上进行倍增，若 $k$ 的这一位为 $1$ 则对答案加上目前状态的贡献，同时将目前状态滚动使得状态与答案对齐。

复杂度 $O(n\log k)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
const ll mod = 998244353;
const int N = 200005;
int st[60][N], sum[60][N];
void add(int& a, int b) {
    a += b;
    if (a >= mod) a -= mod;
}
ll qp(ll x, int n) {
    ll ret = 1;
    while (n) {
        if (n & 1) ret = ret * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return ret;
}
void solve() {
    int n, b;
    ll m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> st[0][i];
    int lgm = __lg(m);//__lg(m) 等同 log2(m)
    for (int i = 1; i <= lgm; i++)
        for (int j = 1; j <= n; j++) st[i][j] = st[i - 1][st[i - 1][j]];
    for (int i = 1; i <= n; i++) {
        cin >> b;
        int x = st[0][i];
        for (int j = lgm; j >= 0; j--)
            if (m >> j & 1) {
                add(sum[j][x], b);
                x = st[j][x];
            }
    }
    for (int j = lgm; j > 0; j--) {
        for (int i = 1; i <= n; i++) {
            add(sum[j - 1][i], sum[j][i]);
            add(sum[j - 1][st[j - 1][i]], sum[j][i]);
        }
    }
    ll inv = qp(m % mod, mod - 2);
    for (int i = 1; i <= n; i++) cout << sum[0][i] * inv % mod << ' ';
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    solve();
    return 0;
}