洛谷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;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/n1anhwa4

---

题外话：

感觉那篇题解的解法确实精炼，我也不喜欢写废话。

虽说我的dp思路就是这个，但是很多重要的地方都没想到。