洛谷团队月赛题:题解

$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)$出答案了。