简述
一般赛场上遇上计算几何的题一般都不难，而碰上了没学过就直接爆零。为了避免这样的情况，我决定好好学一遍计算几何的一些东西。
结果是学了一遍照样爆零。
最近的这一段时间状态非常的疑惑（虽然好像疫情开始之后状态就一直不佳），打正赛的时候频频翻车，不过平常训练的比赛中有时能获得小小的收获和自信，也一直维持了刷题的速度（也刷了很多些水题），Codeforces 的 Rating 也在向我希望的方向变化。这些变化是让我在这无聊的自我训练生活中比较开心的，然而有时也会迷失，无法确定自己的位置，或者是产生迷茫的感觉。
退役前的最后几场比赛被疫情压的很紧，而我感觉我的速度还是慢了。我感觉思维上的一些死结让我面对一些没有准备的情况直接翻车，但是我真的不是很清楚要怎么解开。这个月感觉基础的题目刷了很多，也有很多自己的思考，但是感觉思维上没有什么本质的进步，处于「能理解、印象深刻但是没法自然想到」的情况。也有可能是做题或者是比赛的时候还是不太认真罢了。
我的心态反而没有之前那么紧张了。无论结果怎样，我的在役时间肯定是在减少了。我希望能在仅有的一次竞赛经历中能收获我想收获的东西吧。信息学让我的高中生活丰富了很多，让我也体验到了很多难忘的感受。即使之后再无机会让 FZOI 恢复疫情之前的情况，但我也无奈的接受。时间这个东西真是令人畏惧。
当我开始对一些事情释然之后，很多问题真的就迎刃而解了。无论是 OI、多年的朋友还是说生活，心态真的可以改变很多东西。
我会继续过好每一天的。
这套题里面质量最好的题（虽然跟 BZOJ 的某题比较像）。
我们先考虑把所有的病毒串加到 AC 自动机里去，然后再考虑一个 DP 转移，设 \( dp[i][j] \) 为当前第 \(i\) 个字符匹配于自动机节点 \(j\) 上的方案数。发现数据范围很小，所以其实这个可以矩阵优化。建完 AC 自动机之后，我们针对 \(a_i = 0, 1, -1\) 算三个矩阵。算完这个之后用线段树来维护就可以了。（复杂度上天了）
实测矩阵乘法的时候剪枝可以快 10s 的样子。
这个题还蛮神仙的。主要的思路就是算三元组 \( (p_1, p_2, p_3) \)，满足 \( G(S(p_1, p_2)) = G(S(p_2, p_3)) = G(S(p_1, p_3)) = x \)。我们先考虑 \(G(S(p_1, p_2)) = x\) 的 \((p_1, p_2)\)。假设我们能把这些路径全部求出来，并把这个仅包含有向边 \( S(p_1, p_2) \) 的有向图的入度、出度算出来。如果能算出这种东西的话，发现直接乘法原理可以算出非法的三元组（合法的三元组是没法搞的，因为你还得算 \( (p_1, p_3) \) 的东西才能搞）。如果规定时间内能搞定这个入度出度之后，我们直接 \(\Theta(n)\) 算掉乘法原理那个。搞入度出度可以直接上点分治。
乍一看很难直接做，我们考虑从那个长度为 \(m\) 的串开始搞，发现每个 \(01\) 都对应的是一个不等式条件：
\[ a(s + i) + b < p \]
其中在 \(m\) 串的位置中为 \(i\)，在 \(S\) 中的位置为 \(s + i\)。列了这么多之后进行区间交，然后发现性质 \(\gcd(a, n) = 1\)，代表 \(ai \bmod n\) 是一一对应的，所以我们求最后的值的个数只需要减去 \([n – m + 1, n – 1]\) 内符合条件的数即可。
// P3589.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 200;
int n, a, b, p, m, ltot;
char str[MAX_N];
pair<int, int> limits[MAX_N << 2];
void create(int l, int r)
{
if (l <= r)
limits[++ltot] = make_pair(l, r);
else
limits[++ltot] = make_pair(l, n - 1), limits[++ltot] = make_pair(0, r);
}
int main()
{
scanf("%d%d%d%d%d%s", &n, &a, &b, &p, &m, str);
int ans = 0;
for (int i = 0; i < m; i++)
if (str[i] == '0')
create((p + n - 1LL * i * a % n) % n, (0LL + n - 1 - 1LL * i * a % n) % n);
else
create((n - 1LL * i * a % n) % n, (p + n - 1LL * i * a % n - 1) % n);
for (int i = 1; i < m; i++)
create((0LL + b + n - 1LL * a * i % n) % n, (0LL + b + n - 1LL * a * i % n) % n);
sort(limits + 1, limits + 1 + ltot);
int tmp = -1;
for (int i = 1; i <= ltot; i++)
{
if (limits[i].first > tmp)
ans += limits[i].first - tmp - 1, tmp = limits[i].second;
else
tmp = max(tmp, limits[i].second);
}
printf("%d\n", ans + n - 1 - tmp);
return 0;
}