题目大意：$n$ 个灯开关游戏，按 $i$ 后 $i$ 的约数都改变状态。给定初始状态，希望所有灯都灭掉。随机选择一个灯，如果当前最优策略下次数 $leq k$ 直接用最优策略。问期望步数乘上 $n!$ 对$100003$取模
题解：考虑从大到小按，显然如果当前这盏是亮的就按。可以证明这是最优的一种方法，并且初始状态与最优解的按下的灯的集合一一对应。
$f_i$ 表示在最有情况下还有 $i$ 步可以结束的期望步数。
$$f_i=frac{i}{n}cdot f_{i-1}+frac{n-i}{n}cdot f_{i+1}+1$$
但是如果 $k=0$时 就无法计算。
所以差分 $f$，设 $g$ 表示从 $i$ 步到 $i-1$ 步期望步数。
$$egin{align*}
g_i&=frac{i}{n}+frac{n-i}{n}cdot (g_{i+1}+g_i+1)\
&=1+frac{(n-i)(g_{i+1}+g_i)}{n}\
&=1+frac{ncdot g_{i+1}+ncdot g_{i}-i cdot g_{i+1}-icdot g_i}{n}
end{align*}$$
左右同乘以$n$
$$ncdot g_i=n+ncdot g_{i+1}+ncdot g_i-icdot g_{i+1}-icdot g_i$$
$$icdot g_i=n+ncdot g_{i+1}-icdot g_{i+1}$$
$$ herefore g_i=frac{n+ncdot g_{i+1}-icdot g_{i+1}}{i}（g_n=1,g_{ileq k}=1）$$
卡点：1.最后一不小心答案加了$k$
C++ Code：
#include <cstdio>
#include <cmath>
#define maxn 100010
#define mod 100003
using namespace std;
int n, k, a[maxn], g[maxn];
int inv[maxn], N;
int cnt, ans;
signed main() {
scanf("%d%d", &n, &k);
inv[0] = inv[1] = N = 1;
for (int i = 2; i <= n; i++) {
inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
N = 1ll * N * i % mod;
}
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = n; i; i--) {
if (a[i]) {
cnt++;
int t = sqrt(i);
for (int j = 1; j <= t; j++) {
if (i % j == 0) {
a[j] ^= 1;
if (j * j != i) a[i / j] ^= 1;
}
}
}
}
if (cnt <= k) {
printf("%d
", 1ll * cnt * N % mod);
return 0;
}
g[n] = 1;
for (int i = n - 1; i; i--) {
if (i > k) g[i] = (n + 1ll * (n - i) * g[i + 1]) % mod * inv[i] % mod;
else g[i] = 1;
}
for (int i = 1; i <= cnt; i++) ans = (ans + g[i]) % mod;
printf("%d
", 1ll * ans * N % mod);
return 0;
}