月票发行

GitHub跳转原题关系图 Canvas 关系图返回列表

用有限状态自动机统计连续自由字母段，并以线性递推和 Kitamasa 处理超长段。

OJ: shumeng

题目 ID: CSP202506D

难度:未知

标签:字符串自动机线性递推矩阵快速幂计数DP

日期: 2026-07-31 16:21

形式化题目

构造长度为 $n$ 的字符串，其中 $m$ 个固定位置为 #，其余位置填写 a-z。统计同时满足以下条件的字符串数量对 $998244353$ 取模的结果：

子串 ccf 和 cspark 都至少出现一次；
存在一对 ccf 与 cspark，使得 ccf 出现在 cspark 的左侧。

思路

# 不参与模式匹配，并把模式匹配后缀清空，因此字符串被自然切成若干段连续的自由字母段。段之间用全局状态衔接。

全局三状态

状态 0：尚未出现 ccf；
状态 1：已出现 ccf，但还没有出现位于其右侧的 cspark；
状态 2：已满足条件（存在左侧 ccf 和右侧 cspark）。

状态 2 只增不减。

段内计数

对一段长度为 $L$ 的自由段，用前缀自动机（7 个状态）记录匹配到 ccf/cspark 的后缀。需要的四种段计数：

no_ccf：不含 ccf；
no_spark：不含 cspark；
no_both：两者都不含；
safe_order：段内不出现"先 ccf 后 cspark"的先后关系。

这些固定维数状态的计数满足低阶线性递推。长度 $L \le 10^5$ 时直接预计算； $L$ 更大时用 Kitamasa 在 $O(\log L)$ 内求第 $L$ 项。

段间转移

设一段自由段长度为 $L$ ， $C_c$ 表示不含 ccf 的段数， $C_s$ 表示不含 cspark 的段数， $C_o$ 表示 safe_order 段数， $T=26^L$ 为段内方案总数，三状态的转移为：

新状态 0 = 旧状态 0 × $C_c$ ；
新状态 1 = 旧状态 1 × $C_s$ + 旧状态 0 ×（ $C_o - C_c$ ）；
新状态 2 = 旧状态 2 × $T$ + 旧状态 1 ×（ $T - C_s$ ）+ 旧状态 0 ×（ $T - C_o$ ）。

代码

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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:57
 */
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353LL;
const int PREFIX_COUNT = 7;   // 自动机状态数：空串及 c,cc,cs,csp,cspa,cspar 六个前缀
const int STATUS_COUNT = 4;   // 全局顺序状态数：未出现/已现ccf/已现cspark/已满足
const int SMALL_LIMIT = 100000; // 直接递推预计算的长度上限

// next_state[状态][字符]：加入字符后的新状态
int next_state[PREFIX_COUNT][26];
// output_mask[状态][字符]：本次转移是否产生 ccf(1) / cspark(2)
int output_mask[PREFIX_COUNT][26];
string prefixes[PREFIX_COUNT] = {"", "c", "cc", "cs", "csp", "cspa", "cspar"};

long long normalize(long long value) {
    value %= MOD;
    if (value < 0) value += MOD;
    return value;
}

long long power_mod(long long base, long long exponent) {
    long long answer = 1;
    base %= MOD;
    while (exponent > 0) {
        if (exponent & 1) answer = answer * base % MOD;
        base = base * base % MOD;
        exponent >>= 1;
    }
    return answer;
}

// 构造前缀自动机：转移后更新最长可匹配前缀，并记录本次是否产生了完整模式
void build_automaton() {
    for (int state = 0; state < PREFIX_COUNT; state++) {
        for (int ch = 0; ch < 26; ch++) {
            char character = (char)('a' + ch);
            string text = prefixes[state] + character;
            int mask = 0;
            if (text.size() >= 3 && text.substr(text.size() - 3) == "ccf") {
                mask |= 1;
            }
            if (text.size() >= 6 && text.substr(text.size() - 6) == "cspark") {
                mask |= 2;
            }
            int best = 0;
            for (int candidate = 1; candidate < PREFIX_COUNT; candidate++) {
                if (prefixes[candidate].size() <= text.size() &&
                    text.substr(text.size() - prefixes[candidate].size()) ==
                    prefixes[candidate] &&
                    prefixes[candidate].size() > prefixes[best].size()) {
                    best = candidate;
                }
            }
            next_state[state][ch] = best;
            output_mask[state][ch] = mask;
        }
    }
}

