2023.1-526互联

杂题

CF1085G Beautiful Matrix

比较自然的题。

首先发现总方案数就是 $n!\times f^{n-1}_n$，其中 $f_n$ 是错排数。也就是第一行任意确定一个排列，接下来每一行都是个错排。然后我们相当于给了一个方案，问多少个方案的字典序比它小。

第一行就不同的情况是平凡的。然后我们接下来认为第一行的方案和给出的方案一致。

如果我们枚举第一次不同的行，那就是在做 $n$ 次下列的问题：

给出排列 $p$ 和它的错排 $q$，问有多少个 $p$ 的错排 $q'$ 字典序比 $q$ 小。

朴素的想法是：枚举 LCP 长度 $i$ 和 $q'_{i+1}$，此时的方案数相当于是一个局部错排问题：也就是长度为 $a+b$ 的排列，对于 $i\le a$ 要求 $p_i\neq i$，对于 $i\gt b$ 问要求，询问 $p$ 的数量。记这个数目为 $F(a,b)$。

先考虑 $F(a,b)$ 的转移：类似原始的错排问题的考虑方式，先特判平凡的 $F(a,0)$ 和 $F(0,b)$。然后我们考虑分类讨论 $p_1\le a$ 和 $p_1\gt b$ 即可。于是可以 $O(n^2)$ 地预处理出 $F$。

然后我们得到了一个 $O(n^3)$ 的做法，显然可以进一步优化：因为我们枚举 $q_{i+1}'$ 的时候，其实仅关注其是否在 $a$ 个 $p_i\neq i$ 的约束位置里，所以如果我们能计算出这样的 $q_{i+1}'$ 的数目就结束了。而显然也可以在枚举 LCP 的过程中用树状数组维护出来。这样就在 $O(n^2\log n)$ 的时间内解决了本题。

代码

分层图

找不到出处。

一个 $m$ 行 $n$ 列的矩阵。满足：

同一行的任意两点间有连边。

同一列的相邻两点间有连边。

求：这张图的哈密顿回路数量。$\mod 10^9+7$。

$n\le 500,m\le 10^4$。

我们考虑暴力一些的做法：直接从上到下扫描一个哈密顿回路。可以发现我们考虑完了前 $i\lt n$ 行以后，观察那些第 $i$ 行和第 $i+1$ 行的连边，有一些是 $i\rightarrow i+1$ 的，有一些是 $i+1\rightarrow i$ 的，两者数目应该相同且非零。于是我们可以设 $f(i,x)$ 表示考虑完了 $\le i$ 的行，此时留下 $x$ 个插头的方案数。

计算出 $f(m-1,x)$ 后，容易计算最后一行对应的方案数并且计算答案。

$f(1,x)$ 也是容易计算的。然后我们考虑 $f(i,x)\rightarrow f(i+1,y)$ 的转移。显然系数和 $i$ 无关，因此我们可以转而用矩阵快速幂去维护，做到 $n^3\log m$ 的复杂度。现在就是要确定转移的系数。

但其实这里才是最复杂的地方：我们称第 $i$ 行伸出来的 $x$ 个插头是红色，第 $i+1$行伸出来的 $y$ 个插头是蓝色。你考虑每个蓝色插头都应该位于一对红色插头的内部（一对插头是，先从 $i$ 走到 $i+1$，再从 $i+1$ 走到 $i$ 的）。

而且注意到一对蓝色插头和一对红色插头还能重合，还可以是一端重合，另一端不重合。这就非常麻烦。。

考虑可以枚举一个 $k$：表示恰好有 $k$ 对红色插头内没有接任何蓝色插头。则我们至少要给这 $k$ 个空分配 $2$ 个数（对应了插头的两端）。然后我们把 $j$ 个蓝色插头分配给 $i-k$ 个红色插头。此时可以看成：先给每个蓝色插头分配 $2$ 个数，此时还剩下 $n-2(j+k)$ 个数，分配给共 $i+j$ 个空即可。比如：假如有 $2$ 个红色插头，$3$ 个蓝色插头。并且我们把前两个蓝色插头给到了第一个红色插头的组里。那么就是：第一个红色插头那边有 $3$ 个空，第二个那边有 $2$ 个空。如果第一个红色插头的左侧那个空没分配数，就说明红色插头的左侧，和蓝色插头的左侧是同一个数，右侧同理。这样就可以不重不漏地考虑到所有情况。

