Znzryb's Blog

manacher

马拉车算法其实和这个 kmp，z 函数还是有异曲同工之妙的。

我们维护一个最远的回文串边界，记为 r。

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

// refer cp algorithm
// https://cp-algorithms.com/string/manacher.html
// AC https://acm.hdu.edu.cn/contest/view-code?cid=1180&rid=12078
// 2026-03-21 把不用的宏给删掉了
vector<ll> manacher_odd(string s){
    int n=SZ(s);
    s='$'+s+'^';
    vector<ll> p(n+2);
    ll l=0,r=1;     // (l,r) 是开区间，其内部是这个回文子串
    for(int i=1;i<=n;++i){
        // 保底半径
        p[i]=min(r-i,p[l+r-i]);
        // 暴力外扩
        while (s[i-p[i]]==s[i+p[i]]) { // 因为有哨兵，永不越界
            p[i]++;
        }
        if(i+p[i]>r){
            l=i-p[i],r=i+p[i];
        }
    }
    return vector<ll>(p.begin()+1,p.end()-1);
}
vector<ll> manacher(const string &s){
    string t;
    for(auto c:s){
        t+='#';     // 千万不要    t+='#'+'c'
        t+=c;
    }
    t+='#';
    auto res=manacher_odd(t);
    return vector<ll>(res.begin()+1,res.end()-1);
}
// 返回的radius要除以二，i&1的位置是空格，偶数长度回文串，0-based

可以这样子使用这个差分，得到以该点起点的的这个回文串的数量。

1
2
3
4
5
6
7
8
9
10
11
12

vector<ll> ps = manacher(s);
vector<ll> cntS(szs + 3);
for (int i = 0; i < SZ(ps); ++i) {
    ll r = ps[i] / 2;
    if (r == 0) {
        continue;
    }
    ll pos = i / 2;
    cntS[pos - r + 1]++;
    cntS[pos + 1]--;
}
partial_sum(all(cntS), cntS.begin());

隔板法的思想就是，把 a 插入 d 个空格当中，换为给 a 加上 d-1 个隔板。

为什么是这个公式呢？不难发现，我们可以把 a 个球和 d-1 个隔板放在一起进行乱排，模拟可以为 0 的情况。

$C_{N+K-1}^{K-1}=C_{N+K-1}^{N}$ 我认为前面一个更容易理解。

要求这个题目要求 $x_{i}\geq a_{i}$，也可以使用这个插板法。

The 21st Hunan Provincial Collegiate Programming Contest——2025-湖南省赛-I. Tearing Paper

这道题目，隔板法是有效的，是因为隔板法其实是要求插入元素的这个顺序是不重要的，那么这道题目，细想之下，确实如此。

经过抽象以后，这道题目需要求解的内容如上。

不难发现，我们其实只关注这个 U R 之间的相对关系，说白了就是两个 U 之间隔了几个 R？只要这个不变，路径是不会改变的。

题目大意

题目描述
给定一个长度为 $n$ 的正整数序列 $a$。
求该序列中有多少个连续子段的和为素数。换言之，计算满足 $1 \le l \le r \le n$ 且 $\sum_{i=l}^r a_i$ 为素数的数对 $(l, r)$ 的数量。

输入格式
第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试用例的数量。
每个测试用例包含两行：
第一行为一个整数 $n$（$1 \le n \le 10^6$），表示序列的长度。
第二行为 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$，且单组测试数据内 $\sum a_i \le 10^6$），表示序列的元素。
保证同一个文件内所有测试用例的 $n$ 的总和不超过 $10^6$，所有测试用例的 $\sum a_i$ 的总和不超过 $10^6$。

输出格式
对于每个测试用例，输出一行一个整数，表示和为素数的子段数量。

样例

输入：

1
2
3
4
5

2
4
1 2 3 4
12
1 1 4 5 1 4 1 9 1 9 8 10

输出：

1
2

5
16

样例解释
在第一个样例中，满足条件的 $(l,r)$ 数对如下：
$l=1, r=2$：该子段的和为 $3$。
$l=2, r=2$：该子段的和为 $2$。
$l=2, r=3$：该子段的和为 $5$。
$l=3, r=3$：该子段的和为 $3$。
$l=3, r=4$：该子段的和为 $7$。

思路讲解

AC代码

1

心路历程（WA，TLE，MLE……）

题目大意

题目描述

在一个 $n \times m$ 的网格平面上，有一个关键区域。该区域是一个闭矩形，其四个顶点的坐标分别为 $(a,b)$、$(a,d)$、$(c,d)$、$(c,b)$，其中 $0 \le a < c \le n$ 且 $0 \le b < d \le m$。

现在会随机选择一条从 $(0,0)$ 到 $(n,m)$ 的合法路径。合法路径是指每一步只能向右（$x$ 坐标加 $1$）或向上（$y$ 坐标加 $1$）的格点路径。

这条路径必定会将整个平面分成“左上”和“右下”两部分（允许其中一部分为空）。我们关注的是该关键区域是否会被这条路径切断。如果整个闭矩形区域完全位于路径的同一侧（完全在“左上”部分或完全在“右下”部分），则称该关键区域保持“完整”；否则视为被路径切断。

求在所有等概率选择的合法路径中，关键区域保持“完整”的概率。答案需要对 $998244353$ 取模。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试用例的数量。

接下来每行代表一个测试用例，包含六个整数 $n, m, a, b, c, d$（$1 \le n \le 10^3$，$1 \le m \le 10^6$，$0 \le a < c \le n$，$0 \le b < d \le m$），其含义如题目描述所示。

输出格式

对于每个测试用例，单独输出一行一个整数，表示关键区域保持“完整”的概率对 $998244353$ 取模后的结果。

样例输入

1
2
3
4

3
3 3 1 1 2 2
3 3 0 0 3 3
3 3 0 1 3 2

样例输出

1
2
3

1
299473306
199648871

样例解释

在第一个测试用例中，关键区域的大小为 $1 \times 1$。它永远不会被任何路径切断，因此保持完整的概率为 $1$。

在第二个测试用例中，关键区域的大小为 $3 \times 3$，即覆盖了整个纸张。由于除非其中一部分为空，否则撕裂路径总是将纸张分成两个非空部分，因此关键区域保持完整的概率为 $\frac{2}{20}$，即 $\frac{1}{10}$。对 $998244353$ 取模后输出 $299473306$。

在第三个测试用例中，关键区域保持完整的概率为 $\frac{8}{20}$，即 $\frac{2}{5}$。对 $998244353$ 取模后输出 $199648871$。

思路讲解

完全理解隔板法（stars and bars）（插板法应用的特征）

我觉得是类似于这样子思考。

隔板法的思想就是，把 a 插入 d 个空格当中，换为给 a 加上 d-1 个隔板。

AC代码

1

心路历程（WA，TLE，MLE……）

https://qoj.ac/contest/2646