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

Posted by Panda2134's Blog on March 13, 2018

上午做了六省联考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$ .

于是:

这可以高斯消元求解。但是 $n \le 10^5$ ,时间无法承受。

《训练指南》上面的 2 个关于马尔科夫过程的题,一个是高斯消元法,一个是手动消元。这里是不是可以手动消元呢?想想数学课上,学数列的时候,遇到这种式子常常移项差分。试一试:

就可以一个一个递推了。

边界的处理?$b_k$ 是不符合递推式的断点,怎么办?

换一边来推!

结合 $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;
}