wordpress添加收藏功能免费seo技术教程
http://cplusoj.com/d/senior/p/SS241006C
对于这个式子，我们可以从它的组合意义入手。
假设我们有 n + 1 n+1 n+1 个白球要染色，中间有一个绿球，绿球左边有 a a a 个红球，右边有 b b b 球。染完后绿球左边每个白球有 x x x 的贡献，右边每个白球有 y y y 的贡献。
但接下来怎么做呢？这列出来的式子不是一样吗？注意，当我们转化为组合意义的时候，我们就可以不考虑计数的方法了，我们可以用dp了。
设 d p ( n , a , b ) dp(n,a,b) dp(n,a,b) 表示当前的答案。保证绿球一定存在。
转移的话，我们可以考虑最左边和最右边的球的颜色：
d p ( n , a , b ) = d p ( n − 1 , a − 1 , b ) + x d p ( n − 1 , 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−1,b)+xdp(n−1,a,b)
d p ( n , a , b ) = d p ( n − 1 , a , b − 1 ) + y d p ( n − 1 , a , b ) dp(n,a,b)=dp(n-1,a,b-1)+ydp(n-1,a,b) dp(n,a,b)=dp(n−1,a,b−1)+ydp(n−1,a,b)
考虑边界条件 a = 0 a=0 a=0，或 b = 0 b=0 b=0
- a = 0 a=0 a=0， d p ( n , 0 , b ) = x d p ( n − 1 , 0 , b ) + ( n − 1 b ) y n − b − 1 dp(n,0,b)=xdp(n-1,0,b)+\binom{n-1}{b}y^{n-b-1} dp(n,0,b)=xdp(n−1,0,b)+(bn−1)yn−b−1
- b = 0 b=0 b=0， d p ( n , a , 0 ) = y d p ( n − 1 , a , 0 ) + ( i − 1 a ) x i − a − 1 dp(n,a,0)=ydp(n-1,a,0)+\binom{i-1}{a}x^{i-a-1} dp(n,a,0)=ydp(n−1,a,0)+(ai−1)xi−a−1
然后就到了这题最巧妙的地方了。我们发现 n n n 很大，但是是定值。而 a , b a,b a,b 很小，这启示我们并不是往矩阵来想，而是我们考虑把 n n n 丢掉。
我们直接联立最前面两条式子：
d p ( n − 1 , a − 1 , b ) + x d p ( n − 1 , a , b ) = d p ( n − 1 , a , b − 1 ) + y d p ( n − 1 , a , b ) ( x − y ) d p ( n − 1 , a , b ) = d p ( n − 1 , a , b − 1 ) − d p ( n − 1 , a − 1 , b ) 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−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)
d p ( n − 1 , a , b ) = d p ( n − 1 , a , b − 1 ) − d p ( n − 1 , a − 1 , b ) x − y dp(n-1,a,b)=\dfrac{dp(n-1,a,b-1)-dp(n-1,a-1,b)}{x-y} dp(n−1,a,b)=x−ydp(n−1,a,b−1)−dp(n−1,a−1,b)
这时就可以把 n n n 丢掉了。
对于边界条件的处理，我们照样联立即可。
联立 a = 0 a=0 a=0 和 b = 0 b=0 b=0，可以解出 d p ( 0 , 0 ) dp(0,0) dp(0,0) 时的答案
联立 a = 0 a=0 a=0 和 b ≠ 0 b\neq 0 b=0，可以解出 d p ( 0 , b ) dp(0,b) dp(0,b) 的答案。
然后就做完了
现在我们还有最后一个问题， x = y x=y x=y 怎么处理。
我们直接回归原式，然后把 x n − a − b x^{n-a-b} xn−a−b 提到外面，再重新剩下那坨式子的组合意义，此时红色蓝色已经没有意义了，相当于就是 n + 1 n+1 n+1 个球选 a + b + 1 a+b+1 a+b+1 个球，即为 ( n + m + 1 a + b + 1 ) \binom{n+m+1}{a+b+1} (a+b+1n+m+1)。