Informatik verbindet dich und mich.
信息将你我连结。
Zeit und Raum trennen dich und mich.
时空将你我分开。
相逢是问侯
分手是祝愿
性质 \(1\)：最优策略下，每个开关只会被操作至多 \(1\) 次。
证明 \(1\)：一个开关操作 \(2\) 次等效于操作 \(0\) 次。
性质 \(2\)：一定可以使所有灯都灭掉。
证明 \(2\)：考虑构造性的做法，从大到小找到所有亮着的灯，操作对应的开关即可。
性质 \(3\)：最优策略下存在唯一的操作方法。
证明 \(3\)：局面和操作的方案数都是 \(2^n\)，所有局面和操作方案构成双射。
性质 \(4\)：所有开关均不能表示为其他开关的线性组合。
证明 \(4\)：若可以，则一个局面对应多个操作方案。
我们可以利用性质 \(2\) 求出初始局面的最小操作次数 \(m\)。
由性质 \(3\)，我们可以求出需要操作的开关编号，而这是唯一的。
不妨求出序列 \(S\)，若 \(S_i=0\) 则开关 \(i\) 不需要操作，若 \(S_i=1\) 则开关 \(i\) 需要操作。
一次操作相当于随机选择一个下标 \(i\)，并反转 \(S_i\)。
同时，当 \(S\) 中 \(1\) 的个数不超过 \(k\) 时，即当前需要操作的次数 \(\leq k\)，直接结束即可。
此时问题就只和 \(S\) 中 \(1\) 的个数有关了。
我们令 \(f_i\) 表示 \(S\) 中 \(1\) 的个数为 \(i\) 时，需要操作的次数期望。
对于 \(0 \leq i \leq k\)，显然有 \(f_i = i\)。
对于 \(k < i < n\)，显然有 \(f_i = \dfrac{i}{n} \times f_{i-1} + \dfrac{n-i}{n} \times f_{i+1} + 1\)。
对于 \(i = n\)，显然有 \(f_i = f_{i-1} + 1\)。
考虑令 \(f_n = x\)，容易据此表示出所有 \(f_i\)。
接下来，我们考虑令 \(i = k + 1\)，由 \(f_i = \dfrac{i}{n} \times f_{i-1} + \dfrac{n-i}{n} \times f_{i+1} + 1\) 得 \(f_{k+1} = \dfrac{k+1}{n} \times k + \dfrac{n-k-1}{n} \times f_{k+2} + 1\)，容易据此解出 \(x\)。
注意加一点特判，然后就能过了，复杂度大概可以做到 \(O(n \log n)\)。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const long long mod=100003;
long long inv(long long num){long long pre=mod-2,ans=1;while(pre){if(pre&1) ans=ans*num%mod;num=num*num%mod;pre>>=1;}return ans;
}
int n,k;
vector<int> G[100010];
long long fact[100010];
void init(){fact[0]=1;for(int i=1;i<=n;i++){fact[i]=fact[i-1]*i%mod;for(int j=i;j<=n;j+=i){G[j].push_back(i);}}
}
int op[100010];
long long k_x[100010],b_x[100010];
int main(){scanf("%d %d",&n,&k);init();for(int i=1;i<=n;i++){scanf("%d",&op[i]);}int cnt=0;for(int i=n;i>=1;i--){if(op[i]==1){cnt++;for(int j=0;j<G[i].size();j++){op[G[i][j]]^=1;}}}if(cnt<=k || k==n-1){printf("%lld",cnt*fact[n]%mod);return 0;}k_x[n]=1;b_x[n]=0;k_x[n-1]=1;b_x[n-1]=mod-1;for(int i=n-1;i>=k+2;i--){long long pre_k=k_x[i],pre_b=b_x[i]-1;long long t_1=i*inv(n)%mod,t_2=(n-i)*inv(n)%mod;pre_k-=t_2*k_x[i+1]%mod;pre_k=(pre_k%mod+mod)%mod;pre_b-=t_2*b_x[i+1]%mod;pre_b=(pre_b%mod+mod)%mod;k_x[i-1]=pre_k*inv(t_1)%mod;b_x[i-1]=pre_b*inv(t_1)%mod;}long long pre_k=k_x[k+1],pre_b=-b_x[k+1]+1;long long t_1=(k+1)*inv(n)%mod,t_2=(n-k-1)*inv(n)%mod;pre_b+=t_1*k%mod;pre_b=(pre_b%mod+mod)%mod;pre_k-=t_2*k_x[k+2]%mod;pre_k=(pre_k%mod+mod)%mod;pre_b+=t_2*b_x[k+2]%mod;pre_b=(pre_b%mod+mod)%mod;long long x=pre_b*inv(pre_k)%mod;printf("%lld",(k_x[cnt]*x%mod+b_x[cnt])%mod*fact[n]%mod);return 0;
}