+++
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](https://acm.hdu.edu.cn/showproblem.php?pid=7013)

## 题意

给定 $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](https://acm.xidian.edu.cn/problem.php?id=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](https://acm.hdu.edu.cn/showproblem.php?pid=7015)

## 题意

给定一个字符串 `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$ 个字符中有多少不同的函数：

```c++
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;
}
```

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

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