CF1942

· · 个人记录

CF1942

E

Solution

首先假定第一头牛是先手的，最后再将答案乘 2 就行。

将相邻的两头牛配对，我们有如下结论：

先手必胜当且仅当存在一对牛之间空格为奇数。

考虑证明，由于可以移动任意的牛，先手可以将所有空格为奇数的一对牛移动为偶数，后手由于所有牛空格为偶数，移动后必然在一对牛之间空格为奇数。

这样反复移动，先手的牛必然会压缩后手的牛的生存空间，知道所有空格为 0，先手获胜。

这样我们要对其进行计数，不妨用所有情况减去每对牛之间空格为偶数的情况。

所有情况 \tbinom{l}{2n}。

我们枚举有 2x 个空格在一对牛的中间，将 x 个空格分为 n 组，容易用插板法计算，为 \tbinom{x+n-1}{n-1}。

剩下的 l-2x-2n 继续用插板法分为 n+1 组， \tbinom{2l-2x-2n-1}{l-2x-2n-1}。

答案即为 \left(\displaystyle\dbinom{l}{2n} - \sum\limits_{x=0,2|x}^{l-2n}\dbinom{x+n-1}{n-1}\dbinom{2l-2x-2n-1}{l-2x-2n-1}\right) \times 2。

F

Solution

首先 f(i)=\sqrt{(f(i-1)+a_i)}，由于 a_i 是整数，这等价于 f(i)=\left\lfloor\sqrt{(f(i-1)+a_i)}\right\rfloor，这样就将原问题转化为整数问题。

考虑将操作离线并用线段树维护所有答案。

我们从 1 到 n 对数组扫描线，扫描到 i 时，进行全局开根，对于每个询问，加上询问时对应的 a_i，这可以转化为区间加。

现在线段树要实现全局开根，区间加，容易用势能线段树做到。