上午做了六省联考2017 Day2.
挂的一塌糊涂，除了某个做过的题 A 了之外其他题目加起来只有55. 这个题目的贪心都没想到。
cxy神犇接近AK。
技不如人， 如果不多刷题的话， 可能只有失败的后果吧。
现在也不要想别的了，挂了就是自己弱， 没别的。 就是自己弱。太弱了，就没有大学上了。
去除杂念， 专心刷题， 才有可能超越啊。
思路
我们考虑50分的情况。
对于50%的数据, 满足 $n = k$.
$n = k$ , 说明求期望变成了求最小步数。打个暴力可以发现, 最小步数一定小于 $n$ . 为什么呢? 我们考虑构造一个方案来达到最小的步数。每个数的约数小于等于它本身，于是我们贪心地从右边往左边扫，每次碰到一个亮着的灯就按按钮。我们注意到，由于异或的定义，每个按钮最多按一次。所以总次数小于 $n$， 一定是可行解。如何证明其最优性？如果某个灯本来是亮的，可以分2种情况。由于它必须最后被按灭，要么它在扫到它之前就灭了，要么它在扫到它的时候被按灭。前者说明一次按灭了大于等于2个灯，贪心的答案不会更坏。后者也不会使得答案劣于最优解。如果某个灯是灭的，在按比它编号大的按钮的时候被点亮，我们可以发现，按比它编号大的按钮，一定是由于那个灯是亮的，因此不得不按。最优解不可能比当前贪心策略更好。
这种贪心实际上可以得到80分。
以上都还没有涉及到期望。我们现在来加入 $n \neq k$ 的情况，这就需要建立期望的递推关系。
真的需要把当前的状态塞进期望递推式吗？动态规划和递推的状态设计，要看转移的需要。如果转移不需要完整的局面，就没必要把完整的局面塞进递推。显然，如果设每个开关 $i$ 至少还需要按的次数为 $x_i$ ，那么一定有 $x_i \in \{ 0, 1 \}$. 考虑当前全部开关加起来还需要按 $t$ 次才能清零。这可以看做有 $t$ 个 1 装在 $t$ 个盒子里面，其他的盒子为空。任意取走某一个 1 ，此后的步数减少 1 ；往没有 1 的盒子里面放一个 1 ，此后的步数增加 1.
可以看出，转移只和全部开关加起来要按的次数有关。
设 $a_i$ 表示当前还有 $i$ 个 1 的情况下期望按多少次能全部按成0.此处的 $i$ 就是刚才的 $t$ .
于是：
\[\begin{equation} a_i = \begin{cases} i & 当 i \le k \\ 1 + \frac{n - i}{n} \cdot a_{i+1} + \frac{i}{n} \cdot a_{i-1} & 当 i > k \end{cases} \end{equation}\]这可以高斯消元求解。但是 $n \le 10^5$ ，时间无法承受。
《训练指南》上面的 2 个关于马尔科夫过程的题，一个是高斯消元法，一个是手动消元。这里是不是可以手动消元呢？想想数学课上，学数列的时候，遇到这种式子常常移项差分。试一试：
\[\begin{align*} \text{Let }b_i &= a_{i+1} - a_i \\ \Rightarrow b_i &= \frac{i \cdot b_{i-1} - n}{n - i}(i > k) \end{align*}\]就可以一个一个递推了。
边界的处理？$b_k$ 是不符合递推式的断点，怎么办？
换一边来推！
\[\begin{align*} b_i &= \frac{i \cdot b_{i-1} - n}{n - i}(i > k) \\ \Rightarrow b_{i-1} &= \frac{(n-i)b_i+n}{i}(i > k) \\ \Rightarrow b_{i} &= \frac{(n - i - 1)b_{i+1}+n}{i+1}(i \ge k) \end{align*}\]结合 $b_{n-1} = 1$ 这一结论（所有盒子里面都有 1 ，任意摸一个都可以减少一步），又有 $\forall i < k, b_i = 1$ ，可以得出答案。
疑问：题中给出的状态，不一定可达 $b_{n-1}$ ，为何可以这么递推？
好像想通了…… $b_{n-1}$ 只是递推的起点，我们要根据初始状态的最少步数来确定取 ${b_n}$ 的哪一项。
考虑差分出的 $b_i$ 的组合意义：从剩下 $i+1$ 步到 $i$ 步的期望操作数目。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int MAXN = 1e5, MOD = 100003;
int n, k, cnt, ans, A[MAXN+10], a[MAXN+10], b[MAXN+10]; vector<int> vec[MAXN+10];
inline int mod_mul(int a, int b) { return ((int64(a) % MOD) * (int64(b) % MOD)) % MOD; }
inline int fastpow(int a, int x) {
int ret = 1;
while(x) {
if(x&1) ret = mod_mul(ret, a);
x >>= 1; a = mod_mul(a, a);
}
return ret;
}
int main() {
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++)
scanf("%d", A + i);
for(int i = 1; i <= n; i++)
for(int j = 1; i * j <= n; j++)
vec[i * j].push_back(i);
for(int i = n; i >= 1; i--) if(A[i]) {
++cnt;
for(int j = 0; j < int(vec[i].size()); j++) {
int x = vec[i][j];
A[x] ^= 1;
}
}
b[n - 1] = 1;
for(int i = n-2; i >= k; i--)
b[i] = mod_mul(mod_mul(n-i-1, b[i+1]) + n, fastpow(i+1, MOD-2));
for(int i = k-1; i >= 0; i--)
b[i] = 1;
a[0] = 0;
for(int i = 0; i <= n-1; i++)
a[i+1] = b[i] + a[i];
ans = a[cnt];
for(int i = 1; i <= n; i++)
ans = mod_mul(ans, i);
printf("%d", ans);
return 0;
}
