526互联

【杂题乱写】ARC110

发布时间 2023-09-07 06:26:54作者: SoyTony

AtCoder-ARC110A Redundant Redundancy

答案是 \(\operatorname{lcm}_{i=1}^n i +1\)，只需要在 \(p^k\) 位置乘上一个 \(p\) 即可。

提交记录：Submission - AtCoder

AtCoder-ARC110B Many 110

只需要匹配有限长度的 110 即可，匹配起始位置只有 \(3\) 个，暴力匹配计算。

提交记录：Submission - AtCoder

AtCoder-ARC110C Exoswap

设 \(r\) 为当前最大的 \(a_i\neq i\) 的位置，当前操作就是把 \(r\) 向右交换直到原位。

模拟这个过程即可判断。

提交记录：Submission - AtCoder

AtCoder-ARC110D Binomial Coefficient is Fun

考虑 \(\binom{i}{j}\) 的生成函数 \(F_j(x)=\sum_{i\ge 0} \binom{i}{j}x^i\)，可以推导：

\[\begin{aligned} F_j(x) &=\sum_{i\ge 0} \dbinom{i}{j}x^i\\ &=\sum_{i\ge 0} \left(\dbinom{i-1}{j-1}+\dbinom{i-1}{j}\right)x^i\\ &=\sum_{i\ge 0} \dbinom{i-1}{j-1}x^i+\sum_{i\ge 0} \dbinom{i-1}{j}x^i\\ &=xF_{j-1}(x)+xF_j(x) \end{aligned} \]

因此有 \(F_j(x)=\frac{x}{1-x}F_{j-1}(x)\)，而 \(F_0(x)=\frac{1}{1-x}\)，所以 \(F_j(x)=\frac{x^j}{(1-x)^{j+1}}\)。

设 \(s=\sum_{i=1}^n a_i\)，答案是求：

\[\begin{aligned} \sum_{j=s}^m [x^j]\prod_{i=1}^n F_{a_i}(x) &=\sum_{j=s}[x^j]F_s(x)\\ &=\sum_{j=s}^m [x^j] \dfrac{x^s}{(1-x)^{s+n}}\\ &=\sum_{j=s}^m [x^{j-s}] \left(\dfrac{1}{1-x}\right)^{s+n} \end{aligned} \]

有一经典结论：

\[\begin{aligned} [x^i]\left(\dfrac{1}{1-x}\right)^j &=[x^i](1-x)^{-j}\\ &=(-1)^i\dbinom{-j}{i}\\ &=(-1)^i\dfrac{(-j)^{\underline{i}}}{i!}\\ &=(-1)^i\dfrac{(-1)^ij^{\overline{i}}}{i!}\\ &=\dfrac{(i+j-1)^{\underline{i}}}{i!}\\ &=\dbinom{i+j-1}{i} \end{aligned} \]

因此答案就是：

\[\sum_{j=s}^m \dbinom{j+n-1}{s+n-1}=\dbinom{m+n}{s+n} \]

题解给出组合意义做法。

考虑把 \(m\) 个求划分成 \(n+1\) 段，第 \(i\) 段为 \(b_i\)，再在第 \(i\) 段选 \(a_i\) 个球的方案数，把段与段之间看作球，即为在 \(m+n\) 个球中，先选 \(a_1\) 个球，再选一个球，再选 \(a_2\) 个球，再选一个球……

结果为 \(m+n\) 个球中选 \(s+n\) 个，即 \(\binom{m+n}{s+n}\)。

提交记录：Submission - AtCoder

AtCoder-ARC110E Shorten ABC *

一个核心转化是把 \(\texttt{ABC}\) 分别看作 \(1,2,3\)，那么操作等价于把 \(s_i,s_{i+1}\) 替换成 \(s_i\oplus s_{i+1}\)。

这样一个方案对应划分区间要求每个区间大小是 \(1\) 或存在至少两种不同元素且异或和不为 \(0\)，方案得到的结果就是每个区间的异或和。

考虑 DP，容易想到转移根据前缀异或和讨论，找到上一个出现位置 \(last\) 转移（更靠前的位置一定可以通过改变最后一个区间大小来包含所有方案），即需要预处理 \(last_{i,j}\) 以及一个 \(p_i\) 表示 \(i\) 连续段的开头（一个长度大于 \(1\) 连续段是不能转移的）。

注意仍存在一种特殊情况，如 \(\texttt{BBBCBA}\)，\(i=4\) 时可以从 \(0,1,2,3\) 转移，但 \(1,3\) 处的前缀异或和相等，特判前缀全部相同时都转移即可。

提交记录：Submission - AtCoder