[EC Final 2022] Binary String

形式化题目

给定一个长度为 $n$ 的环上的 $01$ 串 $a_0a_1\dots a_{n-1}$ 。每一秒，同时把所有满足 $a_i = 0$ 且 $a_{(i+1) \bmod n} = 1$ 的相邻对交换，即把每个 01 变成 10（同一格在同一步内最多参与一次交换）。

例如 100101110 一步之后变成 001010111。

问：从初始串出发，在无限秒中总共会出现多少个互不相同的串？两个串只要存在一位不同就算不同，所以循环移位算作不同的串。答案对 $998244353$ 取模。

$T \leqslant 10^6$ 组测试，所有串长之和 $\sum n \leqslant 10^7$ 。这就要求每组测试做到 $O(n)$ 。

样例：1 的答案是 $1$ ；001001 的答案是 $3$ ；0001111 的答案是 $9$ 。

暴力解法

思路

题目本身就是一段可以直接照做的过程：每一步把串扫一遍，同时执行所有 01 → 10，把得到的每个串都丢进一个集合里记录，直到某个串第二次出现为止。这时集合的大小就是答案。

之所以到「重复出现」就能停：这个系统是确定性的（同一个串必然只接同一个后继串），一旦某个串 $s$ 再次出现，之后就会沿着 $s$ 之后的那一段历史无限循环，不会再有新的串。

代码

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
40
41
42
43
44
45
46
47
48
49
50
51/**
 * 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-10-02 15:23
 * update_at: 2026-10-03 17:40
 */
// P9717 暴力对拍解：直接照题意模拟，直到某个串第二次出现为止。
//
// 用哈希表记录出现过的串（这里直接把串本身当 key），每一步同时把所有 01
// 换成 10，第一次遇到重复串时，出现过的不同串个数就是答案。
//
// 只用来跑很短的串（生成器保证 n <= 12，答案不超过 O(n^2)），
// 与 n 到 1e7 的正解形成对照。
#include <bits/stdc++.h>
using namespace std;

string step(const string &s) {
    int n = (int)s.size();
    string t = s;
    for (int i = 0; i < n; i++)
        if (s[i] == '0' && s[(i + 1) % n] == '1') {
            t[i] = '1';
            t[(i + 1) % n] = '0';
        }
    return t;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        unordered_set<string> seen;
        seen.insert(s);
        string cur = s;
        int cnt = 1;
        while (true) {
            cur = step(cur);
            if (seen.count(cur)) break;
            seen.insert(cur);
            cnt++;
        }
        cout << cnt << '\n';
    }
    return 0;
}

复杂度

设答案（不同串的个数）为 $A$ 。每步 $O(n)$ 构造新串，共 $A$ 步，用哈希表判重，总时间 $O(An)$ ，空间 $O(An)$ 存下所有出现过的串。 $n$ 稍大一点就完全不可行——而且 $A$ 本身最大可以达到 $O(n)$ 甚至 $O(n^2)$ 的量级，暴力连"答案有多大"都答不出来。

瓶颈

瓶颈显然是「真的把每个串都造出来」。但值得反思的是：这些串的数量真的需要逐个枚举吗？

试着手算几个小例子（每行是某一秒的串）：

text

1
2
3
4
5
6
7
8初始      001100
第 1 秒   010100
第 2 秒   101000
第 3 秒   010001
第 4 秒   100010
第 5 秒   000101
第 6 秒   001010
第 7 秒   010100   ← 又回到第 1 秒的串

001100 在第 1 秒后就进入了「第 1 秒 → 第 7 秒」这条路，之后永远在 $\{$ 第 1 秒, 第 2 秒, $\dots$ , 第 7 秒 $\}$ 这 7 个串里循环。也就是说轨道形状是一根"把手"接一个"环"（ $\rho$ 形）：先走 $T$ 步进入环，环上有 $P$ 个不同的串，答案就是 $T + P$ 。

而且细看这几个环上的串：它们都是同一个串的循环移位。010100 左移一格是 101000，再左移是 010001……环上正好是 010100 的全部 6 个循环移位中的 6 个吗？不是——这个环长是 $6$ （第 1 秒到第 6 秒），而串长也是 $6$ ，所以环长等于这个串的最小循环周期。

这两条观察（ $\rho$ 形 + 环长 = 终态最小周期）就把问题从"枚举所有串"变成了"只求一个终态串"，这是正解的出发点。

正解

思路

一、把 01 交换看成粒子运动（TASEP）

