「Summary」2022-08-12 做题记录

差异化竞争

2022-08-11

$\mathbb{CF1558D}$

link

想不到

考虑这个操作的意义，事实上它指出来元素之间的大小关系。
可以在一开始认为这个序列所有元素之间的链接符号都是 $\le$ ，而当一次操作 $(x, y)$ 发生之后，表面效果是让 $a_x$ 往前挪到了第 $y$ 个位置，实际上指出了 $a_{y - 1} \le a_x, a_x < a_{y + 1}$ 。
则这个操作可以告诉我们一堆向上面一样的信息，抽调元素，则剩下的都是小于等于和小于，考虑这个一共有多少种方案，即 $n$ 个数，有 $n - 1$ 组相邻两个元素之间的关系，其中有 $c$ 个小于号，有 $n - 1 - c$ 个小于等于号，满足不等关系且在值域范围类的序列的个数。
这个要用一个技巧，把 $a_i \le a_{i + 1}$ 转化为 $a_i < a_{i + 1}+ 1$ 。
那么转化为全是小于号的情况，则在值域范围内选出 $n$ 个数，保证递增的方案数，这个直接就是 $\binom{V}{n}$ ，考虑值域 $V = 2 \times n - c - 1$ 。
那么用平衡树维护这个就好了。

$\mathbb{HDU6397}$

link

结论

在没有上界的情况下，方案数是 $\binom{m + k - 1}{k - 1}$ ，正向很难做，考虑计算不合法的贡献，如果有 $i$ 个元素大于 $n - 1$ ，则 $\sum x - i \times n = k - i \times n$ ，方案数为 $\binom{m + k - i \times n - 1}{k - 1}$ ，这个配合容斥就能算了，系数奇负偶正。

$\mathbb{HDU7060}$

link

特判写错三次 🤡

如果 $x$ 的第 $j(i记 $s_i$ 表示 $x$ 第 $i∼n$ 位的和，那么作为第 $i$ 为出现的数字的贡献为（不计算 $x$ 的第 $i$ 位的贡献）$s_{i+1}\times 10^{i-1}\left(\sum^{k-2}_{j=0}\binom{n-i-1}{j}\right)$
再考虑 $x$ 的第 $i$ 位作为划分出来的数的第 $i$ 位的贡献。因为第 $n$ 位后面必须划分，所以相当于在剩余 $n−i$ 位中可以随意划分不超过 $k−1$ 次。贡献为
$a_{i}\times 10^{i-1}\left(\sum^{k-1}_{j=0}\binom{n-i}{j}\right)$ 。

$\mathbb{CF1536F}$

link

观察

一个强有力的性质是说后手必胜。
证明很简单，如果先手胜利，则现在有奇数个格子染了色，把他们之间的空格剔除，则相邻的之间一定颜色不一样，发现这个是矛盾的，得出后手必胜。
之后就好做了，枚举后手在哪一次胜利，记为 $f(k)$ ，则 $f(k) = 2 \times \binom{n - 2 \times k}{2\times k - 1} + 2\times \binom{n - 2\times k - 1}{2 \times k - 1}$ ，直接求和即可。

$\mathbb{HDU5226}$

link

有没有一种可能，你这个 Lucas 函数根本没有调用

远古结论 $\sum_{i = 0}^{k} \binom{n}{k} = \binom{n + 1}{k + 1}$ 。
然后注意处理的值域上界，要用到 Lucas 。

$\mathbb{HDU4349}$

link

oeis

确实，这个序列有前人研究过，给个 oeis 的链接。
也可以在 math.stackexchange 上找到相应的一些研究。
其实证明也很简单，用 Lucas 定理，$\binom{n}{m}$ 为奇数，就是说 $\binom{n}{m}$ 在模 $2$ 的意义下为 $1$ ，结合定理 $\binom{n}{m} = \binom{n \ \mathrm{mod}\ 2}{m \ \mathrm{mod}\ 2} \times \binom{n / 2}{m / 2}$ ，如此一直拆下去，相当于所有 $\binom{n \ \mathrm{mod}\ 2}{m \ \mathrm{mod}\ 2}$ 一样的项都是 $1$ ，因为在模 $2$ 的意义下，只有 $0,1$ 两种取值，很容易知道 $\binom{1}{1}$， $\binom{1}{0}$ 和 $\binom{0}{0}$ 是 $1$ 。
于是可以二进制拆分 $n$ ，同样对于 $1\le k \le n$ 也可以这样拆，与 $n$ 判断就行了，但是这样复杂度不对。
可以考虑一个和数位 DP 一样的做法，从 $n$ 的最高位到最低位，如果是 $1$ ，则另一个数可以放 $0/1$ ，如果是 $0$ 则另一个数只能放 $0$ ，细想其实只需要统计 $n$ 中 $1$ 的个数就行了，记为 $cnt$ ，则合法的数一共有 $2^{cnt}$ 种。
做到这里，就能得到和 oeis 上一样的结论了。

$\mathbb{HDU3304}$

link

上一题的推广

继续用 Lucas ，$\binom{n}{m} = \binom{n \ \mathrm{mod}\ p}{m \ \mathrm{mod}\ p} \times \binom{n / p}{m / p}$ ，如果在模 $p$ 的意义下不为 $0$ ，则说明每一项都不为 $0$ ，那么只需要保证每一位上 $n_i \ge m_i$ 即可。
所以，当遇到与组合数取模相关的题目时要能想到用 Lucas 定理。