+++ date = "2021-08-03T19:45:00+08:00" draft = false tags = [] title = "2021 杭电多校 (“中超联赛”) 第五场" authors = ["xry111"] +++

大概过程：

• 开场签 1006，同时王老师签了 1003
• 然后写 1007 错了 $114514$ 发，最后王老师改对了
• 然后 1002 一开始觉得是压缩存储矩阵然后快速幂，发现事 $\mathcal{O}(n^4 \log L)$ 的。突然发现他有个傻了吧唧的条件是 $n | (M - 1)$，那就是裸的 Fourier 变换题了…… 结果被卡常数，加了个预处理单位根的幂才过。
• 最后他俩在那自闭 1005 和 1009 不知道在干啥，我自闭 1004， 最后没思路了开始用内嵌汇编乱卡，赛后卡过了

String Mod

题意

给定 $n$, $L$, $k$，设 $a^n = b^n = 1$，求

$$(a + b + (k - 2))^n$$

中 $a^i b^j$ 项的系数模 $M$。保证 $1 \leq n \leq 500$，$n | (M - 1)$。

做法

一开始想压缩存储一个矩阵然后快速幂，发现乘法的复杂度事 $\mathcal{O}(n^4)$， 肯定过不了。然后突然发现一个怪异的条件 $n | (M - 1)$，这就意味着在模 $M$ 意义下一定有 $n$ 阶单位根， 再回头一看之前那个“矩阵乘”其实就是二维循环卷积， 那么傻子都知道肯定是 Fourier 变换以后直接快速幂一下再变回去了 (类似 XDOJ 1085， 只不过变成了二维)。

因为 $n$ 才 $500$，不需要写 FFT (这个模数写 FFT 得看 $114514$ 篇论文， 然后写 $1919810$ 行)，直接用 DFT 的定义 $\mathcal{O}(n^2)$ 地硬算每行每列就行了，这样二维 DFT 的复杂度就是 $\mathcal{O}(n^3)$。 因此总的复杂度是 $\mathcal{O}(n^3 + n^2 \log L)$。

本题需要对于每组读入预处理单位根的幂，否则会卡常。

Another String

题意

给定一个字符串 S 和一个数 $k$，对于每个 $i$， 令 $U$ 是 S[:i] 所有子串的集合，$V$ 是 S[i:] 所有子串的集合，求

$$\sum_{u \in U} \sum_{v \in V} [|u| = |v|] \left [\sum_i [u(i) \neq v(i)] \leq k \right ]$$

做法 (?)

很容易想到一个 $\mathcal{O}(n^3)$ 的做法： 枚举 $a$, $t$, $b$，如果 s[a:a+t] 和 s[b:b+t] 中字符不同的位置不超过 $k$ 个，就要对 $[a + t, b]$ 中的每个 $i$ 答案都加 $1$。因为只有一次查询，不用写 xx 树，最后求个前缀和即可。

本地测了一下发现跑 $3$ 秒多，看了一下上面那个 $[a + t, b]$， 发现对于固定的 $a$ 和 $b$，合法的 $t$ 肯定是从 $1$ 开始的一段连续的整数 (除非没有合法的 $t$)。这样，如果我们对于特定的 $a$ 和 $b$ 能够较快地求出最大的合法的 $t$，然后把前缀和做两次，就能解决这个问题。 最后实在没办法了，用汇编写了个求 $16$ 个字符中有多少不同的函数：

static inline int n_mismatch(const char *a, const char *b)
{
	int r;
	static const long x = 1;
	__asm__(
		"vmovdqu	(%1), %%xmm0\n"
		"vpcmpeqb	(%2), %%xmm0, %%xmm0\n"
		"vpcmpeqd	%%xmm1, %%xmm1, %%xmm1\n"
		"vpxor	%%xmm1, %%xmm0, %%xmm0\n"
		"vpmovzxbw	%%xmm0, %%ymm0\n"
		"vextracti128	$1, %%ymm0, %%xmm1\n"
		"vpbroadcastd	%3, %%ymm2\n"
		"vpmovzxwd	%%xmm1, %%ymm1\n"
		"vpand	%%ymm2, %%ymm1, %%ymm1\n"
		"vpmovzxwd	%%xmm0, %%ymm0\n"
		"vpand	%%ymm2, %%ymm0, %%ymm0\n"
		"vpaddd	%%ymm1, %%ymm0, %%ymm0\n"
		"vextracti128	$1, %%ymm0, %%xmm1\n"
		"vpaddd	%%xmm1, %%xmm0, %%xmm0\n"
		"vpshufd	$238, %%xmm0, %%xmm1\n"
		"vpaddd	%%xmm1, %%xmm0, %%xmm0\n"
		"vpshufd	$85, %%xmm0, %%xmm1\n"
		"vpaddd	%%xmm1, %%xmm0, %%xmm0\n"
		"vmovd	%%xmm0, %0"
		: "=r"(r)
		: "r"(a), "r"(b), "m"(x)
	);
	return r;
}

赛后才写完卡了过去…… 正解是啥我暂时蒙在鼓里。

原来第一维枚举 $b - a$ 然后就能尺取 $a$ 和 $t$ 了…… 我是傻逼。