就这？思博题。
总觉得做过啊。答案很显然跟字符无关，我们需要固定最左边的子序列，然后枚举最后一位，得出结论（子序列 \(T\)、目标串长 \(n\)）：
\[ ans = \sum_{i = |T|}^n 25^{i – |T|} \times 26^{n – i} {i – 1 \choose k – 1} \]
考虑把 \(n\) 提出来：
\[ ans = 26^n \sum_{i = |T|}^n 25^{i – |T|} \times 26^{-i} {i – 1 \choose k – 1} \]
发现一个重要性质：\(\sum |T| \leq 10^5\)，所以对于不同的 \(|T|\)，最好情况下个数为 \(\Theta(\sqrt{n})\)。那么既然 \(n\) 可以被独立出来，那么最后复杂度就是 \(\Theta(|T|\sqrt{n})\)。
Continue reading →先考虑莫比乌斯反演？
\[ \begin{aligned} ans &= \sum_{i = 1}^n \sum_{j = 1}^n f(\gcd(i, j))^k \\ &= \sum_{d = 1}^n f(d)^k \sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) = d] \end{aligned} \]
经典化简：
\[ \begin{aligned} ans &= \sum_{T = 1}^n \lfloor \frac{n}{T} \rfloor^2 \sum_{x|T} \mu(x) f(\frac{T}{x})^k \end{aligned} \]
我们可以对这个 \(\lfloor \frac{n}{T} \rfloor^2\) 进行整除分块，所以问题的重心转移到了求后面那个 Dirichlet 卷积的前缀和身上。
Continue reading →
乍一看很难直接做，我们考虑从那个长度为 \(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;
}