做斗图网站,h5网站建设需要哪些资料,discuz做商城网站,vscode制作个人网站http://cplusoj.com/d/senior/p/SS241006C 对于这个式子#xff0c;我们可以从它的组合意义入手。
假设我们有 n 1 n1 n1 个白球要染色#xff0c;中间有一个绿球#xff0c;绿球左边有 a a a 个红球#xff0c;右边有 b b b 球。染完后绿球左边每个白球有 x x x 的贡…http://cplusoj.com/d/senior/p/SS241006C 对于这个式子我们可以从它的组合意义入手。
假设我们有 n 1 n1 n1 个白球要染色中间有一个绿球绿球左边有 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 a0 a0或 b 0 b0 b0 a 0 a0 a0 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 b0 b0 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 a0 a0 和 b 0 b0 b0可以解出 d p ( 0 , 0 ) dp(0,0) dp(0,0) 时的答案
联立 a 0 a0 a0 和 b ≠ 0 b\neq 0 b0可以解出 d p ( 0 , b ) dp(0,b) dp(0,b) 的答案。
然后就做完了
现在我们还有最后一个问题 x y xy xy 怎么处理。
我们直接回归原式然后把 x n − a − b x^{n-a-b} xn−a−b 提到外面再重新剩下那坨式子的组合意义此时红色蓝色已经没有意义了相当于就是 n 1 n1 n1 个球选 a b 1 ab1 ab1 个球即为 ( n m 1 a b 1 ) \binom{nm1}{ab1} (ab1nm1)。
