2020牛客暑期多校训练营（第五场）C-Easy

设min(ai,bi)min(a_i,b_i)所对应的二元生成函数为f(x,y)f(x,y)，则答案为[xnym]fk(x,y)[x^ny^m]f^k(x,y)

由基本生成函数知识可知

f(x,y)=∑i>0,j>0min(i,j)xiyj=∑0<i≤jixiyj+∑i>j>0jxiyj=∑i=1∞ixi∑j=i∞yj+∑j=1∞jyj∑i=j+1∞xi=∑i=1∞ixiyi1−y+∑j=1∞jyjxj+11−x\begin{aligned} f(x,y)&=\sum\limits_{i>0,j>0}min(i,j)x^iy^j\\ &=\sum\limits_{0<i\le j}ix^iy^j + \sum\limits_{i>j>0}jx^iy^j\\ &=\sum\limits_{i=1}^\infty ix^i\sum\limits_{j=i}^\infty y^j+\sum\limits_{j=1}^\infty jy^j\sum\limits_{i=j+1}^\infty x^i\\ &=\frac{\sum\limits_{i=1}^\infty ix^iy^i}{1-y}+\frac{\sum\limits_{j=1}^\infty jy^jx^{j+1}}{1-x} \end{aligned}

考虑 g(x)=∑i=1∞ixi=x∑i=0∞ixi−1=x(11−x)′=x(1−x)2\begin{aligned} g(x)=\sum\limits_{i=1}^\infty ix^i =x\sum\limits_{i=0}^\infty ix^{i-1} =x(\frac1{1-x})' =\frac x{(1-x)^2} \end{aligned}

则 f(x,y)=xy(1−y)(1−xy)2+x2y(1−x)(1−xy)2=xy(1−xy)(1−x)(1−y)\begin{aligned} \text{则 }f(x,y)&=\frac{xy}{(1-y)(1-xy)^2}+\frac{x^2y}{(1-x)(1-xy)^2}\\ &=\frac{xy}{(1-xy)(1-x)(1-y)} \end{aligned}

因此 ans=[xnym]fk(x,y)=[xn−kym−k](1(1−xy)(1−x)(1−y))k=∑i=0min(n−k,m−k)[xiyi]1(1−xy)k×[xn−k−i]1(1−x)k×[ym−k−i]1(1−y)k=∑i=0min(n−k,m−k)(i+k−1i)(n−i−1k−1)(m−i−1k−1)\begin{aligned} \text{因此 }ans&=[x^ny^m]f^k(x,y)\\ &=[x^{n-k}y^{m-k}](\frac{1}{(1-xy)(1-x)(1-y)})^k\\ &=\sum_{i=0}^{min(n-k,m-k)}[x^iy^i]\frac{1}{(1-xy)^k}\times [x^{n-k-i}]\frac{1}{(1-x)^k}\times [y^{m-k-i}]\frac{1}{(1-y)^k}\\ &=\sum_{i=0}^{min(n-k,m-k)}\binom{i+k-1}i\binom{n-i-1}{k-1}\binom{m-i-1}{k-1} \end{aligned}

时间复杂度O(T(n+m))O(T(n+m))