背景：本人在模拟赛中遇到了形如
i=1∑C(BA−i)i 的式子，本以为不可做，后来发现这个东西可以
O(1) 求，由于网上没见过这类式子的求法，所以小小总结了一下。
前置知识：
(mn)=(m+1n+1)−(m+1n)
也就是组合数递推式换了一下形式。
求：
i=0∑C(BA−i)。
i=0∑C(BA−i)
=i=0∑C[(B+1A−i+1)−(B+1A−i)]
=i=0∑C(B+1A−i+1)−i=0∑C(B+1A−i)
=i=−1∑C−1(B+1A−i)−i=0∑C(B+1A−i)
=(B+1A+1)−(B+1A−C)
扩展：求
i=1∑C(BA−i)i。
i=1∑C(BA−i)i
i=1∑C[(B+1A−i+1)i−(B+1A−i)i]
=i=1∑C(B+1A−i+1)i−i=1∑C(B+1A−i)i
=i=0∑C−1(B+1A−i)(i+1)−i=1∑C(B+1A−i)i
=i=0∑C−1(B+1A−i)+i=0∑C−1(B+1A−i)i−i=1∑C(B+1A−i)i
=i=0∑C−1(B+1A−i)−(B+1A−C)C
=(B+2A+1)−(B+2A−C+1)−(B+1A−C)C
再扩展：求
i=1∑C(BA−i)ik,k>0。
设
fx,k=i=1∑C(B+xA−i)ik。
i=1∑C(B+xA−i)ik
=i=1∑C[(B+x+1A−i+1)ik−(B+x+1A−i)ik]
=i=1∑C(B+x+1A−i+1)ik−i=1∑C(B+x+1A−i)ik
=i=0∑C−1(B+x+1A−i)(i+1)k−i=1∑C(B+x+1A−i)ik
=−(B+x+1A−C)(C+1)k+i=0∑C(B+x+1A−i)(i+1)k−i=1∑C(B+x+1A−i)ik
=−(B+x+1A−C)(C+1)k+i=0∑C[(B+x+1A−i)j=0∑k(jk)ij]−i=1∑C(B+x+1A−i)ik
=−(B+x+1A−C)(C+1)k+j=0∑k[(jk)i=0∑C(B+x+1A−i)ij]−i=1∑C(B+x+1A−i)ik
=−(B+x+1A−C)(C+1)k+j=0∑k−1[(jk)i=0∑C(B+x+1A−i)ij]+i=0∑C(B+x+1A−i)ik−i=1∑C(B+x+1A−i)ik
=−(B+x+1A−C)(C+1)k+j=0∑k−1[(jk)i=0∑C(B+x+1A−i)ij]
=−(B+x+1A−C)(C+1)k+j=1∑k−1[(jk)i=1∑C(B+x+1A−i)ij]+i=0∑C(B+x+1A−i)
=−(B+x+1A−C)(C+1)k+j=1∑k−1(jk)fx+1,j+i=0∑C(B+x+1A−i)
后面的式子在前文已经解决，前面的式子可以直接求，中间的式子可以递推，有用的状态是
O(k2) 的，所以可以
O(k3) 递推。用多项式可以优化到
O(k2logk)。下文会有一个更好的做法。
再再再扩展：求
i=1∑C(BA−i)(ki),k>1。
i=1∑C(BA−i)(ki)
=i=1∑C[(B+1A−i+1)(ki)−(B+1A−i)(ki)]
=i=1∑C(B+1A−i+1)(ki)−i=1∑C(B+1A−i)(ki)
=i=0∑C(B+1A−i)(ki+1)−i=1∑C(B+1A−i)(ki)
=i=0∑C−1[(B+1A−i)(ki)+(B+1A−i)(k−1i)]−i=1∑C(B+1A−i)(ki)
=i=0∑C−1(B+1A−i)(k−1i)+i=0∑C−1(B+1A−i)(ki)−i=1∑C(B+1A−i)(ki)
=i=1∑C−1(B+1A−i)(k−1i)−(B+1A−C)(kC)
i=1∑C(BA−i)ik 的另一种求法。
前置知识：斯特林数反演。
i=1∑C(BA−i)ik
=i=1∑C(BA−i)j=0∑k{kj}(ji)
=j=0∑k{kj}i=1∑C(BA−i)(ji)
右边的式子在上文可以
O(k)，总复杂度
O(k2)。
以上是本人瞎胡的，如果有错或有更好的做法，欢迎提出。