最后在 $f(1,x)$ 的初始化和最后 $f(m-1,x)\rightarrow ans$ 的部分有一些细节系数需要注意。不再赘述。

这个题可能还是很需要代码的：代码

2021 集训队互测 Imbalance

写起来让人有点汗流浃背。

对于 $k\le 22$ 我们暴力状压判掉，然后 $\frac{n}{k}$ 不会很大。

首先考虑，写成一个 $\lceil \frac{n}{k} \rceil$ 行，$k$ 列的矩阵。然后每一个位置填上 $0/1$。那你考虑就是：对于每个格子 $(i,j)$，考虑 $(i-1,j+1)\rightarrow (i-1,k)$ 以及 $(i,1)\rightarrow (i,j)$ 这 $k$ 个格子加起来不能为 $\frac{k}{2}$。于是我们先枚举前 $\lceil \frac{n}{k}\rceil-1$ 行的和，然后再一列一列地 dp，记录每一行当前的和。这样可以通过 $n\le 66$ 的部分分。

首先我们需要一个转化：注意到如果有两段长度为 $k$ 的，一个里 $0$ 的个数 $\le \frac{k}{2}$，另一个里 $\ge \frac{k}{2}$，则一定还存在一段 $=\frac{k}{2}$ 的。所以我们只用算：每一段里 $0$ 的个数都 $\lt \frac{k}{2}$ 的，以及每一段里 $0$ 的个数都 $\gt \frac{k}{2}$ 的即可。显然这两个是本质相同的问题。

令 $r=\lceil \frac{n}{k} \rceil$，则其上界为 $5$。然后，我们考虑把前缀和 $s_i$ 写在 $i\bmod k$ 的位置，这样我们就有 $r$ 条折线。

