1006C简单题（计数式子的组合意义 + dp式子联立）

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142740338

http://cplusoj.com/d/senior/p/SS241006C

对于这个式子，我们可以从它的组合意义入手。

假设我们有 $n+1$ 个白球要染色，中间有一个绿球，绿球左边有 $a$ 个红球，右边有 $b$ 球。染完后绿球左边每个白球有 $x$ 的贡献，右边每个白球有 $y$ 的贡献。

但接下来怎么做呢？这列出来的式子不是一样吗？注意，当我们转化为组合意义的时候，我们就可以不考虑计数的方法了，我们可以用dp了。

设 $dp(n,a,b)$ 表示当前的答案。保证绿球一定存在。

转移的话，我们可以考虑最左边和最右边的球的颜色：

$dp(n,a,b)=dp(n-1,a-1,b)+xdp(n-1,a,b)$
$dp(n,a,b)=dp(n-1,a,b-1)+ydp(n-1,a,b)$

考虑边界条件 $a=0$ ，或 $b=0$

• $a=0$ ， $dp(n,0,b)=xdp(n-1,0,b)+\binom{n-1}{b}y^{n-b-1}$

• $b=0$ ， $dp(n,a,0)=ydp(n-1,a,0)+\binom{i-1}{a}x^{i-a-1}$

然后就到了这题最巧妙的地方了。我们发现 $n$ 很大，但是是定值。而 $a,b$ 很小，这启示我们并不是往矩阵来想，而是我们考虑把 $n$ 丢掉。

我们直接联立最前面两条式子：

$$dp(n-1,a-1,b)+xdp(n-1,a,b)=dp(n-1,a,b-1)+ydp(n-1,a,b)\\ (x-y)dp(n-1,a,b)=dp(n-1,a,b-1)-dp(n-1,a-1,b)$$

$$dp(n-1,a,b)=\dfrac{dp(n-1,a,b-1)-dp(n-1,a-1,b)}{x-y}$$

这时就可以把 $n$ 丢掉了。

对于边界条件的处理，我们照样联立即可。

联立 $a=0$ 和 $b=0$ ，可以解出 $dp(0,0)$ 时的答案

联立 $a=0$ 和 $b\neq 0$ ，可以解出 $dp(0,b)$ 的答案。

然后就做完了

现在我们还有最后一个问题， $x=y$ 怎么处理。

我们直接回归原式，然后把 $x^{n-a-b}$ 提到外面，再重新剩下那坨式子的组合意义，此时红色蓝色已经没有意义了，相当于就是 $n+1$ 个球选 $a+b+1$ 个球，即为 $\binom{n+m+1}{a+b+1}$ 。