交换 01 → 10 之后，原来在右边的那格 $1$ 占了左边那一格，所以可以理解成：每个 $1$ 都试图向左移动一格，前提是它左边那一格是 $0$ ；左边被别的 $1$ 占着，它就原地不动。所有 $1$ 同时行动。

这是一个标准的排除过程模型（TASEP，等价于初等元胞自动机 Rule 184）。它的好处是粒子保持相对顺序： $1$ 只会向左、 $0$ 只会向右，粒子之间不会穿模，所以如果把 $1$ 从左到右编号，这个编号永远不会乱。

二、状态图是 $\rho$ 形：答案 = $T + P$

因为是确定性系统，从初始串出发的轨迹必然是「一条链 + 一个环」：

\underbrace{s_0 \to s_1 \to \dots \to s_{T-1}}_{\text{过渡段，}T\text{ 个串}} \to \underbrace{c_0 \to c_1 \to \dots \to c_{P-1}}_{\text{环，}P\text{ 个串}} \to c_0 \to \dots

出现过的不同串就是链上的 $T$ 个加环上的 $P$ 个，两两不重复（ $c_0$ 是第一次被访问的重复串）：

\boxed{\text{answer} = T + P}

$T$ 是"进入循环的步数"， $P$ 是"循环里不同串的个数"。

三、进入循环后的形态

在粒子模型里， $1$ 一直向左走、 $0$ 一直向右走，直到再也挤不动为止——也就是不再存在 01 这个模式。不再有 01 意味着：串里所有 $1$ 都排成了连续的一段，所有 $0$ 也排成连续的一段。此时唯一的动作就是把整个串向左（或向右）整体旋转一格，所以循环里的串全是这一个串的循环移位， $P$ 就是它的最小循环周期。

因此只需构造出循环中的任意一个串（终态），再用 KMP 求最小周期即可得到 $P$ 。 $T$ 则在求终态的过程中顺带算出。

一个容易踩的坑。 环长 $P$ 不是 $\dfrac{n}{\gcd(n,k)}$ （ $k$ 为终态或初始串中 $1$ 的个数，两者相同）。粒子模型里每秒每个 $1$ 都向左走一格，所以每秒是整体旋转 1 格而非 $k$ 格， $\dfrac{n}{\gcd(n,k)}$ 与 $P$ 一般不等。例如 001100 的 $k=2$ ， $\frac{6}{\gcd(6,2)}=3$ ，但真实答案是 $P=6$ （环是 010100 → 101000 → 010001 → 100010 → 000101 → 001010 → …）。小规模穷举（ $n \leqslant 14$ 的全部串）也确认了这个等式不成立，必须老老实实用 KMP 求最小周期。

四、把 $1$ 变成多数派

由第三节，终态是"一段 $1$ 加一段 $0$ "。

为了简化讨论，先做一个对称化简。定义变换 $M$ ：把每个字符取反（0↔1），再把整个串反转。注意到 $M$ 把 01 映成 10、把 10 映成 01，所以

M\big(\mathrm{step}(s)\big) = \mathrm{step}\big(M(s)\big),

即 $M$ 是轨道之间的同构， $T$ 和 $P$ 都不变。于是当 $0$ 比 $1$ 多时，先做一次 $M$ ，之后可以假定

\#1 \geqslant \#0 .

五、Raney 引理：把环切成链

环上有一个麻烦：最左边的那个 $0$ 段，可能要靠串尾的 $1$ 段绕一圈回来才能吃到。为了让"从右往左的扫法"一次成功，需要一个好的起点。

把 $1$ 记 $+1$ 、 $0$ 记 $-1$ 做前缀和。取前缀和首次达到全局最小值的位置，从它之后切开。 这是经典 Raney 引理的构造，切完之后这个（线性的）串满足：任意前缀里 $1$ 的个数都不少于 $0$ 的个数。

它的作用是保证串尾的 $1$ 段有足够"势能"一路向左吃光所有 $0$ 段，不必再考虑绕环的问题：每个 $0$ 段左边总能凑出足够的 $1$ 把它吃完。

六、栈模拟： $1$ 段吃 $0$ 段，求 $T$

切好之后从右往左扫，把串切成极长的 $01$ 段（连续的 1 叫 $1$ 段，连续的 0 叫 $0$ 段），用一个栈维护还没被吃掉的段。段的运动规律是：

长度 $> 1$ 的 $0$ 段，如果它左边紧邻的不是 $1$ 段（即它右边是 01），就整体左移一格；
长度 $> 1$ 的 $1$ 段对称地整体右移一格；
一个 $1$ 段和一个 $0$ 段正面相邻时，交界处两段每秒各减 $1$ （互相抵消），直到其中一段消失。