// 多项式取模乘法：a,b 是次数小于 degree 的多项式，按 characteristic 的递推关系降次
vector<long long> multiply_polynomial(const vector<long long> &a,
    const vector<long long> &b, const vector<long long> &characteristic) {
    int degree = (int)characteristic.size() - 1;
    vector<long long> temp(2 * degree - 1, 0);
    for (int i = 0; i < degree; i++) {
        for (int j = 0; j < degree; j++) {
            temp[i + j] = (temp[i + j] + a[i] * b[j]) % MOD;
        }
    }
    for (int i = 2 * degree - 2; i >= degree; i--) {
        long long coefficient = temp[i];
        if (coefficient == 0) continue;
        for (int j = 1; j <= degree; j++) {
            temp[i - j] = normalize(temp[i - j] -
                coefficient * characteristic[j]);
        }
    }
    temp.resize(degree);
    return temp;
}

// Kitamasa 算法：在线性递推 characteristic 下求第 index 项（index 从 0 开始）
long long linear_term(long long index, const vector<long long> &initial,
    const vector<long long> &characteristic) {
    int degree = (int)characteristic.size() - 1;
    if (index < degree) return initial[index];
    vector<long long> result(degree, 0);
    vector<long long> base(degree, 0);
    result[0] = 1;
    if (degree == 1) base[0] = normalize(-characteristic[1]);
    else base[1] = 1;
    while (index > 0) {
        if (index & 1) result = multiply_polynomial(result, base, characteristic);
        base = multiply_polynomial(base, base, characteristic);
        index >>= 1;
    }
    long long answer = 0;
    for (int i = 0; i < degree; i++) {
        answer = (answer + result[i] * initial[i]) % MOD;
    }
    return answer;
}

// 预计算前 SMALL_LIMIT 项：no_ccf/no_both/no_spark/safe_order
// 分别是不含ccf、不含两者、不含cspark、段内不先ccf后cspark 的字符串计数
void make_small_sequences(vector<long long> &no_ccf, vector<long long> &no_both,
    vector<long long> &no_spark, vector<long long> &safe_order) {
    no_ccf.assign(SMALL_LIMIT + 1, 0);
    no_both.assign(SMALL_LIMIT + 1, 0);
    no_spark.assign(SMALL_LIMIT + 1, 0);
    safe_order.assign(SMALL_LIMIT + 1, 0);
    vector<long long> state_ccf(PREFIX_COUNT, 0);
    vector<long long> state_both(PREFIX_COUNT, 0);
    vector<long long> state_spark(PREFIX_COUNT, 0);
    vector<long long> state_order(PREFIX_COUNT * STATUS_COUNT, 0);
    state_ccf[0] = 1;
    state_both[0] = 1;
    state_spark[0] = 1;
    state_order[0] = 1;
    no_ccf[0] = 1;
    no_both[0] = 1;
    no_spark[0] = 1;
    safe_order[0] = 1;

    for (int length = 0; length < SMALL_LIMIT; length++) {
        vector<long long> next_ccf(PREFIX_COUNT, 0);
        vector<long long> next_both(PREFIX_COUNT, 0);
        vector<long long> next_spark(PREFIX_COUNT, 0);
        vector<long long> next_order(PREFIX_COUNT * STATUS_COUNT, 0);
        for (int state = 0; state < PREFIX_COUNT; state++) {
            for (int ch = 0; ch < 26; ch++) {
                int next = next_state[state][ch];
                int mask = output_mask[state][ch];
                if (mask == 0) {
                    next_both[next] = (next_both[next] + state_both[state]) % MOD;
                }
                if ((mask & 1) == 0) {
                    next_ccf[next] = (next_ccf[next] + state_ccf[state]) % MOD;
                }
                if ((mask & 2) == 0) {
                    next_spark[next] = (next_spark[next] + state_spark[state]) % MOD;
                }
                for (int status = 0; status < STATUS_COUNT; status++) {
                    int new_status = status;
                    if (mask & 1) {
                        if (status == 0) new_status = 2;
                        else if (status == 1) new_status = 3;
                    }
                    if (mask & 2) {
                        if (status >= 2) continue;
                        new_status = 1;
                    }
                    int old_index = state * STATUS_COUNT + status;
                    int new_index = next * STATUS_COUNT + new_status;
                    next_order[new_index] = (next_order[new_index] +
                        state_order[old_index]) % MOD;
                }
            }
        }
        state_ccf.swap(next_ccf);
        state_both.swap(next_both);
        state_spark.swap(next_spark);
        state_order.swap(next_order);
        for (int state = 0; state < PREFIX_COUNT; state++) {
            no_ccf[length + 1] = (no_ccf[length + 1] + state_ccf[state]) % MOD;
            no_both[length + 1] = (no_both[length + 1] + state_both[state]) % MOD;
            no_spark[length + 1] = (no_spark[length + 1] + state_spark[state]) % MOD;
        }
        for (int state = 0; state < PREFIX_COUNT * STATUS_COUNT; state++) {
            safe_order[length + 1] = (safe_order[length + 1] + state_order[state]) % MOD;
        }
    }
}

