有N盏灯，给定了初始状态。N个开关，第i个开关可以同时改变它的约数的开、关状态。现在给定一个k。若对于当前状态，最快可以在k步内使所有灯关闭，那么就按照最少操作数进行操作，否则随机选择开关。求步数的期望乘n!模100003的值。
N≤100000
首先考虑如何对于一个状态求最小步数。 由于编号小的开关不会影响到后面的灯，所以应该按编号从大到小决策。对于当前枚举到的灯i，如果它是开着的，那么必须使用开关i。。所以可以很快求出对于初始状态的步数。 假设这个步数为m。如果m≤k，就可以直接输出答案了。 如果m>k，那么还需要求期望值。容易发现，选择任意一个开关，最小步数会加1或减1，而且如果选择的是对于当前状态最小步数的方案中选择的开关，最小步数必然减1，否则加1。 那么就可以设概率DP了。 设f[i]表示从最小步数为i到最小步数为i-1的期望步数。 易得 f[i]=iN+(1−iN)(f[i+1]+1+f[i]) ，边界为f[N]=1 移项，然后拆掉右边的f[]，可得： f[i]=N∑Nj=i(N−i)!(i−1)!(N−j)!j! 最终答案要乘上N!，代入得： f[i]=N(N−i)!(i−1)!∑Nj=iCjN 可以预处理阶乘和组合数，然后O(1)算答案。 最终答案就是 ∑mi=k+1f[i] 了
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N=100005,mo=100003; typedef long long LL; int n,Fac[N],C[N],m,k,bz[N],Inv[N],ans; char c; int read() { int x=0,sig=1; for (c=getchar();c<'0' || c>'9';c=getchar()) if (c=='-') sig=-1; for (;c>='0' && c<='9';c=getchar()) x=x*10+c-48; return x*sig; } int main() { n=read(); k=read(); for (int i=1;i<=n;i++) bz[i]=read(); for (int i=n;i;i--) if (bz[i]) { m++; for (int j=1;j*j<=i;j++) if (i%j==0) { bz[j]^=1; if (i/j>j) bz[i/j]^=1; } } Fac[0]=Fac[1]=Inv[1]=1; for (int i=2;i<=n;i++) { Fac[i]=(LL)Fac[i-1]*i%mo; Inv[i]=(LL)Inv[mo%i]*(mo-mo/i)%mo; } if (k>=m) { printf("%d\n",(LL)Fac[n]*m%mo); return 0; } C[0]=1; for (int i=0;i<n;i++) C[i+1]=(LL)C[i]*(n-i)%mo*Inv[i+1]%mo; for (int i=1;i<=n;i++) C[i]=(C[i]+C[i-1])%mo; for (int i=k+1;i<=m;i++) ans=(ans+(LL)Fac[n-i]*Fac[i-1]%mo*(C[n]-C[i-1]))%mo; if (ans<0) ans+=mo; ans=(LL)ans*n%mo; ans=(ans+(LL)Fac[n]*k)%mo; printf("%d\n",ans); return 0; }