嘘~ 正在从服务器偷取页面 . . .

洛谷P3750 [六省联考 2017] 分手是祝愿题解

发布日期: 2024-05-09

更新日期: 2024-05-09

文章字数: 771

洛谷P3750 [六省联考 2017] 分手是祝愿题解

题目链接：P3750 [六省联考 2017] 分手是祝愿

题意：

有一个长度为 $n$ 的 01 串，下标编号 $1$ 到 $n$。对位置 $p$ 操作一次可以使所有编号为 $p$ 的约数的位置 $0$ 变 $1$，$1$ 变 $0$。目标是使所有位置变成 $0$。B 君先随机操作若干次，等到当前局面可以在 $k$ 次操作以内达成目标时就使用最优策略，达成目标后结束操作。求期望操作次数。

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

输入格式：

第一行两个整数 $n, k$。

接下来一行 $n$ 个整数，每个整数是 $0$ 或者 $1$，其中第 $i$ 个整数表示第 $i$ 个灯的初始情况。

输出格式：

输出一行，为操作次数的期望乘以 $n$ 的阶乘对 $100003$ 取模之后的结果。

数据范围：

对于 $100\%$ 的测试点，$1 \leq n \leq 100000, 0 \leq k \leq n$；

对于以上每部分测试点，均有一半的数据满足 $k = n$。

相逢是问候，分手是祝愿。可以，很会起标题。

设 $f_i$ 为最优策略需要 $i$ 步时的期望步数，则

$f_i=\left\{\begin{array}{l} i, &i \le k \\[8pt]\frac{i}{n} f_{i-1}+\frac{n-i}{n} f_{i+1}+1 & i>k \end{array}\right.$

设 $f_i = f_{i-1} + b_i$ ，则

$f_i=\frac{i}{n}\left(f_i-b_i\right)+\frac{n-i}{n}\left(f_i+b_{i+1}\right)+1$

整理得

$b_i=\frac{(n-i) b_{i+1}+n}{i}$

边界：$b_n=1$

时间复杂度 $\mathcal{O}(n\sqrt{n})$ 或者 $\mathcal{O}(n \log n)$

代码是第一种：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

const int mod = 1e5 + 3;
int cnt, a[N], b[N], inv[N], fac[N], f[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m; inv[1] = fac[1] = 1;
    for(int i = 2; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
    for(int i = 2; i < mod; i++) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = n, j; i; i--) if(a[i])
    {
        for(j = 1; j * j < i; j++)
            if(i % j == 0) { a[j] ^= 1; a[i / j] ^= 1; }
        if(j * j == i) { a[j] ^= 1; } ++cnt;
    }
    if(m == n || m == n - 1) return cout << fac[n] * cnt % mod << '\n', 0;
    for(int i = 0; i <= m; i++) f[i] = i;
    b[n] = 1;
    for(int i = n - 1; i > m; i--) b[i] = ((n - i) * b[i + 1] + n) % mod * inv[i] % mod;
    for(int i = m + 1; i <= n; i++) f[i] = (f[i - 1] + b[i]) % mod;
    cout << fac[n] * f[cnt] % mod << '\n';
    return 0;
}