[BZOJ3142][Hnoi2013]数列（数学相关）

题目描述

传送门

题解

题意就是给出n,k,m,p，求有多少长度为k的序列A，满足：首项为正整数；递增数列；相邻两项的差小于等于m；最大值小于等于n 设a(i)=A(i+1)-A(i)，我们只考虑a(i)，显然a(i)所需要满足的条件就是ai≤m$a_i/le m$ 一个合法的a(i)序列对答案的贡献为 n−∑i=1k−1ai$n-/sum/limits_{i=1}^{k-1}a_i$ 合法的a(i)序列一共有mk−1$m^{k-1}$个，那么 ans=∑a1=1m∑a2=1m...∑ak−1=1m(n−a1−a2−...−ak−1)$ans=/sum/limits_{a_1=1}^m/sum/limits_{a_2=1}^m.../sum/limits_{a_{k-1}=1}^m(n-a_1-a_2-...-a_{k-1})$ =n∗mk−1−∑a1=1m∑a2=1m...∑ak−1=1m∑i=1k−1ai$=n*m^{k-1}-/sum/limits_{a_1=1}^m/sum/limits_{a_2=1}^m.../sum/limits_{a_{k-1}=1}^m/sum/limits_{i=1}^{k-1}a_i$ 从这里可以看出，后面的一坨实际上就是1..m这些数每个数出现了(k−1)∗mk−2$(k-1)*m^{k-2}$次，求它们的和 所以用一下等差数列的求和公式？ans=n∗mk−1−m(m+1)2∗(k−1)∗mk−2$ans=n*m^{k-1}-{m(m+1)/over 2}*(k-1)*m^{k-2}$

代码