嗯……概率期望这东西太神了……
先考虑一下最佳方案，肯定是从大到小亮的就灭（这个仔细想一想应该就能发现）
那么直接一遍枚举就能$O(nlogn)$把这个东西给搞出来
然后考虑期望dp，设$f[i]$表示从$i$个正确选项中选择一个正确的变为$i-1$个的期望次数
那么$$f[i]=frac{i}{n}+(1-frac{i}{n})*(1+f[i+1]+f[i])$$
其中$frac{i}{n}$表示一次就选了正确的选项，$(1-frac{i}{n})$表示按错了，那么会增加一个正确选项，然后这个时候要按回去次数是$(1+f[i+1]+f[i])$，然后再加上按错的一次
那么移项可得$$f[i]=1+frac{(n-i)*(f[i]+1)+1}{n}$$
然后只要从后往前递推就可以了
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<vector> 6 using namespace std; 7 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 8 char buf[1<<21],*p1=buf,*p2=buf; 9 inline int read(){ 10 #define num ch-'0' 11 char ch;bool flag=0;int res; 12 while(!isdigit(ch=getc())) 13 (ch=='-')&&(flag=true); 14 for(res=num;isdigit(ch=getc());res=res*10+num); 15 (flag)&&(res=-res); 16 #undef num 17 return res; 18 } 19 const int N=100005,mod=100003; 20 int b[N];vector<int> g[N]; 21 int f[N],inv[N],n,k; 22 void solve(){ 23 int ans=0,tp=0; 24 for(int i=1;i<=n;++i) 25 for(int j=i;j<=n;j+=i) 26 g[j].push_back(i); 27 for(int i=n;i;--i) 28 if(b[i]){ 29 ++tp; 30 for(int j=0,s=g[i].size();j<s;++j) b[g[i][j]]^=1; 31 } 32 if(tp<=k) ans=tp; 33 else{ 34 f[n]=1; 35 for(int i=n-1;i;--i) f[i]=(1ll+1ll*(n-i)*(f[i+1]+1)*inv[i])%mod; 36 for(int i=tp;i>k;--i) (ans+=f[i])%=mod; 37 (ans+=k)%=mod; 38 } 39 for(int i=1;i<=n;++i) ans=1ll*ans*i%mod; 40 printf("%d ",ans); 41 } 42 int main(){ 43 // freopen("testdata.in","r",stdin); 44 n=read(),k=read(); 45 for(int i=1;i<=n;++i) b[i]=read(); 46 inv[1]=1; 47 for(int i=2;i<=n;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod; 48 solve(); 49 return 0; 50 }