題目描述

傳送門

題解

題意就是給出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}$

代碼