于是整个过程就是不断用右边的 $1$ 段吃掉左边的 $0$ 段。从右往左扫时，遇到一个 $1$ 段就把它入栈并与栈顶的 $0$ 段相撞：

设当前 $1$ 段长度为 $c$ 、左端点为 $i+1$ （即它占据 $[i+1,\, i+c]$ ），栈顶 $0$ 段长度为 $k$ 、左端点为 $l$ ，两段之间的空隙是 $g = l - (i+c)$ 。

$k > c$ （ $0$ 段更长）： $1$ 段被吃光， $0$ 段剩下 $k-c+1$ ，它的左端点右移 $c-1$ 。这段相撞在
$r = \frac{l-1-i-c}{2} = \frac{g-1}{2}$
秒后结束。
$k \leqslant c$ （ $1$ 段更长）： $0$ 段被吃光， $1$ 段剩 $c-k+1$ 继续去撞栈里的下一个 $0$ 段（所以用一个 while 循环）。这段相撞在
$r = \frac{l+2k-1-i-c}{2} = k + \frac{g-1}{2}$
秒后结束。

$r$ 是怎么来的？ 两段各以每秒一格的速度相向移动，先要花 $g/2$ 秒把空隙填掉，再过 $k$ 秒才把较短的 $0$ 段吃光；把"填空隙"和"吃段"合起来写成整格恰好是上式（ $g$ 一定是奇数，因为 $1$ 段右边界和 $0$ 段左边界之间隔着奇数个位置， $g-1$ 是偶数，所以 $r$ 是整数）。 $k>c$ 时吃到 $1$ 段用尽即停，少掉那 $k$ 秒。

取所有相撞事件的 $r$ 的最大值，得到

mx = T + 1 .

（"相撞结束"是过渡段的最后一步，所以 $T = mx - 1$ 。）栈里最后剩下的 $1$ 段就是终态里的那些 $1$ 段。

两个边界情形要注意：最右侧长度为 $1$ 的 $1$ 段可能和串首的 $1$ 段"并成一段"，需要把这样的单格 $1$ 段也补进栈。如果栈最后是空的（终态里没有长度 $\geqslant 2$ 的 $1$ 段），说明终态是 0101… 交替串，此时直接输出 $mx + 1$ 。

七、还原终态并用 KMP 求周期 $P$

有了终态里每个 $1$ 段的初始位置和长度，把它们整体按 $mx-1$ 步的反方向偏移（每个 $1$ 段向左移动过的总格数就是 $T=mx-1$ ），空隙用 01 交替补齐（因为终态里相邻两个 $1$ 段之间必然是 0101…01 的形式），就得到循环中的某一个确定串。

最后求它的最小循环周期 $P$ ：把串复制一遍接在后面，做一次 KMP 求 fail 数组，候选周期是 $n - \mathrm{fail}[n-1]$ ，但它只有在整除 $n$ 时才是真正的循环周期，否则 $P = n$ 。

于是

\text{answer} = T + P = (mx - 1) + P .

因为 $T + P \leqslant n + n = 2n < 998244353$ ，题目里的取模其实是诈骗，不需要真的取模。

算法流程

对每个测试点：

$n = 1$ 时直接输出 $1$ 。
若 $0$ 比 $1$ 多，做一次「取反 + 反转」。
求前缀和，在前缀和首次取到最小值处之后旋转（Raney 引理）。
从右往左扫 $01$ 段，用栈模拟 $1$ 段吃 $0$ 段，同时更新 $mx$ 。
栈空 → 输出 $mx+1$ ；否则按 $mx-1$ 反向偏移还原终态，用 01 交替补空隙。
对终态求最小循环周期 $P$ ，输出 $mx - 1 + P$ 。

代码

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171/**
 * 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-10-02 15:23
 * update_at: 2026-10-03 17:40
 */
