ABC 杂题题解

jucason-xu / 2023-07-20 / 原文

A

首先，我们考虑 \(\sum_{i=l}^ra_i\equiv r-l+1(\bmod k)\) ，其实可以转化成 \(\sum_{i=l}^ra_i\equiv \sum_{i=l}^r 1(\bmod k)\)。

也就是 \(\sum_{i=l}^r(a_i-1)\equiv 0(\bmod k)\)，同时还要有 \(r-l+1\lt k\)。

考虑前缀和优化，\([l,r]\) 之和为 \(0\)，即 \(s_r\equiv s_{l-1}(\bmod k)\)。那么，我们记录当前所有的 \(s_i\)，从左往右找到所有和当前位置前缀和相等的左端点，用 map 记录，加入贡献。同时将左边已经超出长度要求的左端点从 map 中删除即可。

B

考虑先枚举 \(s=i+j+k\)，每次加入“和为 \(s\) 的蛋糕数量”，直到数量超过目标值，然后依次枚举 \(i\) 和 \(j\) 即可。

我们唯一的瓶颈是如何计算 \(1\le i,j,k\le n\) 且 \(i+j+k=s\) 的 \((i,j,k)\) 数量。考虑容斥。首先先不考虑 \(i,j,k\le n\) 的条件，利用插板法求出答案为 \(\binom{s-1}{2}\)。

然后减去有一个超过 \(n\) 的情况，我们就强制先给其中一个分 \(n\)，然后再插板，\(\binom{3}{1}\binom{s-n-1}{2}\)。

但是还要加上有两个超过 \(n\) 的情况，给其中两个分 \(n\) 再插板，得到 \(\binom{3}{2}\binom{s-2n-1}{2}\)。

因为我们的 \(s\) 只枚举到 \(3n\)，所以不会出现三个都超过 \(n\)，则直接返回即可。

C

考虑先处理所有可能的点集是否是完全图。我们可以往已有的点集内加入一个新点并判断它是否和已有的全部点相连。

这样，我们可以枚举点集 \(msk\)，并选出其中最小的点 \(x\)。如果去掉 \(x\) 之后依旧是完全图，且 \(x\) 和其中的所有点有边，则满足情况。

然后，我们考虑 \(g_{msk}\) 表示点集 \(msk\) 最少划分成多少个连通块。考虑子集枚举，枚举当前划分出哪个子集作为新加入的完全子图。\(g_{S}=\min {g_{S/A}+1}\)，其中 \(A\) 在之前已经被确定是完全子图。

这样的复杂度是 \(O(n2^n+3^n)\) 的，足以通过。

D

考虑二位前缀和，其实我们就是要计算 \(f(n,m)\) 表示 \((0,0)\) 到 \((n,m)\) 的长方形内所有位置的和。只要有计算这个的方法就可以了。

而考虑 \(f(n,m)=\sum_{x\le n,y\le m}\binom{x+y}{y}\)

我们考虑按行求，设 \(d(n',m)\) 表示 \(\sum_{i\le m}\binom{n'+i}{i}\)，我们只要对所有的 \(n'\le n\) 计算出 \(d(n',m)\)。而通过组合数的性质可以很容易知道 \(\sum_{i\le m}\binom{n'+i}{i}=\sum_{i\le m}\binom{n+m+1}{m}\)。

所以只要枚举 \(n'\) 即可。复杂度 \(O(n)\)。