「IXOI R3」贴吧 82 号

形式化题目

给定长度为 n 的 01 串。选择一个正整数 x 会翻转所有 x 的倍数位置，求把字符串变成全 1 所需的最少选择次数。

暴力解法

思路

每个操作重复两次会抵消，所以操作 $x$ 只需考虑“选”或“不选”。枚举全部 $2^n$ 个操作子集，逐个模拟所有倍数翻转，再检查字符串是否变成全 $1$ ，即可得到小数据答案。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-06 19:06
 * update_at: 2026-09-06 19:22
 */
// brute.cpp：小数据暴力解，枚举每个操作是否选择，用来辅助对拍。
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n >> s;

    int answer = n + 1;
    int all = 1 << n;
    for (int mask = 0; mask < all; mask++) {
        string t = s;
        int used = 0;
        for (int x = 1; x <= n; x++) {
            if (((mask >> (x - 1)) & 1) == 0) {
                continue;
            }
            used++;
            for (int j = x; j <= n; j += x) {
                t[j - 1] = (t[j - 1] == '0' ? '1' : '0');
            }
        }
        if (t.find('0') == string::npos) {
            answer = min(answer, used);
        }
    }
    cout << answer << '\n';
    return 0;
}

复杂度与瓶颈

每个方案最多模拟 $O(n \log n)$ 次翻转，总时间复杂度为 $O(2^n n \log n)$ ，只能通过 $n \leqslant 10$ 的子任务。瓶颈是枚举了所有操作选择，而实际上每个操作是否选择会被某个位置唯一确定。

正解

思路

设 $z_x$ 表示是否选择操作 $x$ ，因此 $z_x \in \{0,1\}$ 。位置 $i$ 最终需要翻转 $t_i=1-s_i$ 次（按奇偶性计），满足

t_i=\bigoplus_{x\mid i}z_x.

按 i=1,2,...,n 处理。操作 i 只会影响 i 的倍数，不会影响更小的位置；因此处理位置 i 时，当前异或值已经由更小的操作唯一确定：

若当前值已经等于 t_i，不选 i；
否则必须选 i，并把它加入所有倍数的当前影响。

这同时说明了选择方案的唯一性，也是从指数枚举降到调和级数复杂度的关键。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-06 19:06
 * update_at: 2026-09-06 19:22
 */
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n >> s;

    vector<unsigned char> current(n + 1, 0);
    int answer = 0;

    // 按下标从小到大决定是否操作 i。操作 i 只影响 i 的倍数，
    // 所以处理到 i 时，current[i] 已经只包含更小操作的影响。
    for (int i = 1; i <= n; i++) {
        int need = (s[i - 1] == '0');
        if (current[i] != need) {
            answer++;
            for (int j = i; j <= n; j += i) {
                current[j] ^= 1;
            }
        }
    }

    cout << answer << '\n';
    return 0;
}

复杂度

操作 $i$ 会遍历 $i$ 的所有倍数，总次数为 $n/1+n/2+\cdots+n/n=O(n\log n)$ ，状态数组占用 $O(n)$ 空间。

总结

把“翻转”改成 GF(2) 上的异或后，除数关系可以从小到大逐点消元。每一步不是试探，而是被当前位置的目标奇偶性唯一确定。