我们的约束实质上是考虑编号相邻的两条折线：然后任意选中一个 $x$，然后他们在 $x$ 处的点值差应该小于 $k'=\frac{k}{2}$。然后我们不妨把第 $i$ 条折线整体向下移动 $(i-1)k'$，这样约束就变成了第 $i$ 条直线严格在第 $i-1$ 条直线的下方。我们 $(k')^{r}$ 地枚举每一行的前缀和，然后就确定了 $r$ 条路径的起点与终点，做不相交路径计数。

$S$ 的给出实际上限制了第一条路径的前 $m$ 步，不妨先来考虑 $m=0$ 的情况。还有一个细节是最后一行因为有残缺所以终点并不位于 $x=k$ 处。这实质上带来一个问题：就是当所有终点都在 $x=k$ 处的时候，想让路径不相交就只能让第 $i$ 个起点和第 $i$ 个终点匹配。但是此时我们就可以违反这个事情：比如假设有两行，那可以第一个起点和第二个终点匹配，第二个起点从下面绕上去和第一个终点匹配。因此我们需要强制 ban 掉最后一个终点右下方的所有点。然后路径数就不方便用组合数统计了，需要跑一个简单的 dp。

$m\gt 0$ 就是第一条路径的起点也被钦定，我们故技重施：把这个起点左上方的点也 ban 掉即可。

复杂度的话，大概是 $O((k')^{r}\times r^3)$，还有一个 dp 的复杂度。我们需要提前最外层枚举最后一行的答案然后跑出 dp 后再开始 dfs，这里一个比较松的分析是 $O(n^4)$ 的，足够通过了。

代码

2021 集训队互测愚蠢的在线法官

很有启发性的一个题！

本题有非常多的理解角度，但我认为官方题解给出的角度很有启发性，我也主要从它的角度来写一下理解。

一些比较平凡的事情：若 $A_i$ 有重复元素则不满秩因此行列式为 $0$；交换两个 $A_i,A_j$，因为同时交换了一行一列所以行列式不变。因此我们不妨认为 $A_i$ 按照 dfs 序给出。

注意到一个看上去非平凡的部分分是 $A_i=i$。因此来考虑研究此时的情形。

可以手玩出：菊花的答案是 $v_1\prod_{i\ge 2}(v_i-v_{1})$，链的答案是 $v_1\prod_{i\ge 2}(v_i-v_{i-1})$，加以对于一些小的树的手玩可以发现规律：令 $w_i:=v_{i}-v_{fa_i}$，则答案就是 $\prod w_i$。

一个形式化的证明也非常精彩：

令 $i\mid j$ 表示 $i$ 是 $j$ 的祖先（可以有 $i=j$）。然后 $v_{LCA(i,j)}$ 可以写成：$\sum_{k}[k\mid i][k\mid j]w_k$。这显然是一个矩阵乘法的形式：$A(i,j)=\sum_{k}B(i,k)B(k,j)$。因此，构造矩阵 $B,C$：

\[B_{i,j}=[j\mid i]w_k \\ C_{i,j}=[i\mid j] \]

然后，就有 $A=B\times C$。对于方阵而言，众所周知 $|A|=|B|\times |C|$。

显然 $|B|$ 和 $|C|$ 都是下三角矩阵，有：$|B|=\prod_{i}w_i,|C|=1$，因此就有 $|A|=\prod_{i=1}^{w_i}$。

有趣的是，这个证明可以非常容易地来做 $\gcd $ 矩阵的行列式，也就是 $|A_{i,j}=v_{gcd\{i,j\}}|$。这里暂且不走远

对于 $k\lt n$ 的一般情况，考虑依然可以仿照上面的形式：构造出 $k\times n$ 和 $n\times k$ 的矩阵 $B,C$ 相乘：

\[B_{i,j}=[j\mid A_i]w_j\\ C_{i,j}=[i\mid A_j] \]

依然有 $A=B\times C$，但由于 $B,C$ 不是方阵，我们无法用上面的方式计算行列式。

Cauthy-Binet 公式给出了此时的一个拓展：

\[|A|=\sum_{S\subseteq\{1,2,...,n\},|S|=k}|B_{\{1,2,...,k\},S}|\times |C_{S,\{1,2,...,k\}}| \]

考虑其组合意义：我们称 $a_1,a_2,...,a_k$ 为左部点，然后我们相当于又选中了一个大小为 $k$ 的点集，称为右部点（两个集合可以有交）。然后我们考虑所有左部点和右部点的匹配方案（一个左部点 $u$ 能匹配到右部点是 $v$ 当且仅当 $v\mid u$）。显然每个匹配方案都对应了一个排列 $\sigma$，令 $|\sigma|$ 是其逆序对数，然后一个匹配方案的权值是 $(-1)^{|\sigma|}$ 乘上右部点的 $w$ 之乘积。

考虑我们可以设 $dp(u,x)$ 表示 $u$ 子树内还有 $x$ 个左部点的答案和。但是这样一来复杂度爆炸二来干不掉逆序对的影响。一个事情是如果 $x\ge 2$ 那么你发现，子树内两个左部点，和往上的两个右部点都能匹配，你交换一下权值不变，但是逆序对奇偶性改变。然后可以感知到这个是能够抵消掉的。所以我们强制要求选出的右部点只能有一种匹配方式。

那就设 $dp(u,0/1)$ 就好了，转移的时候根据 $u$ 是否为左部点进行讨论，时间复杂度 $O(n)$。

代码

zjk 大神也有一个深刻的理解方式，有空学习了补充一下。

2021 集训队互测抽奖

神题。

首先需要知道 K-FWT 的存在：一个常用的做法是，考虑原本的卷积的实质：依次考虑每个维度，然后在枚举其他位的构成，此时有一个长度为 $k$ 的数组，我们在这一位上做长度为 $k$ 的循环卷积即可。

而长度为 $k$ 的循环卷积可以用 DFT 来实现：事实上 DFT 的过程就是在做循环卷积，不过平常我们会让 $n$ 足够大使得循环卷积变成了线性卷积。我们这里的 DFT 并不需要用到 FFT 那种神秘的分治处理，直接暴力 $O(k^2)$ 地得到 $1,\omega_{k}^{1},\omega_{k}^{2},...,\omega_{k}^{k-1}$ 处的点值，将其替换掉原本的数组即可。

这样，我们要做枚举 $n$ 个数位，每次需要 $k^{n-1}$ 地枚举其它数位的表示，然后 $k^2$ 地暴力 DFT。因此时间复杂度是 $O(nk^{n+1})$ 的。

上面的都是基础的 K-FWT 内容。原始的 FWT 存在一个 $f(S)\rightarrow f'(T)$ 的形式化表达，我们这里也存在一个，从原数组 $f$ 到 FWT 结果 $f'$ 的形式化表达：

\[f(S)\rightarrow f'(T) : \prod_{i=1}^{n}\omega_{k}^{S_iT_i} \]

换言之，$f$ 数组的第 $S$ 项，给 $f'$ 数组的第 $T$ 项的贡献系数是一个 $k$ 次单位根，这个单位根的上指标就是 $\sum_{i=1}^{n}S_iT_i$，也就是 $S\cdot T$（这里把 $S,T$ 看成了一个 $n$ 维向量）。

然后考虑这一题的做法：我们直接用长度为 $n$ 的三进制数来表示整个状态。令 $c_1(S)$ 是 $S$ 的三进制表示里 $1$ 的个数，类似定义 $c_2(S)$。

那么，从 $f(i,S)$ 转移到 $f(i+1,T)$ 的系数是多少？令 $X:=T\ominus S$（$\ominus$ 定义为不退位减法），则显然方案数就是 $\sum_{i=1}^{m}[c_1(x)=a_i\land c_2(x)=b_i]$。

令 $f(S) := \sum_{i=1}^{m}[c_1(S)=a_i\land c_2(x)\land b_i]$，然后定义乘法是三进制异或卷积。则我们要求的就是 $f^k$ 的 $O(n^2)$ 条信息：对于每个 $i+j\le n$，去计算所有满足 $c_1(S)=i\land c_2(S)=j$ 的 $f^k(S)$ 的和。

直接 $n3^{n+1}$ 地去暴力做 3-FWT 显然是不可行的，我们考虑这样一个事情：就是如果 $c_1(x)=c_1(y)\land c_2(x)=c_2(y)$，则非常显然有 $f(x)=f(y)$。

于是我们可以用 $O(n^2)$ 个二元组 $(i,j)$ 来描述整个 $f$ 的信息：对于一对 $(i,j)$，我们令 $S$ 是前 $i$ 位都是 $1$，接下来的 $j$ 位都是 $2$，其余位都是 $0$。然后令 $f(i,j) := f(S)$（你也可以任选另外一个你喜欢的 $S$，但是这样选比较方便）。显然我们要求的就是所有 $f^k(i,j)\times \dbinom{n}{i,j,i-j-j}$ 的信息。把这个数 $S$ 称作 $key(i,j)$。

并且，根据上面 $f\rightarrow f'$ 的表达方式，可以发现我们也可以用同样的方式，用 $O(n^2)$ 个二元组 $(i,j)$ 来描述整个 $f'$ 的信息。那么我们只需要完成 $f\rightarrow f'$ 的步骤，然后直接令 $f'$ 的每个元素 $f'(i,j):=f'(i,j)^{k}$，最后再 IFWT 回去即可。压力就来到了 $f\rightarrow f'$ 的步骤。

最暴力的想法是：直接枚举一个 $f(i,j)$ 给到 $f'(x,y)$ 的贡献。令 $T := key(i,j),S := key(x,y)$。也就是暴力枚举 $T$，然后考虑 $f(T)\rightarrow f'(S)$ 的贡献。

此时，直接逐位考虑 $T$ 的取值，并且状态中记录当前的 $i=c_1(T)$ 和 $j=c_2(T)$，然后维护此时的 $\sum \omega^{S\cdot T}$ 即可。这实际上是一个背包的过程，将其记作 $G(i,j)$。然后最后 $G(i,j)\times f(i,j)$ 贡献到 $f'(S)$ 上即可。你发现这个过程中，我们已经考虑掉了所有和 $T$ 属于同一等价类的数给 $S$ 的贡献。换言之这个 dp 其实是算出了“一个等价类”去给一个确定的“数”的贡献。

然后这就是一个 $O(n^5)$ 的做法。瓶颈在于对于每一对 $(x,y)$ 我们需要 $O(n^3)$ 的背包去得到共 $O(n^2)$ 个 $G_{x,y}(i,j)$ 的信息。考虑 $G_{x,y}$ 其实可以看成：$x$ 个 $1$ 类物品，$y$ 个 $2$ 类物品，$n-x-y$ 个 $3$ 类物品卷积（背包）的结果。因此可以从 $G_{x,y-1}$ 出发，$O(n^2)$ 地推得 $G_{x,y}$ 的信息：我们撤销掉一个 $3$ 类物品，再加入一个 $2$ 类物品即可。类似地也能够从 $G_{x-1,y}$ 出发，$O(n^2)$ 地推得 $G_{x,y}$ 的信息。总时间复杂度是 $O(n^4)$ 的，需要注意常数的效率。

代码

正睿24省选十连 Round4 B

题意：

给出一个 $n\times n$ 的黑白矩阵，求有多少个非空子矩阵满足：可以用若干 $2\times 2$ 的地毯不重不漏地恰好覆盖所有白色格子。$n\le 300$。

很妙的子矩阵计数。

先考虑猜点充要条件：比如容易猜按列扫描，每一列的白色连通段长度都为偶数；然后对行扫一遍也满足。然后发现一个很强的 hack 是 $4\times 4$ 的矩形挖掉 $4$ 个角。

修一下：本质就是说我们要区分那些，作为 $2\times 2$ 第一列和第二列白格子。在上面的 hack 里：如果按列扫描，显然第一列的两个格子都是作为 $2\times 2$ 的第一列，然后 $(2,2)$ 和 $(3,2)$ 就应该作为第二列；然后 $(1,2)$ 和 $(4,2)$ 就会作为第一列。然后这个时候因为长度成奇数就矛盾了。然后就能干掉这个 hack。

我们整理一下：按列扫描，然后扫到一个白色格子的时候：如果他的左侧也是白色格子，且这个格子是第一列，那么当前的格子就应该与之合并，作为第二列。否则，这个白色格子应该和右侧的合并，我们到右侧的时候再去处理即可。如果扫到一个黑色格子，而且其左侧是位于第一列的白色格子，那么就不合法。并且要求：任意列上，那些被要求在第一列的格子，构成的每个连续段长度都是偶数。

我们用 $0/1$ 来维护扫描过的白色格子，要求是在第一列还是第二列。为 $1$ 表示其在第一列，为 $0$ 表示其在第二列。然后上面的内容就等价于：扫到白色格子的时候，如果左侧是白色格子，该白色格子的颜色就是其取反，否则为 $1$。然后为 $1$ 的白色格子右侧必须也是白色格子，且每一列上为 $1$ 的白色格子的连续段长度都得是偶数。

现在考虑：枚举答案的左边界，从左往右枚举右边界。当确定左右边界后，我们尝试快速计算合法的上下边界 $[l,r]$ 的取值数：显然如果有一行出现不合法（为 $1$ 的格子右侧是黑格子），那么之后的 $[l,r]$ 都不能包含这一行；并且，右边界的$[l,r]$ 范围内不应有为 $1$ 的黑格子。也就是相当于有一个“全局ban”和“暂时ban”，限制了这一列的 $[l,r]$ 不能包含的一些行。这是容易处理的。

第三个条件，也就是说，$[l,r]$ 和每一列的为 $1$ 的连续段都是偶数，这个条件可以用 xor hashing 来快速判定：我们给每一列的，每一个 $1$ 的连续段赋上一个随机权值 $w$，然后对于一个 $i\in [1,n]$，令 $f_i$ 是所有包含这个点的连续段的 $w$ 的异或和，则 $[l,r]$ 合法就等价于 $f_l\sim f_r$ 的异或和为 $0$。我们确定左右边界后，直接按照 $r$ 扫描线，使用哈希表/map来维护，即可做到 $O(n^3)/O(n^3\log n)$ 的复杂度。

代码

一个双序列划分问题

呃呃，我也不知道真正出处。

题意：

给出长度为 $n$ 的序列 $a$。对于一个序列 $b$，定义其权值为 $\sum_{i=1}^{|b|}\max_{j\le i}\{b_j\}$。试讲 $a$ 划分成两个子序列 $s,t$，最小化 $f(s)+f(t)$ 之和。$n\le 5\times 10^5,1\le a_i\le 10^9$。

这种双序列划分有比较经典的套路：假设我们考虑了 $1\sim i$ 的划分，考虑 $x=\max_{j\le i}b_j$，则总有一序列的当前前缀最大值为 $x$。令 $f(i,j)$ 表示说，另一序列的当前前缀最大值是 $j$ 的答案。考虑转移，令 $f:=f(i),g:=f(i+1),y=b_i$。然后我们用 $f(i)+b\rightarrow g(j)$ 来描述 $g(j):=\min\{g(j),f(i)+b\}$ 的转移。

讨论 $x$ 与 $y$ 的大小关系，容易得到转移：

$x\le y$ 时。

这种情况比较平凡，因为不管 $y$ 加到哪里都有贡献 $y$。有：

加入 $x$ 所在的序列：则 $\forall i,f(i)+y\rightarrow g(i)$。
加入 $i$ 所在的序列，则 $\forall i,f(i)+y\rightarrow g(x)$。

$x\gt y$ 时。

这种情况下会在转移系数有一些额外的讨论：

加入 $x$ 所在的序列，则 $\forall i,f(i)+x\rightarrow g(i)$。
加入 $i$ 所在的序列，则 $\forall i,f(i)+\max\{x,a_i\}\rightarrow g(\max\{i,a_i\})$。

由于一定有 $i$ 是某个 $a_j$（或 $0$），因此我们直接离散化即可，这样 $f$ 的大小就只有 $O(n)$。然后暴力实现上述转移容易做到 $O(n^2)$。考虑使用数据结构优化上述转移。

当 $x\le y$ 的是：我们实质上只需要支持对 $f$ 数组的三种操作：

全局加常数，单点取 $\min$，求前缀最小值。

这是很平凡的。而 $x\gt y$ 的时候我们需要更精细的研究这个过程：

首先我们需要算出 $f(\lt y)$ 的前缀最小值，用以单点更新 $g(y)$。然后，考虑应该是：对于 $i\lt y$ 和 $i\gt x$ 而言，我们做的是 $f(i):=f(i)+x$，对于 $i\in [y,x]$ 而言，我们做的是 $f(i):=f(i)+i$。因此我们的查询还是前缀最小值，但是新增了两个修改：

区间加常数，区间加下标。

到此时有广为人知的分块 + 维护凸包的做法，复杂度显然为 $O(n\sqrt n)$；也有广为人知的 KTT 做法，复杂度应该是 $O(n\log^2 n)$？但是 KTT 超纲，我们来点纲内做法，那么显然要利用这个题里操作的一些限制。

若有两个位置 $i\lt j$，且满足 $a_i\le a_j$，则我们说 $i$ 优于 $j$，并且排除 $j$。维护所有未被排除的位置的集合。则查询前缀 $\le p$ 的最优解，就是在这个集合里找到最大的 $\le p$ 的元素，并且查询该位置的值。

注意到我们容易在支持所有上述修改的情况下，$O(\log n)$ 地返回当前的某个 $f(i)$ 的值。因此查询单点值的复杂度可以接受，只要可以维护这个集合 $S$ 即可。

一次区间加常数不会改变这个区间内 $S$ 的形态；一次区间加下标只会让这个区间内的 $S$ 缩小（也就是一些位置被前面的人干掉了）。一次单点取 $\min$ 显然只会最多往 $S$ 里增加一个元素。唯一的问题是：考虑我们的 dp 过程，是两侧加 $x$ 中间加了 $i$。因此在 $[1,y)$ 和 $[y,x]$ 这部分里，可能会出现：$[1,y)$ 这里的一个 $f_i$ 本来能干掉一个 $[y,x]$ 里的 $f_j$，但是因为这里 $f_i$ 增加的多，所以导致它干不掉了。也就是 $S$ 的大小还会进一步变大。

但是理性分析一下：可以发现我们最多只会把位置 $y$ 加进去，$\gt y$ 的位置一定不会加进去。因为我们是有一步，把 $f_{1\sim y-1}$ 的最小值加上 $y$，和 $f_y$ 取 $\min$ 的操作，这个操作很关键：因为本来有个位置 $i\in [1,y)$ 满足 $i$ 由于 $z$ 的话，你注意到 $f_i+y$ 也一定由于 $f_z+z$，然后因为你把 $f_i+y$ 放在了位置 $y$ 上所以 $z$ 就肯定能被 $y$ 干掉。