洛谷3750 [六省联考2017]分手是祝愿

$$ \text{首先可以证明，把原局面从到大小一个一个关所经历的步数一定最少} \\ \left( \text{每次必定选择编号最大的没有关闭的灯} \right) \text{所以先求出来这个步数。} \\ \text{如果这个步数不超过}k\text{，那么这个步数就是答案。} \\ \text{否则设}f\left( i \right) \text{表示还剩}i\text{步的时候，随机选择一个开关是转移到还剩}i-\text{1步的期望步数。} \\ f\left( i \right) =\frac{i}{n}\left( \text{选中了一个正确的开关} \right) +\left( 1-\frac{i}{n} \right) \left( f\left( i \right) +f\left( i+1 \right) +1 \right) \left( \text{选中了一个错误的开关，那么步数}+1 \right) \\ \text{显然}f\left( n \right) =\text{1，此时随便选一个开关都会让步数少}1. \\ \text{整理得}f\left( i \right) =1+\frac{n-i}{i}\left( f\left( i+1 \right) +1 \right) \\ \text{计算出}f\left( k+1 \right) \text{到}f\left( n \right) \text{的答案累加起来，加上}k\text{即可。} \\ $$

#include <algorithm>
#include <iostream>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t mod = 100003;
const int_t LARGE = 1e5;
int_t inv[LARGE + 1];
int_t state[LARGE + 1];
int_t f[LARGE + 1];
std::vector<int_t> divisors[LARGE + 1];
int_t n, k;
int main() {
    for (int_t i = 1; i <= LARGE; i++) {
        for (int_t j = 1; j * i <= LARGE; j++) {
            divisors[j * i].push_back(i);
        }
    }
    inv[1] = 1;
    for (int_t i = 2; i <= LARGE; i++) {
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    }
    cin >> n >> k;
    for (int_t i = 1; i <= n; i++) {
        cin >> state[i];
    }
    int_t steps = 0;
    for (int_t i = n; i >= 1; i--) {
        if (state[i]) {
            steps++;
            for (int_t x : divisors[i]) state[x] ^= 1;
        }
    }
    int_t result = 0;
    if (steps <= k) {
        result = steps;
    } else {
        f[n] = 1;
        for (int_t i = n - 1; i >= 1; i--) {
            f[i] = (1 + (n - i) * inv[i] % mod * (f[i + 1] + 1) % mod) % mod;
        }
        for (int_t i = steps; i > k; i--) result = (result + f[i]) % mod;
        result = (result + k) % mod;
    }
    for (int_t i = 1; i <= n; i++) result = result * i % mod;
    cout << result << endl;
    return 0;
}