洛谷團隊月賽題:題解

$10pts$

暴力算不解釋，時間復雜度O(kn+k2)O(kn+k^2)O(kn+k2)。

$30pts$

我們觀察到$n$很大，楊輝三角會T，直接算會上溢，所以需要預處理出$1$~$k$逆元再算，時間復雜度O(kn+nlogk+n2)O(kn+nlogk+n^2)O(kn+nlogk+n2)或O(kn+n+k+n2)O(kn+n+k+n^2)O(kn+n+k+n2)。

$60pts$

代入幾個$k$，發現數列通項是一個多項式，故SnS_nSn?也有一個通項；觀察次數，可知ana_nan?等于一個$k$次多項式，那么SnS_nSn?等于一個$k+1$次方多項式，拉格朗日插值+高斯消元解出SnS_nSn?表達式即可，當然也要預處理逆元，時間復雜度為O(k3)O(k^3)O(k3)。

$80pts$

不要被$n$嚇到，還是先算表達式，代入時高精度取模即可，時間復雜度為O(k3+klgn)O(k^3+klgn)O(k3+klgn)，其中lg為以10為底的對數。

$100pts$

手推！發現Sn=Cn+kk+1S_n=C_{n+k}^{k+1}Sn?=Cn+kk+1?，那么就可以$O(klgn)$出答案了。