1.12 模拟赛

A 一次函数

不难发现一个数真正重要的只有这个数中的连续段个数以及这个数最后一位是 $0/1$ 。

我们设 $f(x)$ 表示 $x$ 二进制表示下的连续段的个数。那么答案就是在

$\sum_{i=1}^n f(ai + b)$

的基础上再减去除开最后一个位置的奇数的个数，因为这些数会和下一个数的 $1$ 合并成一段。

这个东西怎么求？不难发现这是个 $\bmod a$ 不变的式子，而这题正好 $a$ 非常小。所以我们考虑求

$\sum_{i=1}^{an+b} [i \bmod a = 0] f(i) - \sum_{i=1}^{b} [i \bmod a = 0] f(i)$

我们考虑做一个数位 $dp$ ，设 $dp[i][j][0/1][0/1],wy[i][j][0/1][0/1]$ 分别表示当前在第 $i$ 个位，当前这个数 $\bmod a = j$ ，最后一次填的是 $0/1$ ，是否卡着上界的所有数的连通块个数的和以及方案数。

转移就用 $wy$ 取推 $dp$ 即可。

可以滚动一下第一维，于是时间复杂度 $O(a\log b)$ ，空间 $O(a)$ 。

场上漏掉了 $2 | n$ 且最后一个数是奇数的情况要少 $1$ 个，由于 subtask 获得了 $0$ 分的好成绩。

B 卡片

前两个操作以及给出任意一种方案让人联想到 2-sat 问题。但是直接建图肯定是不行的，第三个操作会导致连出很多边。

我们考虑把图拆成了 $a_0,a_1$ 表示 $a$ 是否被选。我们考虑一个 $a_1$ ，不难发现它通过 $3$ 操作连出去的边一定形成一个区间扣掉它自己。因为包含它的所有 $3$ 操作并起来肯定是一个区间。

一种比较不动脑子的做法是直接线段树优化建图跑 tarjan ，但是可以做模拟 tarjan ，只需要求区间 dfn 为 $0$ 的所有数即可，这个可以拿线段树维护，同时再维护一下栈中的区间中的最小值。这样可以通过本题。

但是之前学到过另一种做 2-sat 的方法。对于所有连通块，我们任意选一个点，把它的值尝试设成 $0$ ，然后进行一次 dfs ，进行类似染色的操作，看看是否合法。如果不合法就尝试设成 $1$ ，如果还不合法就直接输出无解。过程中如果当前点是 $1$ 则需要找到这个点 $3$ 操作连出去的某个区间内是否存在已经选了 $1$ 的位置，如果有就是不合法的。这个可以使用一个 BIT 来判。然后还需要找到某个点后面第一个非 $0$ 的位置 dfs 下去，这个可以使用可撤销并查集维护。因为如果 $0$ 不合法尝试判 $1$ 的时候会需要撤销操作。这样就会非常好写。

两种做法复杂度均为 $O(n\log n)$ 。

这题场上过了，感觉加深了对 2-sat 的不同算法的理解。

C 匹配

考虑把询问串拆成三个部分，$pre,gap,suf$ 。其中 $gap$ 的长度我们钦定成 $k$ ，表示第一次失配出现在 $gap$ 的第一个位置。由于我们钦定了 $gap$ 的长度，我们可以 $O(|T|)$ 枚举这个串来对于 $pre,gap,suf$ 进行统计。

我们考虑 $pre,suf$ 的限制。我们可以对正反 $S$ 以及连上所有询问串建 $SA$ ，如果我们枚举了 $gap$ 的第一个位置所在的位置，那么限制就变成了反串都某个后缀和 $pre$ 的 $LCP$ 大于 $pre$ 的长度，以及正串的一个后缀和 $suf$ 的 $LCP$ 大于 $suf$ 的长度。由于 $k$ 是固定的，我们可以考虑把 $i,i+k$ 分别在反，正 $SA$ 上的位置作为两个坐标来做点，然后询问由于 $LCP \ge$ 某个长度的东西形成 $SA$ 上的一个区间，所以我们可以把询问变成一个矩阵数点。不难发现这个询问是可以离线下来做的。

然后由于 $gap[0] \neq s[p]$ 这个条件做起来很麻烦，直接按字母容斥掉也需要做 $26$ 遍问题，显得比较麻烦。有一种 djq 代码里面的很神仙的容斥，直接容斥成长度为 $k,k-1$ 的差。因为考虑对于一个 k-匹配 的情况，要计算的相当于是 $gap$ 中第一位任意的情况 减去 $gap$ 中第一位相同的情况。而考虑统计 $gap$ 中第一位相同情况的总和，本质上就是算 $gap$ 长度是 $k-1$ 的答案！于是直接做差即可得到正确的答案。

还有一种情况比较细节。

这种情况最毒瘤的地方在于，我们并不知道 $T$ 最后是否伸出了 $S$ 的范围。这种情况下如果 $T$ 并没有伸出 $S$ 的范围显然是合法的，如果伸出了就不合法。开始 lsj 为这种情况专门再写了一次二维数点，但是这样显得代码很长很复杂。我们可以先给 $S$ 后面加很多个 # ，让这个情况一定能匹配上，然后再枚举 $S$ 的最后 $|T|$ 位，暴力判断是否是一个不合法的情况。这样的复杂度依然是 $O(|T|)$ 的。

总复杂度 $O(|S| + \sum|T| \log |S|)$ 之类的。