本文主要是介绍2020省选A卷 组合数问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
求
∑ k = 0 n f ( k ) x k ( n k ) \sum_{k=0}^{n} f(k) x^{k} \binom{n}{k} k=0∑nf(k)xk(kn)
n ≤ 1000 \ n \le 1000 n≤1000， m ≤ 1000 \ m \le 1000 m≤1000
求杨辉三角，枚举即可。
m = 0 \ m=0 m=0
根据二项式定理，即
a 0 ∑ k = 0 n x k ( n k ) = a 0 ( x + 1 ) n a_{0}\sum_{k=0}^{n} x^{k} \binom{n}{k}=a_{0}(x+1)^{n} a0k=0∑nxk(kn)=a0(x+1)n
m ≤ 5 \ m \le 5 m≤5
我们只需要对 y , y ∈ [ 0 , m ] \ y,y \in [0,m] y,y∈[0,m]求出
∑ k = 0 n k y x k ( n k ) \sum_{k=0}^{n}k^{y} x^{k} \binom{n}{k} k=0∑nkyxk(kn)
我们设：
g ( n , y , t ) = ∑ k = 0 n ( k + t ) y x k ( n k ) g(n,y,t)=\sum_{k=0}^{n} (k+t)^{y} x^{k} \binom{n}{k} g(n,y,t)=k=0∑n(k+t)yxk(kn)
显然：
g ( n , y , t ) = ∑ k = 0 n ( k + t ) y x k ( n k ) = ∑ k = 0 k ⋅ ( k + t ) y − 1 x k ( n k ) + t ∑ k = 0 n ( k + t ) ( y − 1 ) ( n k ) = n ∑ k = 1 n ( k + t ) y − 1 x k ( n − 1 k − 1 ) + t ⋅ g ( n , y − 1 , t ) = n x ∑ k = 0 n − 1 ( k + 1 + t ) y − 1 ( n − 1 k ) + t ⋅ g ( n , y − 1 , t ) = n x ⋅ g ( n − 1 , y − 1 , t + 1 ) + t ⋅ g ( n , y − 1 , t ) \begin{array}{rcl} g(n,y,t) & = & \sum_{k=0}^{n} (k+t)^{y} x^{k} \binom{n}{k}\\ & = & \sum_{k=0} k \cdot (k+t)^{y-1} x^{k} \binom{n}{k} + t\sum_{k=0}^{n}(k+t)^{(y-1)}\binom{n}{k} \\ & = & n \sum_{k=1}^{n} (k+t)^{y-1} x^{k} \binom{n-1}{k-1} + t \cdot g(n,y-1,t) \\ & = & n x \sum_{k=0}^{n-1}(k+1+t)^{y-1} \binom{n-1}{k} +t \cdot g(n,y-1,t) \\ & = & n x \cdot g(n-1,y-1,t+1) + t \cdot g(n,y-1,t) \end{array} g(n,y,t)=====∑k=0n(k+t)yxk(kn)∑k=0k⋅(k+t)y−1xk(kn)+t∑k=0n(k+t)(y−1)(kn)n∑k=1n(k+t)y−1xk(k−1n−1)+t⋅g(n,y−1,t)nx∑k=0n−1(k+1+t)y−1(kn−1)+t⋅g(n,y−1,t)nx⋅g(n−1,y−1,t+1)+t⋅g(n,y−1,t)
y = 0 \ y=0 y=0时：
g ( n , y , t ) = ( x + 1 ) n g(n,y,t)=(x+1)^{n} g(n,y,t)=(x+1)n
爆搜即可。复杂度 O ( 2 m + 1 ) \ O(2^{m+1}) O(2m+1)。
m ≤ 1000 \ m \le 1000 m≤1000
容易发现状态只有 m ( m + 1 ) 2 \ \frac{m(m+1)}{2} 2m(m+1)个，记忆化即可。
这篇关于2020省选A卷 组合数问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
