$$ \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; }
发表回复