题意理解

我们有一个 $n$ 维系统，每个维度 $i$ 有一个模数 $l_i$ 和一个单位根 $d_i$。系统从全零状态开始，每次随机选择一个维度 $i$ 将其值加 $1 \bmod l_i$，并记录当前状态。当系统回到全零状态时游戏结束，求记录的不同状态数的期望。

核心思路

关键观察 1：马尔可夫链与生成函数

这是一个在群 $\mathbb{Z}_{l_1} \times \mathbb{Z}_{l_2} \times \cdots \times \mathbb{Z}_{l_n}$ 上的随机游走问题。

设 $p_i$ 是选择维度 $i$ 的概率，$T$ 是首次回到全零状态的时间，我们要求的是从开始到时间 $T$ 访问的不同状态数的期望。

关键观察 2：单位根的性质

题目给出的 $d_i$ 满足：

• $d_i^{l_i} \equiv 1 \pmod{mod}$
• 对于 $t < l_i$，$d_i^t \not\equiv 1 \pmod{mod}$
• $\sum p_i d_i^{x_i} \equiv 1$ 当且仅当所有 $x_i = 0$

这意味着 $\{d_i^{x_i}\}$ 构成了特征标群，可以用于傅里叶分析。

关键观察 3：访问状态的生成函数

设 $f(S)$ 表示状态 $S$ 被访问的次数的期望，那么不同状态数的期望就是 $\sum_S [f(S) > 0]$ 的期望。

通过线性性，这等于 $\sum_S \mathbb{P}[\text{状态}S\text{被访问}]$。

算法框架

方法一：容斥原理与莫比乌斯反演

定义在群 $G = \mathbb{Z}_{l_1} \times \cdots \times \mathbb{Z}_{l_n}$ 上的随机游走。

根据 Burnside 引理或莫比乌斯反演，不同状态数的期望可以表示为：

$$E = \sum_{g \in G} \frac{1}{|G|} \sum_{\chi} \chi(g) \cdot [\text{某种生成函数}] $$

其中 $\chi$ 是 $G$ 的特征标。

方法二：生成函数与留数定理

定义生成函数：

$$F(z) = \prod_{i=1}^n \frac{1}{1 - p_i z^{l_i}}$$

这个生成函数计数的是所有路径，但我们需要的是首次回归前的路径。

通过循环引理或首达时间分析，期望不同状态数可以表示为：

$$E = \frac{1}{1 - \prod p_i^{l_i}} \sum_{S \neq 0} [\text{访问}S\text{的概率}] $$

方法三：特征标方法

利用题目给出的 $d_i$，定义特征标：

对于状态 $(x_1, \ldots, x_n)$，其特征值为 $\prod_{i=1}^n d_i^{x_i}$。

那么访问状态 $S$ 的概率与特征值的某种组合有关。

具体地，期望不同状态数为：

$$E = \sum_{(a_1,\ldots,a_n) \neq (0,\ldots,0)} \frac{1}{1 - \sum p_i d_i^{a_i}} $$

其中 $0 \leq a_i < l_i$。

具体推导

概率母函数方法

设 $u_t$ 是时刻 $t$ 首次回到全零状态的概率，$f_t$ 是时刻 $t$ 访问某个新状态的概率。

通过概率母函数的分析，可以得到：

$$E[\text{不同状态数}] = \sum_{t \geq 0} f_t = \frac{1}{u_\infty} $$

其中 $u_\infty$ 是最终回到全零状态的概率。

单位根过滤

利用单位根的性质，对于非全零状态 $(a_1, \ldots, a_n)$，有：

$$\sum_{k=0}^{l_i-1} d_i^{a_i k} = 0$$

这允许我们分离出全零状态的贡献。

最终答案的表达式为：

$$E = \frac{1}{\prod l_i} \sum_{(a_1,\ldots,a_n)} \frac{1}{1 - \sum p_i d_i^{a_i}} $$

其中求和遍及所有 $(a_1, \ldots, a_n)$ 满足 $0 \leq a_i < l_i$。

复杂度分析

直接计算

直接计算上述求和需要 $O(\prod l_i) = O(m)$ 时间，对于 $m \leq 5 \times 10^5$ 是可接受的。

利用卷积结构

注意到求和式具有乘积形式：

$$\sum_{a_1=0}^{l_1-1} \cdots \sum_{a_n=0}^{l_n-1} \frac{1}{1 - \sum p_i d_i^{a_i}} $$

这可以通过分治FFT或生成函数方法在 $O(m \log m)$ 时间内计算。

实现细节

模运算处理

• $mod$ 是质数，可以使用模逆元
• 需要计算 $\frac{1}{1 - x} \bmod mod$，当 $x \equiv 1$ 时需要特殊处理

单位根的使用

题目保证 $d_i$ 是 $l_i$ 次本原单位根，这确保了单位根过滤的正确性。

数值稳定性

由于涉及大量分数运算，需要注意模运算的数值稳定性。

特殊情况

$n = 1$ 的情况

系统退化为 $\mathbb{Z}_{l_1}$ 上的随机游走，答案是调和数的某种变形。

$l_i = 2$ 的情况

此时 $d_i = -1$，系统具有对称性，可以简化计算。

小 $m$ 的情况

当 $m$ 较小时可以直接枚举所有状态。

总结

本题的核心在于：

1. 代数结构：理解群上的随机游走和特征标理论
2. 生成函数：使用概率母函数分析马尔可夫链
3. 单位根技巧：利用题目给出的特殊性质进行简化
4. 组合计数：将期望问题转化为组合求和问题

这是一个典型的概率+代数+组合的综合问题，需要选手具备多领域的数学知识才能解决。题目通过精心设计的条件（单位根性质）为解题提供了关键线索。