2021 杭电多校 (“中超联赛”) 第五场

大概过程:

  • 开场签 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$ 了…… 我是傻逼。

Xi Ruoyao
Xi Ruoyao
PhD Student

Retired from ICPC, now a PhD student and an assistant ICPC coach (with no salary).