1. 问题重述

• 有 $n$ 个开关，初始全部关闭（状态为 $0$）。
• 目标状态 $s \in \{0,1\}^n$。
• 每一步随机按一个开关 $i$，概率为 $\frac{p_i}{\sum_{j=1}^n p_j}$，按下的开关状态翻转。
• 一旦状态等于 $s$，立即停止。
• 求期望按开关次数，对 $998244353$ 取模。

---

2. 状态表示与概率

设 $S_{\text{sum}} = \sum_{i=1}^n p_i$。

我们考虑所有 $2^n$ 个状态，但注意到：只有开关被按奇数次或偶数次是重要的。
定义 $x_i$ 表示第 $i$ 个开关被按过的次数模 $2$（$0$ 表示偶数次，$1$ 表示奇数次），那么当前状态就是 $(x_1, x_2, \dots, x_n)$。

初始状态：$(0,0,\dots,0)$。
目标状态：$s = (s_1, s_2, \dots, s_n)$。

---

3. 抽象为随机游走

我们可以把问题看作在一个 $n$ 维的 $\mathbb{F}_2^n$ 空间上的随机游走：

• 状态是向量 $x \in \{0,1\}^n$。
• 从 $0$ 向量出发。
• 每一步以概率 $\frac{p_i}{S_{\text{sum}}}$ 选择第 $i$ 个基向量 $e_i$（只有第 $i$ 位是 $1$），然后做异或：$x \to x \oplus e_i$。
• 到达状态 $s$ 时停止。

---

4. 期望步数公式（高赌徒破产问题）

这是一个 带吸收态的马尔可夫链，在 $\mathbb{F}_2^n$ 上，除了 $s$ 是吸收态外，其他状态都是瞬态。

设 $E_v$ 表示从状态 $v$ 出发到 $s$ 的期望步数。
显然 $E_s = 0$。

对于 $v \neq s$：

$$E_v = 1 + \sum_{i=1}^n \frac{p_i}{S_{\text{sum}}} E_{v \oplus e_i}. $$

这是一个线性方程组，有 $2^n$ 个变量，但 $n$ 可能很大，不能直接解。

---

5. 利用对称性化简

因为图是 $\mathbb{F}_2^n$ 上的 Cayley 图（以 $\{e_1,\dots,e_n\}$ 为生成元），具有平移对称性：
$E_v$ 只依赖于 $v$ 与 $s$ 的差异。

设 $d = v \oplus s$（在 $\mathbb{F}_2^n$ 中），则 $d=0$ 表示到达目标。
定义 $F_d = E_{d \oplus s}$，则 $F_0 = 0$。

对于 $d \neq 0$：

$$F_d = 1 + \sum_{i=1}^n \frac{p_i}{S_{\text{sum}}} F_{d \oplus e_i}. $$

---

6. 异或卷积视角与傅里叶变换

在 $\mathbb{F}_2^n$ 上，考虑函数 $F$ 满足：

$$F(d) = 1 + \sum_{i=1}^n \frac{p_i}{S_{\text{sum}}} F(d \oplus e_i), \quad F(0) = 0. $$

设 $\hat{F}(k) = \sum_{d \in \{0,1\}^n} (-1)^{k \cdot d} F(d)$ 是 $F$ 在 $\mathbb{F}_2^n$ 上的 Walsh-Hadamard 变换（二进制傅里叶变换）。

方程两边做 Walsh 变换。右边第一项 $1$ 的变换：

• $1$ 的 Walsh 变换：$\hat{1}(k) = \sum_d (-1)^{k\cdot d} \cdot 1 = 2^n \delta_{k,0}$（因为当 $k=0$ 时，和为 $2^n$；当 $k\neq 0$，$\sum_d (-1)^{k\cdot d} = 0$）。

右边第二项：

$$\sum_d (-1)^{k\cdot d} \sum_i \frac{p_i}{S_{\text{sum}}} F(d \oplus e_i) = \sum_i \frac{p_i}{S_{\text{sum}}} \sum_d (-1)^{k\cdot (d \oplus e_i)} F(d) \cdot (-1)^{k\cdot e_i}??? $$

更仔细地：令 $t = d \oplus e_i$，则 $d = t \oplus e_i$，$k\cdot d = k\cdot t + k\cdot e_i$（在 $\mathbb{F}_2$ 中加法是异或，但在实数里表现为 $(-1)^{k\cdot d} = (-1)^{k\cdot t} \cdot (-1)^{k\cdot e_i}$）。

因此：

$$\sum_d (-1)^{k\cdot d} F(d \oplus e_i) = \sum_t (-1)^{k\cdot (t \oplus e_i)} F(t) = (-1)^{k\cdot e_i} \sum_t (-1)^{k\cdot t} F(t) = (-1)^{k\cdot e_i} \hat{F}(k). $$

所以第二项的 Walsh 变换是：

