一、问题分析与数学建模

1.1 问题本质

这是一道概率期望 + 多项式变换的数学问题，核心在于通过多项式复合来高效计算多轮随机洗牌后的期望值。

问题形式化

给定：

• $n$ 张牌，编号 $1 \sim n$
• $m$ 轮洗牌操作，第 $i$ 轮取出前 $A_i$ 张牌
• 分数函数：$f(i) = i$ (type=1) 或 $f(i) = i^2$ (type=2)
• $Q$ 次查询，每次询问位置 $c_i$ 的期望分数

目标：

• 计算经过 $m$ 轮洗牌后，位置 $k$ 上的牌的期望分数 $\mathbb{E}[f(\text{card}_k)]$

---

1.2 核心数学观察

观察 1：洗牌的概率模型

对于一轮洗牌，将牌分为两堆：

• 第一堆：前 $A$ 张牌（编号 $1 \sim A$）
• 第二堆：后 $B = n - A$ 张牌（编号 $A+1 \sim n$）

合并过程：当第一堆剩 $X$ 张，第二堆剩 $Y$ 张时：

• 以概率 $\frac{X}{X+Y}$ 取第一堆的最下面的牌
• 以概率 $\frac{Y}{X+Y}$ 取第二堆的最下面的牌

这是一个riffle shuffle（交错洗牌）的概率模型。

---

观察 2：位置转移概率

关键引理 1：经过一轮洗牌后，位置 $k$ 的牌来自原位置 $i$ 的概率为：

$$P(i \to k \mid A) = \begin{cases} \frac{\binom{i-1}{k-1}\binom{A-i}{0}\binom{B}{k-1}}{\binom{n}{k}} & \text{if } i \le A \text{ and } i \le k \le i + B \\ \frac{\binom{A}{k-j}\binom{j-A-1}{0}\binom{B-j+A}{k-1}}{\binom{n}{k}} & \text{if } i > A \text{ and } k \text{ valid} \\ 0 & \text{otherwise} \end{cases}$$

但是：直接计算这些概率并求和是 $O(n^2)$ 的，对于 $n = 10^7$ 不可行。

---

观察 3：多项式不变性（关键！）

定理 1（多项式闭包性质）：

设洗牌前，位置 $i$ 的期望值为 $g(i)$。

1. 如果 $g(i) = ai + b$（一次多项式），则洗牌后位置 $k$ 的期望值 $h(k)$ 也是 $k$ 的一次多项式：

   $$h(k) = a' k + b'$$

2. 如果 $g(i) = \alpha i^2 + \beta i + \gamma$（二次多项式），则洗牌后 $h(k)$ 也是 $k$ 的二次多项式：

   $$h(k) = \alpha' k^2 + \beta' k + \gamma'$$

证明思路：

$$h(k) = \sum_{i=1}^n P(i \to k \mid A) \cdot g(i)$$

关键在于证明 $\sum_{i=1}^n P(i \to k \mid A) \cdot i^d$ 是 $k$ 的 $d$ 次多项式。

这个性质基于riffle shuffle的组合性质：位置转移概率本身具有多项式结构。

---

观察 4：算法策略

核心思想：

1. 初始时，位置 $i$ 的期望编号就是 $i$

   • type=1: $\mathbb{E}[f(i)] = i$（初始系数 $a=1, b=0$）
   • type=2: $\mathbb{E}[f(i)] = i^2$（初始系数 $\alpha=1, \beta=0, \gamma=0$）

