本文共 1690 字，大约阅读时间需要 5 分钟。

为了解决问题，我们需要找到从开关按动次数的最优策略，并计算在模100003下的期望值。以下是详细的解决步骤：

最优操作策略

为了找到最优操作次数，我们从最大的灯泡编号n开始，向回扫描。对于每个灯泡i，如果它无法通过前面的操作关闭，则必须被单独按下。通过分析，我们发现每个灯泡i必须被按下当且仅当它的奇数约数数量多于偶数约数。

递推关系

设f[i]为从灯泡i开始到熄灭所需的最优操作次数期望。递推公式为： [ f[i] = \left( \frac{i}{n} + \frac{n-i}{n} \times (f[i+1] + f[i] + 1) \right) ] 其中，(\frac{i}{n})和(\frac{n-i}{n})是按正确和错误按钮的概率。

模逆元处理

由于模数100003为质数，可以使用费马小定理计算逆元。编写快速幂算法来计算模逆元，并将递推关系中的除法转换为模运算。

代码实现

代码示例

#include 
   
    
#include 
    
     
#define mo 100003
using namespace std;
ll ksm(ll x, ll y) {
    ll re = 1;
    while (y) {
        if (y & 1) re = (re * x) % mo;
        x = (x * x) % mo;
        y >>= 1;
    }
    return re;
}
void write(ll x) {
    for (int i = 1; i <= n; i++) {
        x = (x * i) % mo;
    }
    printf("%lld", x);
}
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    int num = 0;
    for (int i = n; i >= 1; i--) {
        if (a[i]) {
            num++;
            tmp = sqrt(i);
            for (int j = 1; j <= tmp; j++) {
                if (i % j == 0) {
                    a[j] ^= 1;
                    if (i / j != j) a[i / j] ^= 1;
                }
            }
        }
    }
    if (num <= k) {
        write(1);
        return;
    }
    for (int i = n; i >= 1; i--) {
        f[i] = (((1 * (n - i) * f[i+1]) % mo + 1 * n) % mo;
        f[i] = (f[i] * ksm(i, mo - 2)) % mo;
    }
    ans = k;
    for (int i = k + 1; i <= num; i++) {
        ans = (ans + f[i]) % mo;
    }
    write(ans);
    return;
}
    
   

结果计算

根据递推公式和模逆元，计算期望值，并乘以n的阶乘后取模100003。最终结果即为所求的期望值乘以n的阶乘的值。