题目链接
考虑 \(k = n\) 的情况，从右往左扫每个灯 \(i\)，如果 \(i\) 是亮的就一定操作 \(i\)，因为后面没有灯可以控制它了；否则一定不操作。
回到原题，我们可以计算出需要操作的灯的数量 \(m\)。考虑 dp，设 \(f _ i\) 为亮着的灯的数量从 \(i\) 变成 \(i - 1\) 的期望次数，则 \(f _ i = 1 + \frac {n - i} n (f _ {i + 1} + f _ i)\)，含义为先操作 \(1\) 次，然后有 \(\frac {n - i} n\) 的概率变成 \(i + 1\)，期望需要 \(f _ {i + 1}\) 次才能变回 \(i\)，化为原来的状况。解得 \(f _ i = ((n - i) f _ {i + 1} + n) / i\) 可以递推，答案即为 \(\sum _ {i = k + 1} ^ m f _ {i}\)。
bonus：记 \(m ^ {\underline n} = m (m - 1) \cdots (m - n + 1)\)，则设 \(g _ i = n ^ {\underline {n - i + 1}} f _ i = n ^ {\underline {n - i}} ((n - i) f _ {i + 1} + n) = (n - i) g _ {i + 1} + n ^ {\underline {n - i}} \cdot n\)，可以规避掉求逆元。
时间复杂度 \(\text O (n \log n)\)。
#include<cstdio>
#include<vector>
#define N 100005
using namespace std;const int mod=100003;
int n,k,m,ans,a[N],g[N],fac[N];
vector<int> d[N];
int dc[N];
int main() {scanf("%d%d",&n,&k),fac[0]=1; for(int i=1;i<=n;i++) scanf("%d",&a[i]),fac[i]=1ll*fac[i-1]*i%mod;for(int i=1;i<=n;i++) for(int j=i;j<=n;j+=i) dc[j]++;for(int i=1;i<=n;i++) d[i].reserve(dc[i]);for(int i=1;i<=n;i++) for(int j=i;j<=n;j+=i) d[j].push_back(i);for(int i=n;i;i--) if(a[i]) {m++;for(auto j:d[i]) a[j]^=1;}if(m<=k) {return 0&printf("%d\n",1ll*m*fac[n]%mod);}int pr=g[n]=n;for(int i=n-1;i>k;i--) {g[i]=(1ll*g[i+1]*(n-i)+1ll*n*pr)%mod,pr=1ll*pr*i%mod;}for(int i=m;i>k;i--) {ans=(ans+1ll*g[i]*fac[i-1])%mod;}printf("%d\n",(ans+1ll*k*fac[n])%mod);return 0;
}