// P9717 [EC Final 2022] Binary String
//
// 每一步同时把所有 01 换成 10。把 1 看成向左走的粒子（左边是 0 就走一格，
// 否则原地等待），整个过程就是环上的 TASEP（等价于 Rule 184）。
//
// 【状态图是 ρ 形】状态只会沿着一条链前进，很快进入一个纯旋转的环：环里的
// 每个串都是终态的循环移位，环长 = 终态这个循环串的最小周期 P；进环前走过
// 的步数是 T（初始串算第 0 步）。于是不同的串一共有 T + P 个。
//
// 【把 1 变多】若 0 比 1 多，就把 01 取反再整体反转。交换规则在这个变换下
// 不变（01 -> 10 与 10 -> 01 互相对应），所以 T、P 都不变。
//
// 【破环为链：Raney 引理】在环上，最左边的那个 0 段可能要靠串尾的 1 段绕一
// 圈才能吃掉。把 1 记 +1、0 记 -1 做前缀和，从"前缀和首次取到最小值"的位置
// 之后把环切开，可以保证任意前缀里 1 的个数不少于 0 的个数，于是串尾的 1 段
// 一定能一路向左吃光所有 0 段，环上的麻烦就消失了。
//
// 【栈模拟段相撞】从右往左扫，用一个栈维护还没被吃掉的 01 段（左端点、长度）。
// 长度 > 1 的 1 段整体右移，长度 > 1 的 0 段整体左移；两者相遇后交界处每秒各
// 减 1，直到其中一段消失。设当前 1 段长度 c、左端点 i+1，栈顶 0 段长度 k、
// 左端点 l，则这段相撞结束（也就是"两个段的端点相遇"）所需的秒数 r 为：
//     k > c  ： 1 段被吃光，r = (l - 1 - i - c) / 2
//     k <= c ： 0 段被吃光，r = (l + 2k - 1 - i - c) / 2
// 取所有相撞事件里最大的 r，得到 mx = T + 1（r 的推导见题解正文）。
//
// 【还原终态】栈里剩下的 1 段就是终态里的那些 1 段，把它们整体按 mx-1 反向
// 偏移，空隙用 01 交替补齐，就得到环上的一个确定串。
//
// 【KMP 求 P】环长就是该串的最小整周期。把串复制一遍接在后面，用 KMP 求
// 最小周期 P = 2n - fail[2n]，答案就是 T + P = (mx - 1) + P。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 10000000 + 10;

static char inbuf[1 << 25];      // 一次性读入全部输入
static char s[MAXN];             // 当前串
static int  failArr[MAXN];       // KMP 失配数组
static int  segL[MAXN], segC[MAXN]; // 栈元素：段的左端点、段长

// 求一个串的「循环最小整周期」：即最小的 p | n，使得整体循环左移 p 位不变。
// 先对单串求 KMP 失配数组，取候选周期 p = n - fail[n-1]；只有 p | n 时才是
// 真正的循环周期，否则说明没有更小的周期，答案为 n。
int min_period(int n) {
    failArr[0] = -1;
    for (int i = 1, j = -1; i <= n; i++) {
        while (j >= 0 && s[i] != s[j + 1]) j = failArr[j];
        failArr[i] = ++j;
    }
    int p = n - failArr[n];
    return (p > 0 && n % p == 0) ? p : n;
}

