一看期望就害怕.

首先这个操作只能影响到比自己小的位置, 考虑一个最大的位置, 那么当前要翻就必须翻, 我们从大到小查一遍, 就知道要按几个灯了. 这个时候按灯的顺序就不重要了, 我们可以抽象成需要按$i$个灯的期望步数.

直接算会GG, 我们将期望差分为按$i$个灯转移到按$i-1$个灯的期望步数, 那么有转移:

$E_i = \frac{i}{n} + (1-\frac{i}{n})(E_i + E_{i+1}+1)$. 前一部分是按对了, 后一部分是没按对, 这样就多了一个需要按的, 还需要按回来.

可以递推. 然后对于小于$k$的时候就不推了, 直接算答案.

最后把答案乘上$N!$. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define mod 100003

using namespace std;
typedef long long ll;

const int maxn = 100005;

int n, k, a[maxn], cor;
ll E[maxn], inv[maxn];
vector<int> vec[maxn];

int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    for (int j = i; j <= n; j += i)
      vec[j].push_back(i);
  }
  for (int i = 1; i <= n; ++i)
    scanf("%d", &a[i]);
  inv[1] = 1;
  for (int i = 2; i <= n; ++i)
    inv[i] = inv[mod % i] * (mod - mod / i) % mod;
  for (int i = n; i > k; --i) {
    E[i] = (n + (n - i) * E[i + 1] % mod) % mod * inv[i] % mod;
  }
  for (int i = k; i; --i) E[i] = 1;
  for (int i = n; i; --i) {
    if (a[i]) {
      for (int j = 0; j < (int)vec[i].size(); ++j)
        a[vec[i][j]] ^= 1;
      cor++;
    }
  }
  ll ans = 0;
  for (int i = 1; i <= cor; ++i)
    ans = (ans + E[i]) % mod;
  for (int i = 1; i <= n; ++i)
    ans = (ans * i) % mod;
  printf("%lld\n", ans);
  return 0;
}