BZOJ 4872 - [Shoi2017]分手是祝愿

#数学 #概率与期望 #期望动态规划

Published on 2017-05-02

题目地址

描述

Zeit und Raum trennen dich und mich.
时空将你我分开。

B 君在玩一个游戏，这个游戏由 $n(n\le {10}^5)$ 个灯和 $n$ 个开关组成，给定这 $n$ 个灯的初始状态，下标为从 $1$ 到 $n$ 的正整数。

每个灯有两个状态亮和灭，我们用 $1$ 来表示这个灯是亮的，用 $0$ 表示这个灯是灭的，游戏的目标是使所有灯都灭掉。

但是当操作第 $i$ 个开关时，所有编号为 $i$ 的约数（包括 $1$ 和 $i$ ）的灯的状态都会被改变，即从亮变成灭，或者是从灭变成亮。

B 君发现这个游戏很难，于是想到了这样的一个策略，每次等概率随机操作一个开关，直到所有灯都灭掉。

这个策略需要的操作次数很多，B 君想到这样的一个优化。如果当前局面，可以通过操作小于等于 $k(0\le k\le n)$ 个开关使所有灯都灭掉，那么他将不再随机，直接选择操作次数最小的操作方法（这个策略显然小于等于 $k$ 步）操作这些开关。

B 君想知道按照这个策略（也就是先随机操作，最后小于等于 $k$ 步，使用操作次数最小的操作方法）的操作次数的期望。

这个期望可能很大，但是 B 君发现这个期望乘以 $n$ 的阶乘一定是整数，所以他只需要知道这个整数对 $100003$ 取模之后的结果。

分析

一个灯按两次没有意义，所以一个灯要么按要么不按。而且按灯的顺序是无关紧要的。

我们先考虑一个状态如何最快达到全灭。我们先考虑编号最大的亮灯 $x$ 是由谁熄灭的。不难发现只有按 $x$ 才能熄灭，原因是如果按编号 $> x$ 的灯来熄灭 $x$ ，那么按过的编号 $> x$ 的灯中标号最大的就不能熄灭了。

于是我们得到了一个最优策略，每次按下编号最大的亮灯，重复直到所有灯都熄灭。可以发现，最优策略是唯一的，这也是唯一合法的策略（按灯的顺序是无关紧要的）。

我们先求出初始状态需要按灯的次数 $x$ ，设 $f_i$ 为当前需要按 $i$ 次，变到需要按 $i - 1$ 次的期望次数。根据题目要求，如果 $i\le k$ ，那么 $f_i = 1$ 。否则 $i > k$ ，每次按灯，有 $\frac i n$ 的概率按到一个需要按的灯，有 $\frac {n - i} n$ 的概率按到一个不需要按的灯，不难发现，按到一个不需要按的灯，需要多按一次来抵消，则可以列出方程：

f_i = \frac i n + \frac {n - i} n(f_i + f_{i + 1})

解出

f_i = \frac {n + (n - i)f_{i + 1}} i

递推即可，答案为

n!\sum_{i = 1}^xf_i

线性预处理 $1\sim n$ 的逆元，用筛法 $O(n\log n)$ 预处理每个数的约数，总复杂度 $O(n\log n)$ 。

代码

//  Created by Sengxian on 2017/05/02.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  BZOJ 4872 期望 DP
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 100000 + 3, MOD = 100003;
int n, k, a[MAX_N], f[MAX_N], inv[MAX_N];
vector<int> divisor[MAX_N];

int solve(int cnt) {
    f[n] = 1, f[0] = 0;
    for (int i = n - 1; i > k; --i) f[i] = (n + (ll)(n - i) * f[i + 1]) * inv[i] % MOD;
    for (int i = 1; i <= k; ++i) f[i] = 1;

    int ans = 0;
    for (int i = 1; i <= cnt; ++i) (ans += f[i]) %= MOD;
    for (int i = 1; i <= n; ++i) ans = (ll)ans * i % MOD;

    return ans;
}

int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    n = readInt(), k = readInt();
    for (int i = 1; i <= n; ++i) a[i] = readInt();

    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i)
            divisor[j].push_back(i);

    inv[1] = 1;
    for (int i = 2; i <= n; ++i) inv[i] = ((-(ll)(MOD / i) * inv[MOD % i] % MOD) + MOD) % MOD;

    int cnt = 0;
    for (int i = n; i >= 1; --i) if (a[i]) {
        for (int j = 0; j < (int)divisor[i].size(); ++j)
            a[divisor[i][j]] ^= 1;
        ++cnt;
    }

    printf("%d\n", solve(cnt));

    return 0;
}

BZOJ 4871 - [Shoi2017]摧毁“树状图” BZOJ 4869 - [Shoi2017]相逢是问候

Sengxian's Blog

BZOJ 4872 - [Shoi2017]分手是祝愿

描述

分析

代码