void solve_one(char *a, int n) {
    if (n == 1) { puts("1"); return; }

    for (int i = 1; i <= n; i++) s[i] = a[i - 1];

    // 【把 1 变多】0 占多数时取反并反转
    int zeros = 0;
    for (int i = 1; i <= n; i++) if (s[i] == '0') zeros++;
    if (zeros * 2 > n) {
        for (int i = 1; i <= n; i++) s[i] ^= 1;
        reverse(s + 1, s + n + 1);
    }

    // 【破环为链】前缀和最小处之后切开（Raney 引理）
    int cut = 0, now = 0, low = 0;
    for (int i = 1; i <= n; i++) {
        now += (s[i] == '0' ? -1 : 1);
        if (now < low) { low = now; cut = i; }
    }
    rotate(s + 1, s + cut + 1, s + n + 1);

    // 【栈模拟】从右往左扫描 01 段
    s[n + 1] = '\0';   // 哨兵：保证 i=n 时进入 "新段开始" 分支
    int top = 0, mx = 1;
    int i = n, c = 0;          // c 表示 s[i+1..i+c] 这一段的长度
    while (i >= 0) {
        if (s[i] == s[i + 1]) {
            c++;
        } else {
            // 一段（s[i+1..i+c]）刚刚结束
            if (c > 1) {
                if (s[i + 1] == '0') {
                    segL[++top] = i + 1; segC[top] = c;    // 0 段入栈
                } else {
                    // 1 段：不断吃掉栈里的 0 段
                    while (top && s[segL[top]] == '0' && c > 1) {
                        int k = segC[top], l = segL[top];
                        if (k > c) {
                            // 1 段被吃光，0 段剩下 k-c+1，左端点右移 c-1
                            int v = l - 1 - i - c;
                            if (v / 2 > mx) mx = v / 2;
                            segC[top] = k - c + 1;
                            segL[top] = l + c - 1;
                            c = 0;
                            break;
                        } else {
                            // 0 段被吃光，1 段剩 c-k+1 继续吃
                            int v = l + 2 * k - 1 - i - c;
                            if (v / 2 > mx) mx = v / 2;
                            c = c - k + 1;
                            top--;
                        }
                    }
                    if (c > 1) { segL[++top] = i + 1; segC[top] = c; }
                }
            }
            c = 1;
        }
        i--;
    }

    // 边界：最右侧长度为 1 的 1 段可能与串首的 1 段并成一段
    if (s[n - 1] == '0' && s[n] == '1' && s[1] == '1') {
        segL[++top] = n; segC[top] = 1;
    }
    if (s[2] == '0' && s[1] == '1' && s[n] == '1') {
        segL[++top] = 1; segC[top] = 1;
    }

    if (top == 0) {          // 终态里没有长度 ≥ 2 的 1 段，重建出来就是 0101… 交替串
        printf("%d\n", mx + 1);
        return;
    }

    // 【还原终态】把所有 1 段按 mx-1 反向偏移，空隙用 01 交替补齐
    for (int k = 1; k <= n; k++) s[k] = '?';
    for (int k = 1; k <= top; k++)
        for (int j = segL[k]; j < segL[k] + segC[k]; j++)
            s[(j + mx - 2) % n + 1] = '1';
    int last = 0;
    for (int k = 1; k <= n; k++) {
        if (s[k] == '1') {
            // 注意顺序：紧靠 1 段左侧的那一格要写 '0'，向左边依次 0,1,0,1
            char o = '1';
            for (int j = k - 1; j > last; j--) { o ^= 1; s[j] = o; }
            last = k;
        }
    }
    { char o = '1'; for (int j = last + 1; j <= n; j++) { o ^= 1; s[j] = o; } }

    // 【KMP】环长 = 终态最小整周期
    printf("%d\n", min_period(n) + mx - 1);
}

int main() {
    int len = (int)fread(inbuf, 1, sizeof(inbuf) - 1, stdin);
    inbuf[len] = 0;
    char *p = inbuf;
    while (*p && (*p < '0' || *p > '9')) p++;
    int T = 0;
    while (*p >= '0' && *p <= '9') T = T * 10 + (*p++ - '0');
    while (T--) {
        while (*p && *p != '0' && *p != '1') p++;
        char *st = p;
        while (*p == '0' || *p == '1') p++;
        solve_one(st, (int)(p - st));
    }
    return 0;
}

复杂度

每组测试：翻转、前缀和、栈模拟、还原、KMP 各扫常数次，时间 $O(n)$ ，空间 $O(n)$ 。
总时间 $O\left(\sum n\right) \leqslant 10^7$ ，总空间 $O(\max n)$ 。因为 $T$ 可达 $10^6$ ，代码用一次性 fread 读入全部输入，避免 $10^6$ 次 cin/scanf 的开销。

总结

粒子模型。 把 01 → 10 理解成「 $1$ 向左走一格（左边是 $0$ 时）」，过程就是环上的 TASEP；粒子保持相对顺序， $1$ 只会向左、 $0$ 只会向右。
状态图是 $\rho$ 形。 确定性系统从初始串出发，先走 $T$ 步进入一个环，环长 $P$ ，出现过的不同串共 $T+P$ 个。
终态 = 一段 $1$ 加一段 $0$ 。 过程进行到没有 01 为止，此后只是整体旋转，所以环上的串全是同一个串的循环移位， $P$ 就是这个终态的最小循环周期（KMP 求）。
两个化简。 用「取反 + 反转」把 $1$ 变多（这个变换与演化可交换， $T,P$ 不变）；用 Raney 引理（切在前缀和首次最小值之后）把环变成链，保证串尾的 $1$ 段能一路吃光所有 $0$ 段。
栈模拟定 $T$ 。 从右往左扫 $01$ 段， $1$ 段不断吃掉栈顶的 $0$ 段；每次相撞结束所需秒数是 $r = \frac{g-1}{2}$ 或 $k + \frac{g-1}{2}$ （ $g$ 是两段之间的空隙），取最大值得 $mx = T+1$ 。
还原与周期。 把栈里剩下的 $1$ 段按 $T = mx-1$ 反向偏移、空隙补 01 交替，得到终态串；再求最小循环周期 $P$ ，答案 $= T + P$ 。取模是诈骗，答案本身不超过 $2n$ 。