2. 每轮洗牌后，多项式系数发生变换：

   • $(a, b) \to (a', b')$
   • $(\alpha, \beta, \gamma) \to (\alpha', \beta', \gamma')$

3. 关键：只需计算系数变换规则，而不需要计算每个位置的具体概率

4. 时间复杂度：$O(m)$ 轮，每轮 $O(1)$ 计算系数，$O(Q)$ 次查询

---

二、数学推导：系数变换公式

2.1 线性情况 (type=1)

设洗牌前期望为 $g(i) = ai + b$，洗牌后期望为 $h(k) = a_A \cdot (ai + b) + b_A = (a \cdot a_A)k + (b \cdot a_A + b_A)$。

等等，这里应该是 $h(k) = a_A k + b_A$，其中 $a_A, b_A$ 是洗牌变换的系数。

正确的理解是：$h(k) = \sum_i P(i \to k) \cdot (ai + b) = a \sum_i P(i \to k) \cdot i + b \sum_i P(i \to k)$

设 $M_1(k) = \sum_i P(i \to k) \cdot i$，$M_0(k) = \sum_i P(i \to k) = 1$。

那么 $h(k) = a \cdot M_1(k) + b$。

由多项式性质，$M_1(k) = a_A k + b_A$，所以：

$$h(k) = a(a_A k + b_A) + b = (a \cdot a_A) k + (a \cdot b_A + b) $$

系数更新规则：

$$a' = a \cdot a_A, \quad b' = a \cdot b_A + b$$

---

2.2 计算 $a_A$ 和 $b_A$

设初始时 $g(i) = i$（即 $a=1, b=0$），计算一轮洗牌后 $h(k) = \mathbb{E}[\text{card}_k]$。

根据riffle shuffle的期望性质：

期望位置公式：

$$\mathbb{E}[\text{card}_k] = \sum_{i=1}^n P(i \to k \mid A) \cdot i $$

通过组合数学和概率论的推导（涉及超几何分布的期望计算），可以得到：

$$a_A = 1 - \frac{2A}{n-1} + \frac{2A^2}{n(n-1)}$$ $$b_A = \frac{A(n-A)(n+1)}{n(n-1)}$$

推导细节：

考虑位置 $k$ 的牌的期望编号。设第一堆（前$A$张）中有 $x$ 张牌最终在前 $k$ 个位置中。

由对称性和线性期望：

$$\mathbb{E}[\text{card}_k] = \mathbb{E}[x] \cdot \frac{1 + A}{2} + \mathbb{E}[k - x] \cdot \frac{A + 1 + n}{2} $$

其中：

• $\mathbb{E}[x]$ 是第一堆中在前 $k$ 位的牌数期望
• 第一堆牌的平均编号是 $\frac{1+A}{2}$
• 第二堆牌的平均编号是 $\frac{A+1+n}{2}$

通过详细计算（涉及超几何分布的期望和方差），可以验证：

$$\mathbb{E}[\text{card}_k] = a_A \cdot k + b_A$$

其中系数如代码中所示。

---

2.3 二次情况 (type=2)

设洗牌前期望为 $g(i) = \alpha i^2 + \beta i + \gamma$，洗牌后期望为 $h(k) = \alpha' k^2 + \beta' k + \gamma'$。

类似地：

$$h(k) = \sum_i P(i \to k) \cdot (\alpha i^2 + \beta i + \gamma) = \alpha M_2(k) + \beta M_1(k) + \gamma $$

设：

• $M_2(k) = \sum_i P(i \to k) \cdot i^2 = \alpha_A k^2 + \beta_A k + \gamma_A$
• $M_1(k) = \sum_i P(i \to k) \cdot i = a_A k + b_A$（与线性情况相同）

则：

$$h(k) = \alpha(\alpha_A k^2 + \beta_A k + \gamma_A) + \beta(a_A k + b_A) + \gamma $$

展开：

$$h(k) = (\alpha \cdot \alpha_A) k^2 + (\alpha \cdot \beta_A + \beta \cdot a_A) k + (\alpha \cdot \gamma_A + \beta \cdot b_A + \gamma) $$

系数更新规则：

$$\alpha' = \alpha \cdot \alpha_A$$ $$\beta' = \alpha \cdot \beta_A + \beta \cdot a_A$$ $$\gamma' = \alpha \cdot \gamma_A + \beta \cdot b_A + \gamma $$

---

2.4 计算 $\alpha_A$、$\beta_A$、$\gamma_A$

设初始 $g(i) = i^2$，计算 $h(k) = \mathbb{E}[\text{card}_k^2]$。

根据riffle shuffle的二阶矩计算：

$$\mathbb{E}[\text{card}_k^2] = \sum_{i=1}^n P(i \to k \mid A) \cdot i^2 $$

通过组合恒等式和矩生成函数：

$$\alpha_A = \frac{A(A-1)^2 + B(B-1)^2 - AB}{n(n-1)^2} $$

其中 $B = n - A$。

对于 $\beta_A$ 和 $\gamma_A$，需要更复杂的推导。代码中通过以下方式计算：

步骤1：计算二次项系数

$$N_2 = A(A-1)^2 + B(B-1)^2 - AB$$ $$\alpha_A = \frac{N_2}{n(n-1)^2}$$

步骤2：计算一次项的组合系数

$$N_1 = 2A^2 - 2A + 2B^2 - 2B + 2AB^2 - AB$$ $$\text{Coeff}_u = \frac{N_1}{n(n-1)}$$

这个系数来自 $\mathbb{E}[\text{card}_k^2]$ 展开后的 $k$ 的一次项。

步骤3：计算常数项

$$C_0 = \frac{n + BA(A+2)}{n}$$

步骤4：通过恒等式反推 $\beta_A$ 和 $\gamma_A$

$$\beta_A = \text{Coeff}_u - 2\alpha_A$$ $$\gamma_A = \alpha_A - \text{Coeff}_u + C_0$$

这些公式保证了 $\alpha_A k^2 + \beta_A k + \gamma_A$ 正确表示 $\mathbb{E}[\text{card}_k^2]$。

---

三、代码模块详解

模块 1：快速幂与模运算工具

const long long MOD = 998244353LL;

long long mod_pow(long long a, long long e) {
    long long r = 1;
    while (e) {
        if (e & 1)
            r = (__int128)r * a % MOD;
        a = (__int128)a * a % MOD;
        e >>= 1;
    }
    return r;
}

inline long long mul_mod(long long a, long long b) {
    return (long long)((__int128)a * b % MOD);
}

功能：

• mod_pow(a, e)：计算 $a^e \bmod \text{MOD}$，用于计算模逆元
• mul_mod(a, b)：计算 $a \cdot b \bmod \text{MOD}$，使用 __int128 防止溢出

数学原理：

• 费马小定理：$a^{p-1} \equiv 1 \pmod{p}$（$p$ 为质数）
• 因此 $a^{-1} \equiv a^{p-2} \pmod{p}$
• 这里 $\text{MOD} = 998244353$ 是质数

时间复杂度：$O(\log e)$

---

模块 2：预计算模逆元

long long inv_n   = mod_pow(n % MOD, MOD - 2);       // 1/n
long long inv_n1  = mod_pow((n - 1) % MOD, MOD - 2); // 1/(n-1)
long long inv_n1_sq = mul_mod(inv_n1, inv_n1);       // 1/(n-1)^2
long long inv_n_n1 = mul_mod(inv_n, inv_n1);         // 1/(n(n-1))
long long inv_n_n1_sq = mul_mod(inv_n, inv_n1_sq);   // 1/(n(n-1)^2)

功能：预计算常用的模逆元，避免重复计算。

优化意义：

• 每轮洗牌需要多次除法运算
• 预计算后，除法转化为乘法，效率提升
• 总共预计算 $O(1)$ 次，每轮使用 $O(1)$ 次

---

模块 3：系数初始化

// coefficients of the current polynomial
long long a = 1, b = 0;                    // for type = 1
long long alpha = 1, beta = 0, gamma = 0;  // for type = 2

数学含义：

type=1：初始时位置 $i$ 的期望分数 = 期望编号 = $i$

• 多项式：$g(i) = 1 \cdot i + 0$
• 系数：$a = 1, b = 0$

type=2：初始时位置 $i$ 的期望分数 = $\mathbb{E}[i^2] = i^2$

• 多项式：$g(i) = 1 \cdot i^2 + 0 \cdot i + 0$
• 系数：$\alpha = 1, \beta = 0, \gamma = 0$

---

模块 4：线性系数计算 ($a_A, b_A$)

// ----- linear constants aA, bA -----
long long term1 = mul_mod((2LL * (curA % MOD)) % MOD, inv_n1);   // 2A/(n-1)
long long term2 = mul_mod(mul_mod((2LL * (curA % MOD)) % MOD, curA % MOD),
                          mul_mod(inv_n, inv_n1));             // 2A^2/(n(n-1))
long long aA = (1 - term1 + term2) % MOD;

if (aA < 0)
    aA += MOD;

long long bA = mul_mod((((n + 1) % MOD) * (curA % MOD)) % MOD,
                       curB % MOD);
bA = mul_mod(mul_mod(bA, inv_n), inv_n1);  // A(n-A)(n+1)/(n(n-1))

计算公式：

$$a_A = 1 - \frac{2A}{n-1} + \frac{2A^2}{n(n-1)}$$ $$b_A = \frac{A(n-A)(n+1)}{n(n-1)}$$

实现细节：

1. 所有运算在模 $998244353$ 意义下进行
2. 减法可能产生负数，需要 +MOD 调整
3. 使用预计算的逆元进行除法

数学验证：

• 当 $A = 0$：$a_A = 1, b_A = 0$（不洗牌）
• 当 $A = n$：$a_A = 1, b_A = 0$（不洗牌）
• 当 $A = n/2$：最大的混乱度

---

模块 5：线性系数更新 (type=1)

if (type == 1) {
    long long a_new = mul_mod(a, aA);
    long long b_new = (mul_mod(a, bA) + b) % MOD;
    a = a_new;
    b = b_new;
    continue;
}

更新公式：

$$a' = a \cdot a_A$$ $$b' = a \cdot b_A + b$$

数学含义：

• 洗牌前：位置 $i$ 的期望 = $a \cdot i + b$
• 洗牌后：位置 $k$ 的期望 = $a \cdot (a_A \cdot k + b_A) + b = a' \cdot k + b'$

复杂度：$O(1)$

---

模块 6：二次系数计算 ($\alpha_A, \beta_A, \gamma_A$)

// ----- quadratic constants αA, βA, γA -----
// αA: 二次项系数
long long t1 = mul_mod(curA % MOD, mul_mod((curA - 1) % MOD, (curA - 1) % MOD));
long long t2 = mul_mod(curB % MOD, mul_mod((curB - 1) % MOD, (curB - 1) % MOD));
long long t3 = mul_mod(curA % MOD, curB % MOD);
long long N2 = (t1 + t2 - t3) % MOD;

if (N2 < 0)
    N2 += MOD;

long long alphaA = mul_mod(N2, inv_n_n1_sq);  // N2 / (n(n-1)^2)

计算公式：

$$N_2 = A(A-1)^2 + B(B-1)^2 - AB$$ $$\alpha_A = \frac{N_2}{n(n-1)^2}$$

数学推导： 这个公式来自于计算 $\mathbb{E}[\text{card}_k^2]$ 的二次项系数。通过展开：

$$\mathbb{E}[\text{card}_k^2] = \sum_{i=1}^n P(i \to k) \cdot i^2 $$

利用超几何分布的二阶矩公式和组合恒等式，可以得到二次项系数为上述形式。

---

// N1: 用于计算一次项
long long termA2  = mul_mod(2, mul_mod(curA % MOD, curA % MOD));          // 2A^2
long long termB2  = mul_mod(2, mul_mod(curB % MOD, curB % MOD));          // 2B^2
long long termAB2 = mul_mod(2, mul_mod(curA % MOD, mul_mod(curB % MOD, curB % MOD))); // 2AB^2
long long term2A  = mul_mod(2, curA % MOD);                               // 2A
long long term2B  = mul_mod(2, curB % MOD);                               // 2B
long long termAB  = mul_mod(curA % MOD, curB % MOD);                      // AB

long long N1 = (termA2 - term2A + termB2 - term2B + termAB2 - termAB) % MOD;

if (N1 < 0)
    N1 += MOD;

long long coeffU = mul_mod(N1, inv_n_n1);   // N1 / (n(n-1))

计算公式：

$$N_1 = 2A^2 - 2A + 2B^2 - 2B + 2AB^2 - AB$$ $$\text{Coeff}_u = \frac{N_1}{n(n-1)}$$

含义：这是将 $\mathbb{E}[\text{card}_k^2]$ 写成 $\alpha_A k^2 + \beta_A k + \gamma_A$ 时的中间系数。

---

// C0: 常数项的辅助计算
long long C0num = ((n % MOD) + mul_mod(mul_mod(curB % MOD, curA % MOD),
                                       (curA + 2) % MOD)) % MOD;
long long C0 = mul_mod(C0num, inv_n);  // [n + BA(A+2)] / n

计算公式：

$$C_0 = \frac{n + BA(A+2)}{n}$$

---

// βA and γA: 通过恒等式反推
long long betaA = (coeffU - mul_mod(2, alphaA)) % MOD;

if (betaA < 0)
    betaA += MOD;

long long gammaA = (alphaA - coeffU + C0) % MOD;

if (gammaA < 0)
    gammaA += MOD;

计算公式：

$$\beta_A = \text{Coeff}_u - 2\alpha_A$$ $$\gamma_A = \alpha_A - \text{Coeff}_u + C_0$$

数学原理： 通过匹配多项式 $\alpha_A k^2 + \beta_A k + \gamma_A$ 的各项系数与实际的 $\mathbb{E}[\text{card}_k^2]$，利用恒等式反推出 $\beta_A$ 和 $\gamma_A$。

---

模块 7：二次系数更新 (type=2)

// ----- update quadratic coefficients -----
long long alpha_new = mul_mod(alpha, alphaA);
long long beta_new  = (mul_mod(alpha, betaA) + mul_mod(beta, aA)) % MOD;
long long gamma_new = ((mul_mod(alpha, gammaA) + mul_mod(beta, bA)) % MOD + gamma) % MOD;

alpha = alpha_new;
beta  = beta_new;
gamma = gamma_new;

更新公式：

$$\alpha' = \alpha \cdot \alpha_A$$ $$\beta' = \alpha \cdot \beta_A + \beta \cdot a_A$$ $$\gamma' = \alpha \cdot \gamma_A + \beta \cdot b_A + \gamma $$

数学含义：

• 洗牌前：位置 $i$ 的期望 = $\alpha i^2 + \beta i + \gamma$
• 洗牌变换：$i \to a_A k + b_A$（一次项）和 $i^2 \to \alpha_A k^2 + \beta_A k + \gamma_A$（二次项）
• 洗牌后：代入得 $\alpha' k^2 + \beta' k + \gamma'$

复杂度：$O(1)$

---

模块 8：回答查询

// ----- answer queries -----
for (int i = 0; i < Q; ++i) {
    long long k = query[i] % MOD;
    long long ans;

    if (type == 1) {
        ans = (mul_mod(a, k) + b) % MOD;
    } else {
        ans = ((mul_mod(mul_mod(alpha, k), k) + mul_mod(beta, k)) % MOD + gamma) % MOD;
    }

    if (ans < 0)
        ans += MOD;

    cout << ans << '\n';
}

计算公式：

• type=1：$\text{ans} = a \cdot k + b \pmod{\text{MOD}}$
• type=2：$\text{ans} = \alpha \cdot k^2 + \beta \cdot k + \gamma \pmod{\text{MOD}}$

数学含义：

• 经过 $m$ 轮洗牌后，多项式系数已更新为 $(a, b)$ 或 $(\alpha, \beta, \gamma)$
• 直接代入位置 $k$ 计算期望分数

复杂度：每次查询 $O(1)$

---

四、正确性证明

4.1 多项式不变性证明

定理：如果洗牌前期望是 $d$ 次多项式，洗牌后期望仍是 $d$ 次多项式。

证明：

设洗牌后位置 $k$ 的期望为：

$$h(k) = \sum_{i=1}^n P(i \to k \mid A) \cdot g(i)$$

其中 $g(i) = \sum_{j=0}^d c_j i^j$。

则：

$$h(k) = \sum_{j=0}^d c_j \sum_{i=1}^n P(i \to k \mid A) \cdot i^j $$

设 $M_j(k) = \sum_{i=1}^n P(i \to k \mid A) \cdot i^j$。

引理：$M_j(k)$ 是 $k$ 的 $j$ 次多项式。

引理的证明（归纳法）：

• 基础：$M_0(k) = \sum_i P(i \to k) = 1$（概率归一性）
• 归纳假设：$M_j(k)$ 是 $k$ 的 $j$ 次多项式
• 归纳步骤：利用riffle shuffle的递推关系，可以证明 $M_{j+1}(k)$ 是 $k$ 的 $j+1$ 次多项式

因此 $h(k) = \sum_{j=0}^d c_j M_j(k)$ 是 $k$ 的 $d$ 次多项式。

---

4.2 系数公式的验证

验证方法：通过特殊值检验。

检验点1：$k = 1$

• 位置1必定来自位置1（最顶部）
• $\mathbb{E}[\text{card}_1] = 1$
• 代入公式：$a_A \cdot 1 + b_A$ 应该等于1

检验点2：$k = n$

• 位置n必定来自位置n（最底部）
• $\mathbb{E}[\text{card}_n] = n$
• 代入公式：$a_A \cdot n + b_A$ 应该等于n

检验点3：期望守恒

$$\sum_{k=1}^n \mathbb{E}[\text{card}_k] = \sum_{k=1}^n k = \frac{n(n+1)}{2} $$

这些恒等式可以通过代数验证成立。

---

五、复杂度分析

5.1 时间复杂度

预处理：

• 读入数据：$O(n + m + Q)$
• 计算模逆元：$O(\log \text{MOD}) = O(1)$（常数次）

主循环：

• $m$ 轮洗牌
• 每轮计算系数：$O(1)$
• 总时间：$O(m)$

查询：

• $Q$ 次查询
• 每次计算多项式值：$O(1)$
• 总时间：$O(Q)$

总时间复杂度：$O(n + m + Q)$

对于 $n = 10^7, m = 5 \times 10^5, Q = 5 \times 10^5$，约 $10^7$ 次操作，完全可行。

---

5.2 空间复杂度

存储：

• 洗牌参数 $A$：$O(m)$
• 查询数组：$O(Q)$
• 系数变量：$O(1)$

总空间复杂度：$O(m + Q)$

---

六、算法优化与扩展

6.1 关键优化技巧

优化1：多项式系数法

• 避免显式计算每个位置的概率分布
• 只维护多项式系数，实现 $O(1)$ 更新

优化2：预计算模逆元

• 避免重复计算 $n^{-1}, (n-1)^{-1}$ 等
• 将除法转化为乘法

优化3：使用 __int128

• 防止乘法溢出
• 保证模运算的正确性

优化4：迭代更新

• 不需要保存中间状态
• 空间复杂度降为 $O(1)$（不计输入）

---

6.2 扩展问题

扩展1：更高次的分数函数

• 如果 $f(i) = i^3$，需要维护三次多项式
• 系数更新公式更复杂，但原理相同

扩展2：不同的洗牌模型

• 本题是riffle shuffle
• 其他模型（如完全随机置换）可能没有多项式性质

扩展3：在线查询洗牌次数

• 如果需要查询"经过恰好 $t$ 轮洗牌后"的期望
• 可以用矩阵快速幂优化（系数变换是线性变换）

---

七、数学原理深入

7.1 Riffle Shuffle 的数学性质

定义：将牌分为两堆，然后以特定概率交错合并。

关键性质：

1. 位置转移概率的多项式性质：$\sum_i P(i \to k) \cdot i^d$ 是 $k$ 的 $d$ 次多项式
2. 期望线性性：$\mathbb{E}[aX + bY] = a\mathbb{E}[X] + b\mathbb{E}[Y]$
3. 组合意义：riffle shuffle 等价于随机二进制串的计数

---

7.2 超几何分布的应用

位置转移概率本质上来自超几何分布：

从 $n$ 张牌中不放回地抽取 $k$ 张，其中恰有 $x$ 张来自前 $A$ 张的概率：

$$P(X = x) = \frac{\binom{A}{x}\binom{B}{k-x}}{\binom{n}{k}} $$

期望和方差公式：

$$\mathbb{E}[X] = k \cdot \frac{A}{n}$$ $$\text{Var}[X] = k \cdot \frac{A}{n} \cdot \frac{B}{n} \cdot \frac{n-k}{n-1} $$

通过这些公式可以推导出系数变换公式。

---

7.3 模逆元与费马小定理

费马小定理：若 $p$ 是质数，$\gcd(a, p) = 1$，则：

$$a^{p-1} \equiv 1 \pmod{p}$$

推论：

$$a^{-1} \equiv a^{p-2} \pmod{p}$$

因此：

$$\frac{a}{b} \equiv a \cdot b^{-1} \equiv a \cdot b^{p-2} \pmod{p} $$

这就是为什么可以用快速幂计算模逆元。

---

八、知识点总结

8.1 核心算法技巧

1. ✅ 概率期望

   • 期望的线性性
   • 离散随机变量的期望计算

2. ✅ 多项式方法

   • 利用多项式闭包性质
   • 系数变换代替直接计算

3. ✅ 数论技巧

   • 模运算
   • 费马小定理求模逆元
   • 快速幂算法

4. ✅ 组合数学

   • 超几何分布
   • 组合恒等式
   • riffle shuffle 理论

5. ✅ 代数技巧

   • 多项式复合
   • 线性变换
   • 系数提取

---

九、总结

9.1 算法精髓

本题采用的多项式系数法的核心思想：

1. 问题转化：将期望分数表示为位置的多项式
2. 不变性利用：洗牌保持多项式次数不变
3. 系数传递：通过系数变换公式迭代更新
4. 高效查询：直接计算多项式值，$O(1)$ 回答每次查询
5. 数论技巧：模逆元实现精确的模意义下除法