long long get_sequence_value(long long length, const vector<long long> &small,
    const vector<long long> &characteristic) {
    if (length <= SMALL_LIMIT) return small[(int)length];
    vector<long long> initial(characteristic.size() - 1, 0);
    for (int i = 0; i < (int)initial.size(); i++) initial[i] = small[i];
    return linear_term(length, initial, characteristic);
}

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

    int n, fixed_count;
    cin >> n >> fixed_count;
    vector<int> fixed_position(fixed_count);
    for (int i = 0; i < fixed_count; i++) cin >> fixed_position[i];

    build_automaton();
    vector<long long> no_ccf, no_both, no_spark, safe_order;
    make_small_sequences(no_ccf, no_both, no_spark, safe_order);

    vector<long long> characteristic_ccf = {1, MOD - 26, 0, 1};
    vector<long long> characteristic_both = {1, MOD - 26, 0, 1, 0, 0, 1};
    vector<long long> characteristic_spark = {1, MOD - 26, 0, 0, 0, 0, 1};
    vector<long long> characteristic_order = {
        1, MOD - 52, 676, 1, MOD - 26, 0, 1, MOD - 26, 0, 1
    };

    // 全局状态：0 尚未出现 ccf，1 已出现 ccf 尚未满足，2 已满足条件
    long long status[3] = {1, 0, 0};
    long long current_position = 1;
    for (int i = 0; i < fixed_count; i++) {
        // 处理 # 之前的自由段 [current_position, fixed_position[i]-1]
        long long length = fixed_position[i] - current_position;
        long long count_ccf = get_sequence_value(length, no_ccf, characteristic_ccf);
        long long count_spark = get_sequence_value(length, no_spark, characteristic_spark);
        long long count_safe = get_sequence_value(length, safe_order, characteristic_order);
        long long total = power_mod(26, length);
        long long next_status[3];
        next_status[0] = status[0] * count_ccf % MOD;
        next_status[1] = (status[1] * count_spark + status[0] *
            normalize(count_safe - count_ccf)) % MOD;
        next_status[2] = (status[2] * total + status[1] *
            normalize(total - count_spark) + status[0] *
            normalize(total - count_safe)) % MOD;
        for (int j = 0; j < 3; j++) status[j] = next_status[j];
        current_position = fixed_position[i] + 1;
    }

    // 处理最后一个 # 之后的剩余自由段
    long long length = (long long)n - current_position + 1;
    long long count_ccf = get_sequence_value(length, no_ccf, characteristic_ccf);
    long long count_spark = get_sequence_value(length, no_spark, characteristic_spark);
    long long count_safe = get_sequence_value(length, safe_order, characteristic_order);
    long long total = power_mod(26, length);
    long long next_status[3];
    next_status[0] = status[0] * count_ccf % MOD;
    next_status[1] = (status[1] * count_spark + status[0] *
        normalize(count_safe - count_ccf)) % MOD;
    next_status[2] = (status[2] * total + status[1] *
        normalize(total - count_spark) + status[0] *
        normalize(total - count_safe)) % MOD;
    cout << normalize(next_status[2]) << '\n';
    return 0;
}

