关于 NOI2019 斗主地 的证明

左边 \(L\) 右边 \(R\) 张牌:

左边从上往下第 \(x\) 张牌对第 \(i\) 个位置的贡献

其实都可以打表观察 233

\[\sum_{x}\binom{i-1}{x-1}\binom{n-i}{L-x}w_x \]

\(w_x = x :\)

\[\sum_{x}\binom{i-1}{x-1}\binom{n-i}{L-x} x \]

\[\sum_{x}(\binom{i}{x}x - \binom{i-1}{x}x)\binom{n-i}{L-x} \]

\[\sum_{x}(\binom{i-1}{x-1}i - \binom{i-2}{x-1}(i-1))\binom{n-i}{L-x} \]

\[i\times(\binom{n-1}{L-1} - \binom{n-2}{L-1}) + \binom{n-2}{L-1} \]

\(w_x = x^2 :\)

\[\sum_{x}\binom{i-1}{x-1}\binom{n-i}{L-x} x^2 \]

\[\sum_{x}(\binom{i-1}{x-1}i - \binom{i-2}{x-1}(i-1))\binom{n-i}{L-x}x \]

考虑化简一下 \(\sum_{x}(\binom{i-1}{x-1}i(x-1) - \binom{i-2}{x-1}(i-1)(x-1))\binom{n-i}{L-x}\)

\[\sum_{x}(\binom{i-2}{x-2}i(i-1) - \binom{i-3}{x-2}(i-1)(i-2))\binom{n-i}{L-x} \]

一样可以范德蒙德卷积的化简处理。右边其实也差不多?

这样就证明了 一次函数变换后是一次函数,二次函数变换后是二次函数。

上一篇:「学习笔记」斯特林数


下一篇:[被踩计划] 题解 [省选联考 2020 A 卷] 组合数问题