題目描述

傳送門

題解

題意就是給出n,k,m,p，求有多少長度為k的序列A，滿足：首項(xiàng)為正整數(shù)；遞增數(shù)列；相鄰兩項(xiàng)的差小于等于m；最大值小于等于n 設(shè)a(i)=A(i+1)-A(i)，我們只考慮a(i)，顯然a(i)所需要滿足的條件就是ai≤m$a_i/le m$ 一個(gè)合法的a(i)序列對答案的貢獻(xiàn)為 n?∑i=1k?1ai$n-/sum/limits_{i=1}^{k-1}a_i$ 合法的a(i)序列一共有mk?1$m^{k-1}$個(gè)，那么 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$ 從這里可以看出，后面的一坨實(shí)際上就是1..m這些數(shù)每個(gè)數(shù)出現(xiàn)了(k?1)?mk?2$(k-1)*m^{k-2}$次，求它們的和 所以用一下等差數(shù)列的求和公式？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}$

代碼