复杂度

预计算 $O(10^5)$ 项；每个较长自由段用 Kitamasa 求项为 $O(\log L)$ 。总时间复杂度 $O(m \log n)$ ，空间复杂度 $O(10^5)$ 。

总结

固定字符把超长字符串切成独立自由段，段内计数可以用线性递推快速跨过很长的区间。自动机负责匹配后缀，Kitamasa 负责求递推项，两者组合即可处理 $n$ 高达 $10^9$ 的规模。

题目来自第 38 次 CSP 认证 T4，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 4.0 秒

空间限制： 512 MB

题目背景

西西艾弗岛上的西埃斯公园正在准备 5202 年的月票发行工作。

题目描述

西埃斯公园发行的月票编号为由小写字母（a-z）和井号（#）组成的字符串：

月票编号的字符串长度为 $n$ ，记作位置 $1$ 到位置 $n$ ；
月票编号中有且仅有 $m$ 个位置固定为井号；
其余 $n-m$ 个位置可以自由填写 $26$ 种小写字母。

为了显示月票的发行方为西西艾弗岛上的西埃斯公园，可发行的月票编号必须满足如下要求：

ccf 和 cspark 两种子串均出现至少一次（子串为连续的若干字符）；
至少存在一对 ccf 和 cspark，满足 ccf 在 cspark 前面（左侧）出现。

例如，当字符串长度为 $16$ 、存在一个位置为 $10$ 的井号时，以下编号的月票均为可发行的：

ccfcspark#ccfcsp
ccfcspark#cspark
csparkccf#cspark
ccsparccf#cspark

当然，可发行的月票远不止上面四种。

你的任务就是帮助西埃斯公园计算：总共能够发行多少张不同的月票？两张月票不同当且仅当两张月票的编号至少有一处位置的字符不同。

答案可能很大，你只需要求出其对 $998244353$ 取模的结果即可。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $n$ 和 $m$ ，表示月票编号的字符串长度和井号的数量。

接下来一行包含 $m$ 个正整数 $a_1,a_2,\cdots,a_m$ ，表示指定的井号位置。

输出格式

输出到标准输出。

输出一个整数，表示可发行月票总数对 $998244353$ 取模的结果。

input1

1
212 1
11

output1

样例 1 解释

在本样例中，受井号限制 ccf 和 cspark 只能分布在前面 $10$ 个字符中，因此二者各自只能出现一次，具体有以下三种情况：

ccf 填写在 $1\sim 3$ 的位置，cspark 填写在 $4\sim 9$ 的位置；
ccf 填写在 $1\sim 3$ 的位置，cspark 填写在 $5\sim 10$ 的位置；
ccf 填写在 $2\sim 4$ 的位置，cspark 填写在 $5\sim 10$ 的位置。

上述三种情况中，都有另外两个可以填写任意小写字母的空余位置。因此可发行的月票总数为 $3\times 26^2=2028$ 。

input2

1
214 2
4 8

output2

样例 2 解释

在本样例中，cspark 只能填写在 $9\sim 14$ 的位置，此时 ccf 只要填写在 $1\sim 3$ 或者 $5\sim 7$ 任意一处即可。

将 ccf 填写在一处后，另外一处的三个位置便可以填写任意小写字母；但请注意，两处均填写 ccf 的月票会被重复计算一次。

因此可发行的月票总数为 $2\times 26^3-1=35151$ 。

input3

1
216 1
10

output3

1474661742

子任务

对于所有数据，保证 $9\le n\le 10^9,1\le m\le \min(n,10^6),1\le a_1<a_2<\cdots < a_m\le n$ 。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务 1（30 分）：保证 $n\le 15$ ；
子任务 2（30 分）：保证 $n\le 10^5$ ；
子任务 3（30 分）：保证 $n\le 10^9,m\le 10^4$ ；
子任务 4（10 分）：无特殊限制。

提示

可能存在无可发行月票的情况，此时的计算结果为 $0$ 。但是对所有测试点皆输出 $0$ 不会得分。

月票发行

目录

形式化题目

思路

全局三状态

段内计数

段间转移

代码

复杂度

总结