526互联

Educational Round 147

发布时间 2023-07-28 21:10:03作者: Skylakes

前言：非常好场次编号，爱来自小粉兔。

唉，GF。

A. shaber 模拟。

B. shaber。找最大的满足 \(a_{l\sim r}\) 和 \(a'_{l\sim r}\) 有不同，且 \(a'_{l\sim r}\) 递增的 \(\langle l,r \rangle\) 即可。\(\mathcal O(n)\)。

C. shaber。枚举字符 \(c\)，非 \(c\) 最大连续段长是 \(k\) 的话答案就是 \(\lfloor\frac{k}{2} \rfloor + 1\)，是这个数吧，没仔细看。\(\mathcal O(n|\Sigma|)\)。

D. 注意到选 \(1\) 的段一定不优，能不选就不选，枚举得聪明一点。

E. 一个右括号的贡献次数就是它到和它匹配的左括号这一段的右括号数量（不包括自己）。我一开始瞎 dp，完全没必要，发现把俩匹配的括号搬到一块一定不劣，按贡献次数降序排序，删去前 \(k\) 大即可。\(\mathcal O(n\log n)\)，\(k\) 很小所以直接冒泡是 \(\mathcal O(nk)\)。

F. 有 114514 种理解这个东西的形式。对应着不同的切入点。我咋一个都没想到，这么不牛。

第一种思路：考虑用树的位置刻画，这样最直观。对于一种方案，有一种显然的贪心判定：能往左倒就往左倒，反之往右倒。

我一开始是胡了个更强的充要条件然后转背包，后面发现是假的 /cf，然后大脑就停转了。

考虑 dp 刻画这个东西。第 \(i+1\) 的怎么放和前 \(i\) 个最右端覆盖到哪里有关。所以 \(f_{i,j}\) 表示前 \(i\) 个最右边覆盖到了 \(j\)。转移 \(2f_{i,j}\to f_{i+1,l}[l\in [j+k+1,2k]],f_{i,j}\to f_{i+1,l}[l\in [2k+1,n]]\)。左边那个系数 \(2\) 是因为可能放在 \(l\) 然后向左倒，也有可能放在 \(l-k\) 向右倒。右边系数是 \(1\)，因为根据贪心判定方式只能是放在 \(l\) 向左倒。

这个形式不太好看，换一个写法：\(f_{i,j}=\sum\limits_{l=0}^{j-k-1}f_{i-1,l}+\sum\limits_{l=j-2k}^{j-k-1}f_{i-1,l}\)。

转移太工整了！\(k\) 是常数，所以直接用 GF 来描述这个东西。\(F_i=\sum\limits_{j=0}^{n}f_{i,j}x^j\)，上面那个转移可以看作 \(F_{i-1}\) 乘上两个系数，分别设为 \(A,B\)，那么有 \(A(x)=\frac{x^{k+1}}{1-x},B(x)=\frac{x^{k+1}-x^{2k+1}}{1-x}\)。初始柿子不太想写，从这里学的。

初始 \(F_0=1,F_m=(A(x)+B(x))^m=\frac{(x^{k+1}-x^{2k+1})^m}{(1-x)^m}\)。

暴力展开。分母是 \((1-x)^{-m}=\sum\limits_{i} (-1)^ix^i\binom{-m}{i}=\sum\limits_{i}x^i\binom{m+i-1}{i}\)。分子是 \((2x^{k+1}-x^{2k+1})^m=\sum\limits_{i=0}^m2^i(-1)^{m-i}x^{i(k+1)+(m-i)(2k+1)}\binom{m}{i}\)。

注意到我们只求和不求单项，所以不用多项式算法，直接把系数累加起来乘一下就好！\(\mathcal O(n)\)。其实分母那个柿子是不是可以组合数再化一下，800 万年没看过具体数学了忘了。

第二种思路：考虑一开始拆出来 \(m\) 个长为 \(k+1\) 的段表示树占领的空间。方案数 \(\binom{n-mk}{m}\)，每棵树有两种放置方法（左右），所以系数 \(2^m\)。这么简单吗？

显然不是，要不然刚刚那个 dp 为啥是对的？发现两端之间距离 \(\ge k\) 的时候系数只能是 \(1\)，要不然你选中间这段的方案在这里又会被算一遍。其实直接观察上面那个 dp 柿子也行。殊途同归，都是等价的。

下面是机械的工作。\(f_i\) 表示恰有 \(i\) 个段间距离 \(\ge k\)，\(g_i\) 表示钦定 \(i\) 个段间距离 \(\ge k\) 的方案数。显然 \(g_i=\binom{n-(m+i)k}{m}\binom{m}{i}\)。

二项式反演推柿子：

\[\begin{aligned} f_i & =\sum_{j=i}^m g_j(-1)^{j-i}\binom{j}{i}\\ \mathrm{ans} & = \sum_{i=0}^m 2^{m-i}f_i\\ & = \sum_{i=0}^m 2^{m-i}\sum_{j=i}^m g_j(-1)^{j-i}\binom{j}{i}\\ & = \sum_{j=0}^m 2^{m-j}g_j\sum_{i=0}^j 2^{j-i}(-1)^{j-i}\binom{j}{i}\\ & = \sum_{j=0}^m 2^{m-j}(-1)^jg_j\sum_{i=0}^m2^{j-i}(-1)^i\binom{j}{i}\\ & = \sum_{j=0}^m 2^{m-j}(-1)^j g_j \end{aligned} \]

其实那个 \((-1)^j\) 的系数经验丰富的话可以直接看出来 qwq。\(\mathcal O(m)\)。不过根据上面的推到可以看出来这个容斥系数只对 \(2\) 的次幂满足条件，如果再奇怪一点可能不好搞，所以还是要会这种交换求和顺序+二项式定理的纯代数推导法。