小清新 dp 题，纪念自己的 700 ac （
一个点只有两个状态开和不开，且按两下相当于没按，我们可以从大到小有亮的就按一下，如果我们按到了不需要按的键，就需要再按一下使他变回来。
设 \(f_i\) 表示 \(i\) 个正确选择变为 \(i-1\) 个的期望操作次数。
则有 \(\dfrac{i}{n}\) 概率按到需要按的灯，有 \(\dfrac{n - i}{n}\) 概率按到不需要按的灯。
\(f_i = \dfrac{i}{n} + (1 - \dfrac{i}{n}) \cdot (1 + f_{i+1} + f_i)\)
化简：
\(f_i = \dfrac{i}{n} + \dfrac{(n-i)\cdot f_{i+1}}{i}\)
我们计算必须要按的按键次数 \(cnt\)，若 \(cnt < k\) 显然答案就是 \(cnt\)，否则答案就是 \(\sum^{i\leq cnt}_{i=k+1}{f_i}\)，加上剩下 \(k\) 的期望。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int _ = 1e5 + 10, mod = 1e5 + 3;
int n, k; int a[_];
int inv[_], f[_], ans, cnt;
vector< int > g[_];
signed main() {
cin >> n >> k;
for(int i = 1; i <= n; ++i)
cin >> a[i];
inv[1] = 1;
for(int i = 2; i <= n; ++i)
inv[i] = ((mod - mod / i) * inv[mod % i] % mod) % mod;
for(int i = 1; i <= n; ++i)
for(int j = i; j <= n; j += i)
g[j].push_back(i);
for(int i = n; i >= 1; --i)
if(a[i]) {
for(int j = 0; j < g[i].size(); ++j) a[g[i][j]] ^= 1;
cnt++;
}
f[n] = 1;
for(int i = n - 1; i > k; --i)
f[i] = (n + (n - i) * f[i + 1]) * inv[i] % mod;
for(int i = k; i >= 1; --i) f[i] = 1;
for(int i = 1; i <= cnt; ++i) ans = (ans + f[i]) % mod;
for(int i = 1; i <= n; ++i) ans = (ans * i) % mod;
cout << ans << endl;
return 0;
}