这题是个很好的题呀。我一开始能想到好像对于k=n的情况只要扫一遍就行了……但是我没有意识到这是个必要的环节。

就是我们如果从大到小扫一遍，每次遇到亮的灯就按一下，这个过程中按的灯数是必要的。(这个比较显然……其实是我也找不出步数更少的反例……)那么我们就可以DP了……

考虑从需要i+1步到i步，这个其实就是我们喜闻乐见的抛硬币期望的……propropro版……

可以想到\(dp[i] = \frac{i}{n} + \frac{n-i}{n}(dp[i] + dp[i+1] + 1)\)前面是直接摁到了需要的i个，后面是按错了，你就需要\(dp[i+1] + dp[i] + 1\)的步数过来。因为多按了一个就变成了i+1，回来以后还是i个就是\(dp[i]\)，而那一步是多按的。

化简后就是\(dp[i] = \frac{(n-1)dp[i+1]+n}{i}\)

最后比较一下一共有多少必要按键cnt。如果少于k的话答案就是cnt，否则就是\(k + \sum_{i=k+1}^{cnt}dp[i]\)，最后乘以\(n!\)即为答案。

#include
    
     #define rep(i,a,n) for(int i = a;i <= n;i++)#define per(i,n,a) for(int i = n;i >= a;i--)#define enter putchar('\n')#define pr pair
     
      #define mp make_pair#define fi first#define sc secondusing namespace std;typedef long long ll;const int M = 100005;const ll mod = 100003; ll read(){   ll ans = 0,op = 1;char ch = getchar();   while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();}   while(ch >='0' && ch <= '9') ans = ans * 10 + ch - '0',ch = getchar();   return ans * op;}ll inc(ll a,ll b){return (a+b) % mod;}ll mul(ll a,ll b){return a * b % mod;}ll qpow(ll a,ll b){   ll p = 1;   while(b)   {      if(b & 1) p = mul(p,a);      a = mul(a,a),b >>= 1;   }   return p;}ll n,k,a[M],cnt,dp[M],ans;int main(){   n = read(),k = read();   rep(i,1,n) a[i] = read();   per(i,n,1)   {      if(!a[i]) continue;      cnt++;      for(int j = 1;j * j <= i;j++)      {     if(!(i % j))     {        a[j] ^= 1;        if(j * j != i) a[i/j] ^= 1;     }      }   }   per(i,n,1) dp[i] = mul(inc(n,mul(n-i,dp[i+1])),qpow(i,mod-2));   if(cnt <= k) ans = cnt;   else   {      ans = k;      rep(i,k+1,cnt) ans = inc(ans,dp[i]);   }   rep(i,2,n) ans = mul(ans,i);   printf("%lld\n",ans);   return 0;}