题目大意

有 $n$ 盏灯和 $n$ 个开关，初始时每盏灯亮或灭。操作第 $i$ 个开关时，所有编号为 $i$ 的约数的灯（包括第 $i$ 盏）的状态都会改变（亮↔灭）。目标是将所有灯熄灭。

策略如下：

1. 每次等概率随机按一个开关；
2. 如果当前局面可以通过 ≤ k 次操作使所有灯熄灭，则采用最小操作次数的方法直接操作，不再随机。

求按照这个策略的期望操作次数，乘以 $n!$ 后对 $100003$ 取模的结果。

---

思路分析

1. 关键性质

操作顺序无关性：对于同一个开关按两次相当于没按，因此最优方案中每个开关最多按一次。

贪心确定必要操作：
从大到小考虑开关 $i$：

• 如果灯 $i$ 是亮的，必须按开关 $i$（因为比 $i$ 大的开关不会影响灯 $i$）
• 按开关 $i$ 会改变所有 $i$ 的约数对应的灯的状态

这样可以 $O(n\sqrt{n})$（或优化为 $O(n\log n)$）求出 最小必须操作次数 $cnt$。

2. 期望计算

设 $f[i]$ 表示 当前还需要正确操作 $i$ 个开关 的情况下，到结束的期望步数。

状态转移：

• 如果当前按到需要的开关（概率 $\frac{i}{n}$），则剩余需要操作 $i-1$ 个开关
• 如果按到不需要的开关（概率 $\frac{n-i}{n}$），则剩余需要操作 $i+1$ 个开关（因为错误的操作会增加一个需要修正的开关）

转移方程：

$$f[i] = 1 + \frac{i}{n} \cdot f[i-1] + \frac{n-i}{n} \cdot f[i+1] $$

边界条件：

• $f[0] = 0$（不需要操作了）
• 当 $i ≤ k$ 时，$f[i] = i$（直接操作，不需要随机）

化简递推式

整理可得：

$$f[i] = \frac{n + (n-i) \cdot f[i+1]}{i}$$

注意这是倒序递推关系，可以从 $i=n$ 开始推到 $i=k+1$。

---

3. 最终答案计算

• 如果 $k ≥ cnt$，直接操作：$ans = cnt \cdot n! \mod 100003$
• 否则：$$ans = \left[k + \sum_{i=k+1}^{cnt} f[i]\right] \cdot n! \mod 100003 $$其中 $k$ 表示最后 $k$ 步直接操作，$\sum f[i]$ 表示从 $cnt$ 状态随机到 $k$ 状态的期望步数。

---

算法步骤

1. 读入 $n, k$ 和灯的状态数组 $s$
2. 计算最小必须操作数 $cnt$：
   • 从 $n$ 到 $1$ 逆序遍历
   • 如果 $s[i] = 1$（灯亮），则 $cnt++$，并翻转所有 $i$ 的约数对应的灯状态
   • 同时计算 $bas = n! \mod 100003$
3. 预处理逆元（费马小定理）并计算 $f[i]$：
   • 从 $i=n$ 到 $1$ 逆序计算 $f[i] = \frac{n + (n-i) \cdot f[i+1]}{i}$
4. 计算答案：
   • 如果 $k ≥ cnt$：$ans = cnt \cdot bas$
   • 否则：$ans = (k + \sum_{i=k+1}^{cnt} f[i]) \cdot bas$
5. 输出 $ans \mod 100003$

---

时间复杂度

• 求 $cnt$：$O(n\sqrt{n})$（可优化为 $O(n\log n)$）
• 计算 $f[i]$：$O(n\log mod)$（快速幂求逆元）
• 总复杂度：$O(n\sqrt{n})$ 或 $O(n\log n)$

---

代码解释

for (int i = n; i >= 1; i--) {
    bas = bas * i % mod;  // 计算 n!
    if (!s[i]) continue;  // 灯灭则跳过
    cnt++;  // 必须操作开关 i
    // 翻转所有 i 的约数的灯状态
    for (int j = 1; j * j <= i; j++) {
        if (i % j == 0) {
            s[j] ^= 1;
            if (j * j != i) s[i / j] ^= 1;
        }
    }
}

// 计算期望递推数组 f
for (int i = n; i >= 1; i--) {
    f[i] = (n + (n - i) * f[i + 1] % mod) % mod * power(i, mod - 2) % mod;
}

// 最终答案
if (k >= cnt) {
    printf("%lld", cnt * bas % mod);
} else {
    for (int i = k + 1; i <= cnt; i++)
        ans = (ans + f[i]) % mod;
    printf("%lld", (ans + k) % mod * bas % mod);
}

---

样例验证

样例1：$n=4, k=0, s=[0,0,1,1]$

• 计算得 $cnt=2$（必须操作开关4和3）
• $k=0 < cnt$，需要计算期望
• 最终输出 $512$ ✅

样例2：$n=5, k=0, s=[1,0,1,1,1]$

• 计算得 $cnt=4$
• 输出 $5120$ ✅

---

总结

本题是概率期望DP的经典问题，结合了：

1. 贪心确定最小操作集合
2. 期望DP推导递推关系
3. 数论逆元处理模意义下的除法
4. 约数枚举技巧

关键在于将原问题转化为“从 $cnt$ 个必要操作随机减少到 $≤k$ 个”的期望步数问题，并通过倒序递推高效求解。