考虑求 ∑i=0m(pi)(n−pm−i)\sum_{i=0}^{m}{\tbinom{p}{i}\tbinom{n-p}{m-i}}∑i=0m(ip)(m−in−p) 这个式子等于 ∑i=0mp!i!(p−i)!(n−p)!(m−i)!(n−p−m+i)!\sum_{i=0}^{m}{\frac{p!}{i!(p-i)!}\frac{(n-p)!}{(m-i)!(n-p-m+i)!}}∑i=0mi!(p−i)!p!(m−i)!(n−p−m+i)!(n−p)! =p!(n−p)!∑i=0m1i!(p−i)!1(m−i)!(n−p−m+i)!=p!(n-p)!\sum_{i=0}^{m}{\frac{1}{i!(p-i)!}\frac{1}{(m-i)!(n-p-m+i)!}}=p!(n−p)!∑i=0mi!(p−i)!1(m−i)!(n−p−m+i)!1 令 j=m−ij=m-ij=m−i 即求 p!(n−p)!∑i+j=m1i!(p−i)!1j!(n−p−j)!p!(n-p)!\sum_{i+j=m}{\frac{1}{i!(p-i)!}\frac{1}{j!(n-p-j)!}}p!(n−p)!∑i+j=mi!(p−i)!1j!(n−p−j)!1 于是可以用多项式卷积做
