题面
Zeit und Raum trennen dich und mich.
时空将你我分开。
B 君在玩一个游戏，这个游戏由 \(n\) 个灯和 \(n\) 个开关组成，给定这 \(n\) 个灯的初始状态，下标为从 \(1\) 到 \(n\) 的正整数。
每个灯有两个状态亮和灭，我们用 \(1\) 来表示这个灯是亮的，用 \(0\) 表示这个灯是灭的，游戏的目标是使所有灯都灭掉。
但是当操作第 \(i\) 个开关时，所有编号为 \(i\) 的约数（包括 \(1\) 和 \(i\)）的灯的状态都会被改变，即从亮变成灭，或者是从灭变成亮。
B 君发现这个游戏很难，于是想到了这样的一个策略，每次等概率随机操作一个开关，直到所有灯都灭掉。
这个策略需要的操作次数很多，B 君想到这样的一个优化。如果当前局面，可以通过操作小于等于 \(k\) 个开关使所有灯都灭掉，那么他将不再随机，直接选择操作次数最小的操作方法（这个策略显然小于等于 \(k\) 步）操作这些开关。
B 君想知道按照这个策略（也就是先随机操作，最后小于等于 \(k\) 步，使用操作次数最小的操作方法）的操作次数的期望。
这个期望可能很大，但是 B 君发现这个期望乘以 \(n\) 的阶乘一定是整数，所以他只需要知道这个整数对 \(100003\) 取模之后的结果。
题解
真神题吧。
需要注意到，对于一个状态，哪些开关会被按是唯一的，考虑从最后一个灯开始枚举这个开关是否需要按，可以得到还需要按的开关个数。
然后接下来的 \(\text{trick}\) 和 CF1778D - Flexible String Revisit 一致。
套用一下，特判 \(k\) 个开关以下时不需要随机了即可。
参考代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int mod = 1e5 + 3;
int n, k, a[N];
ll dp[N], frac[N], inv[N];
vector<int> factors[N];
void init(int n)
{
for (int i = 1; i <= n; i ++ )
for (int j = i; j <= n; j += i)
factors[j].push_back(i);
inv[1] = frac[0] = 1;
for (int i = 1; i <= n; i ++ ) frac[i] = frac[i - 1] * i % mod;
for (int i = 2; i <= n; i ++ ) inv[i] = (mod - mod / i * inv[mod % i] % mod) % mod;
for (int i = n; i; i -- ) dp[i] = (dp[i + 1] * (n - i) % mod + n) * inv[i] % mod;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
init(n);
for (int i = 1; i <= n; i ++ ) cin >> a[i];
int res = 0;
for (int i = n; i; i -- )
{
if (!a[i]) continue;
res ++ ;
for (auto d : factors[i]) a[d] ^= 1;
}
ll ans = min(k, res);
for (int i = k + 1; i <= res; i ++ ) (ans += dp[i]) %= mod;
ans = ans * frac[n] % mod;
cout << ans << "\n";
return 0;
}