Luogu

LOJ

分析

首先可以发现，$i$ 只能被 $\geq i$ 的开关操作掉。从而我们只需要从大到小模拟一遍，如果 $i$ 亮着就操作 $i$ 开关，就可以算出最小需要操作的次数 $c$ 了。这样子就可以拿到 $50$ 分（实际上有 80 分）。

冷静分析一下可以发现，达到目标所需要按的开关组合是唯一确定的。我们把这些开关叫做正确的。

考虑一个 DP。设 $dp_i$ 表示从剩余 $i$ 个正确的开关到剩下 $i-1$ 个正确的开关的期望次数。转移时考虑按到正确的开关和没有按到正确的开关的两种情况，可以得到
$$
dp_i=\frac{i}{n}+\frac{n-i}{n}(dp_i+dp_{i+1}+1)
$$
随便推一下式子可以得到
$$
dp_i=\frac{(n-i)dp_{i+1}+n}{i}
$$
算答案时分类讨论一下：如果 $c\leq k$，说明不会随机操作，答案即为 $c\times n!$；否则，我们需要从 $c$ 个正确开关削到 $k$ 个正确开关，故答案为 $(k+\sum_{i=k+1}^{c}dp_i)n!$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int mod=100003;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}
int inv(int x) { return qpow(x,mod-2); }
int fac(int x) { int s=1;
    for (int i=1;i<=x;++i) s=1ll*s*i%mod;
    return s; 
}

int n,k,a[N],dp[N];
vector<int> d[N];

int main() {
    n=read(),k=read();
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=n;++i)
        for (int j=i;j<=n;j+=i) d[j].emplace_back(i);
    int mincnt=0;
    for (int i=n;i;--i)
        if (a[i]) { ++mincnt; for (int j:d[i]) a[j]^=1; }
    if (mincnt<=k) { printf("%d\n",1ll*mincnt*fac(n)%mod); return 0; }
    dp[n]=1;
    for (int i=n-1;i>k;--i)
        dp[i]=(1ll*(n-i)*dp[i+1]+n)%mod*inv(i)%mod;
    int ans=k;
    for (int i=k+1;i<=mincnt;++i) ans=(ans+dp[i])%mod;
    printf("%d\n",1ll*ans*fac(n)%mod);
    return 0;
}