$$\sum_i \frac{p_i}{S_{\text{sum}}} (-1)^{k\cdot e_i} \hat{F}(k) = \hat{F}(k) \cdot \frac{\sum_i p_i (-1)^{k_i}}{S_{\text{sum}}}. $$

记：

$$\lambda_k = \frac{\sum_{i=1}^n p_i (-1)^{k_i}}{S_{\text{sum}}}. $$

注意 $(-1)^{k_i} = 1$ 如果 $k_i=0$，$=-1$ 如果 $k_i=1$。

---

7. 变换后的方程

原方程：

$$F(d) = 1 + \sum_i \frac{p_i}{S_{\text{sum}}} F(d \oplus e_i), \quad F(0)=0. $$

Walsh 变换后（$k \neq 0$ 时 $\hat{1}(k) = 0$）：

$$\hat{F}(k) = 0 + \lambda_k \hat{F}(k), \quad k \neq 0. $$

所以：

$$\hat{F}(k) (1 - \lambda_k) = 0, \quad k \neq 0.$$

若 $1 - \lambda_k \neq 0$，则 $\hat{F}(k) = 0$。

但 $k=0$ 时：

$$\hat{F}(0) = \sum_d F(d) = 2^n \cdot \text{(平均F值)}. $$

$k=0$ 时的方程：

$$\hat{F}(0) = 2^n + \lambda_0 \hat{F}(0),$$

而 $\lambda_0 = \frac{\sum_i p_i}{S_{\text{sum}}} = 1$，所以 $0 = 2^n$，矛盾？说明需要更仔细处理边界。

---

8. 修正：吸收态的影响

我们定义的是 $F(d) = E_{d\oplus s}$，且 $F(0)=0$（吸收态）。
在 $d=0$ 时方程不成立（因为已经停止），所以方程只对 $d\neq 0$ 成立。

设 $G(d) = F(d)$ 对 $d\neq 0$，$G(0)=0$。
那么对 $d\neq 0$：

$$G(d) = 1 + \sum_i \frac{p_i}{S_{\text{sum}}} G(d \oplus e_i). $$

注意 $d\oplus e_i$ 可能等于 $0$（当 $d=e_i$ 且 $s$ 对应位？这里 $d$ 是差异，$d=e_i$ 时 $d\oplus e_i=0$，此时 $G(0)=0$）。

所以方程：

$$G(d) = 1 + \sum_i \frac{p_i}{S_{\text{sum}}} G(d \oplus e_i), \quad d\neq 0. $$

设 $h(d) = 1$ 若 $d\neq 0$，$h(0)=0$？不对，$1$ 是常数，对所有 $d\neq 0$ 都是 $1$，包括 $d=0$ 时方程不存在。

更标准做法：设对所有 $d$（包括 $0$）：

$$G(d) = 1_{d\neq 0} + \sum_i \frac{p_i}{S_{\text{sum}}} G(d \oplus e_i) - 1_{d=0} \cdot \infty??? $$

这样很乱。标准技巧是：设 $H(d) = G(d) - c$ 选择常数 $c$ 消去常数项。

---

9. 标准方法：设 $H(d) = E_{d\oplus s} - E_{s\oplus u}$ 等

更简单的已知结论（来自随机游走理论）：

对于图上的随机游走，从 $u$ 到 $v$ 的期望步数满足：

$$E_u = 1 + \sum_{w} P_{uw} E_w, \quad E_v=0.$$

对称图上可用电势法。在 $\mathbb{F}_2^n$ 上，从 $0$ 到 $s$ 的期望步数公式为：

$$E_0 = \frac{2^n}{ \sum_{k \neq 0} (1 - \lambda_k)^{-1} }? $$

其实更精确的已知结论（可查“随机游走超立方体期望时间”）：

对于按权重随机选择边异或的游走，从 $0$ 到 $s$ 的期望步数为：

$$E = \sum_{k \in \{0,1\}^n \setminus \{0\}} \frac{1}{1 - \lambda_k} \cdot \frac{1 - (-1)^{k\cdot s}}{2}. $$

---

10. 化简到本题

我们要求 $E_0$ 当 $s$ 任意。

已知结论（通过解线性系统+傅里叶变换）：

$$E_0 = \sum_{k \neq 0} \frac{1}{1 - \lambda_k} \cdot \frac{1 - (-1)^{k\cdot s}}{2}, $$

其中

$$\lambda_k = \frac{\sum_i p_i (-1)^{k_i}}{S_{\text{sum}}}. $$

---

11. 模运算实现

模 $998244353$，需要计算：

$$E_0 = \sum_{k \in \{0,1\}^n, k\neq 0} \frac{1 - (-1)^{k\cdot s}}{2} \cdot \left( 1 - \frac{\sum_i p_i (-1)^{k_i}}{S_{\text{sum}}} \right)^{-1}. $$

$(-1)^{k\cdot s}$ 在 $\mathbb{F}_2$ 中等于 $(-1)^{\sum_{i} k_i s_i}$。

