ARC144D与组合恒等式
ARC144D
题意略。
观察，发现 \(x \& y + x |y = x+y\)，原因是每个二进制位，如果出现两次，会计入二次，如果出现一次，会计入一次。猜想 \(f(x)\) 的值与每个二进制位相关且对于每个二进制位独立。
考虑证明，对 \(x\) 的二进制下 \(1\) 的个数 \(n\) 做归纳。
对于 \(n=0\)，\(f(0)=f(0)\)
对于 \(n=1\)，\(f(2^i) = f(2^i)\)
对于 \(n=2\)，\(f(2^i+2^j) + f(0) = f(2^i) +f(2^j)\)
考虑证明 \(n=k\) 时， \(f(x) +(k-1)f(0) = \sum\limits_{i\in x} f(2^i)\)
设对于 \(n=k-1\) 其成立，对于二进制位 1 个数为 k 的 x， \(\forall i\in x,f(x)+f(0)=f(x-2^i) + f(2^i)\)，易证 \(f(x) +(k-1)f(0) = \sum\limits_{i\in x} f(2^i)\)，且对于所有涉及元素二进制下 1 个数少于 n 的，所有限制满足。
故只需要确定 \(f(2^i)\) 和 \(f(0)\)。其最终限制有两个，其一是，最大值不能超过 \(k\)，其二是最小值不能小于 0，最大值一定是把所有大于 \(f(0)\) 的元素加起来，最小值则是把所有小于 \(f(0)\) 的元素加起来。
枚举 \(f(0)\) 和小于 \(f(0)\) 的元素个数，我们可以将限制分配给对应元素 ，得到和式： \[ ans=\sum\limits_{f(0)=0}^{k}\sum\limits_{i=0}^{n}\binom{n}{i}\binom{f(0)}{i}\binom{k-f(0)+n-i}{n-i} \] 第一项计算那些小于 \(f(0)\)，第二项是将至多 \(k\) 个冗余值分配给 \(i\) 个小于 \(f(0)\) 的元素的方案数，每个元素至少分配一个，或者说 \(i\) 个正整数变量和为 \(f(0)\) 的方案，可以给一个虚拟元素分别大于等于 0 个表示放弃，所以先给虚拟元素一个，变成 \(f(0)+1\) 个元素插 \(i\) 个板。最后一项是 \(n-i\) 个非负整数变量，和不超过 \(k-f(0)\) 的方案。先来个虚拟变量，然后先各自加 \(1\)，然后就是 \(k-f(0)+n-i+1\) ，间隔是 \(k-f(0)+n-i\) 个，版一共 \(n\) 个。
解释完了，考虑计算，二维的，算不了。
考虑后两项的组合意义。
根据组合恒等式中的第五个。
对原式变形有 \[ ans=\sum\limits_{i=0}^{n}\binom{n}{i}\binom{k-f(0)+n-i+1}{n-i+1} \] 然后 \(n\) 不大，维护个区间乘积枚举计算就行，记得对计算乘积的元素取模。
组合恒等式
题不是终点，组合恒等式才是重点
对上面那种图的组合恒等式，我们一一证明
式子1
\[ \sum\limits_{k}\binom{r}{m+k}\binom{s}{n-k}=\binom{r+s}{m+n} \]
组合意义证明
第一项是从 \(r\) 个选 \(m+k\) 个，第二项是从 \(s\) 个选 \(n-k\) 个，把两个拼在一起，从 \(r+s\) 个中选 \(n+m\) 个，容易发现和前者一一对应，故恒等。
代数证明
咕咕咕
式子2
\[ \sum\limits_{k}\binom{l}{m+k}\binom{s}{n+k} = \binom{l+s}{l-m+n},l\ge0 \]
组合意义证明
代数证明
咕咕咕