简述
时隔一年之后再学一个新的筛法是不是没救了啊。
这套题里面质量最好的题（虽然跟 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;
}
大概就是要求一个子序列，使得在所有变化中始终长度最长。我们可以考虑分治，讨论变化的点的左右位置，然后用树状数组维护一下即可。
// P4093.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 200;
int n, m, ai[MAX_N], mx[MAX_N], mn[MAX_N], dp[MAX_N], nodes[MAX_N], idx[MAX_N];
inline int lowbit(int x) { return x & (-x); }
void update(int x, int d)
{
for (; x <= n; x += lowbit(x))
nodes[x] = max(nodes[x], d);
}
void clear(int x)
{
for (; x <= n; x += lowbit(x))
nodes[x] = 0;
}
int query(int x, int ret = 0)
{
for (; x; x -= lowbit(x))
ret = max(ret, nodes[x]);
return ret;
}
void solve(int l, int r)
{
if (l == r)
return (void)(dp[l] = max(dp[l], 1));
int mid = (l + r) >> 1;
solve(l, mid);
for (int i = l; i <= r; i++)
idx[i] = i;
sort(idx + l, idx + mid + 1, [](const int &a, const int &b) { return mx[a] < mx[b]; });
sort(idx + mid + 1, idx + r + 1, [](const int &a, const int &b) { return ai[a] < ai[b]; });
for (int i = mid + 1, ptr = l; i <= r; i++)
{
while (ptr <= mid && mx[idx[ptr]] <= ai[idx[i]])
update(ai[idx[ptr]], dp[idx[ptr]]), ptr++;
dp[idx[i]] = max(dp[idx[i]], query(mn[idx[i]]) + 1);
}
for (int i = mid + 1, ptr = l; i <= r; i++)
while (ptr <= mid && mx[idx[ptr]] <= ai[idx[i]])
clear(ai[idx[ptr]]), ptr++;
solve(mid + 1, r);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &ai[i]), mx[i] = mn[i] = ai[i];
for (int i = 1, x, y; i <= n; i++)
scanf("%d%d", &x, &y), mx[x] = max(mx[x], y), mn[x] = min(mn[x], y);
solve(1, n);
int ans = *max_element(dp + 1, dp + 1 + n);
printf("%d\n", ans);
return 0;
}
算是个简单题吧。
首先列个暴力式子：
\[ \sum_G \sum_{i = 1}^n d_i^k \]
发现很不现实。我们考虑把点拆开来考虑，因为全集里面可以直接独立的来算。考虑某个点度数为 \(x\) 的方案数，就变成了：
\[ n \sum_{x = 0}^{n – 1} x^k f(x) \]
其中 \(f(x)\) 代表的是一个图某个点的度数为 \(x\) 的方案数。其实稍微思考下就知道，我们可以把这个点剥离出来，强制连边之后再生成一个图即可：
\[ \begin{aligned} f(x) &= {n – 1 \choose x} 2^{n – 1 \choose 2} \\ ans &= n \sum_{x = 0}^{n – 1} x^k {n – 1 \choose x} 2^{n – 1 \choose 2} \\ &= n2^{n – 1 \choose 2} \sum_{x = 0}^{n – 1} x^k {n – 1 \choose x} \end{aligned} \]