我们枚举 $k$ 的 $2^n$ 种可能（$n$ 大时不可行），但 $\sum p_i \le 50000$ 提示我们用 DP 按 $p_i$ 的和来分组。

---

12. 优化计算

令 $T = S_{\text{sum}}$。

定义 $A_m = \sum_{k: \sum_i k_i p_i = m} (-1)^{k\cdot s}$，其中 $\sum_i k_i p_i$ 不对，应该是 $\sum_i p_i (-1)^{k_i} = \sum_{i: k_i=0} p_i - \sum_{i: k_i=1} p_i$。

设 $U = \sum_{i: k_i=0} p_i$，$V = \sum_{i: k_i=1} p_i$，则 $U+V = T$，且 $\sum_i p_i (-1)^{k_i} = U - V = T - 2V$。

所以 $\lambda_k = \frac{T - 2V}{T} = 1 - \frac{2V}{T}$。

那么 $1 - \lambda_k = \frac{2V}{T}$。

---

13. 重新写公式

$$E_0 = \sum_{k \neq 0} \frac{1 - (-1)^{k\cdot s}}{2} \cdot \frac{T}{2V_k}, $$

其中 $V_k = \sum_{i: k_i=1} p_i$。

注意 $k=0$ 时 $V=0$，分母为 $0$，排除。

枚举 $V$ 的值（$1 \le V \le T$），设 $C_V = \sum_{k: V_k = V} (1 - (-1)^{k\cdot s})/2$。

那么：

$$E_0 = T \sum_{V=1}^T \frac{C_V}{2V}.$$

---

14. 计算 $C_V$

$C_V = \frac12 \left( \sum_{k:V_k=V} 1 - \sum_{k:V_k=V} (-1)^{k\cdot s} \right)$。

第一部分：$f(V) = \#$ of $k$ with $V_k = V$，即选择一些开关使它们的 $p_i$ 和为 $V$ 的方案数（$k_i=1$ 表示选）。

第二部分：$g(V) = \sum_{k:V_k=V} (-1)^{k\cdot s}$。
注意 $(-1)^{k\cdot s} = \prod_{i: s_i=1} (-1)^{k_i} \cdot \prod_{i: s_i=0} 1$。
所以这相当于给 $s_i=1$ 的开关的 $p_i$ 带上权重 $-1$，$s_i=0$ 的开关权重 $1$，做生成函数卷积。

---

15. 生成函数

设 $F(x) = \prod_{i=1}^n (1 + x^{p_i})$，则 $f(V) = [x^V] F(x)$。

设 $G(x) = \prod_{i=1}^n (1 + \omega_i x^{p_i})$，其中 $\omega_i = -1$ 如果 $s_i=1$，否则 $1$。
则 $g(V) = [x^V] G(x)$。

那么 $C_V = \frac12 (f(V) - g(V))$。

---

16. 最终公式

$$E_0 = \frac{T}{2} \sum_{V=1}^T \frac{f(V) - g(V)}{V}. $$

其中 $T = \sum_{i=1}^n p_i$。

由于 $\sum p_i \le 50000$，我们可以用 DP 在 $O(n T)$ 时间内计算 $f(V)$ 和 $g(V)$。

---

17. 算法步骤

1. 读入 $n, s, p$。
2. 计算 $T = \sum p_i$。
3. DP 计算 $f[V]$：
   • $f[0] = 1$。
   • 对每个 $i$ 从 $T$ 到 $p_i$：$f[j] += f[j - p_i]$（模 $998244353$）。
4. DP 计算 $g[V]$：
   • $g[0] = 1$。
   • 对每个 $i$，如果 $s_i=1$，则 $g[j] -= g[j - p_i]$（模 $998244353$），否则 $g[j] += g[j - p_i]$。
5. 计算：$$E_0 = \frac{T}{2} \sum_{V=1}^T \frac{f[V] - g[V]}{V} \pmod{998244353}. $$这里除法 $1/V$ 用模逆元。

---

18. 模运算

模 $998244353$ 是质数，逆元用费马小定理。

---

19. 样例验证

样例 1：$n=2, s=[1,1], p=[1,1]$，$T=2$。

$f[0]=1, f[1]=2, f[2]=1$。
$g$：$s_i$ 全 $1$，所以 $g[0]=1, g[1]=-2, g[2]=1$。

$f-g$：$V=1: 2-(-2)=4$，$V=2: 1-1=0$。

$E_0 = \frac{2}{2} \cdot \frac{4}{1} = 4$，正确。

---

20. 最终答案

输出 $E_0 \bmod 998244353$。

---

最终公式：

$$\boxed{E_0 = \frac{T}{2} \sum_{V=1}^T \frac{f(V) - g(V)}{V}} $$

其中 $f(V)$ 是选 $p_i$ 和为 $V$ 的方案数，$g(V)$ 是选 $p_i$ 和为 $V$ 且 $s_i=1$ 的项带 $-1$ 权重的生成函数系数。