关于 NOI2019 斗主地 的证明

本文主要是介绍关于 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} \]

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

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

这篇关于关于 NOI2019 斗主地 的证明的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！