洛谷团队月赛题:题解

$10pts$10pts

暴力算不解释，时间复杂度 $O(kn+k^2)$O(kn+k2)。

$30pts$30pts

我们观察到 $n$n很大，杨辉三角会T，直接算会上溢，所以需要预处理出 $1$1~ $k$k逆元再算，时间复杂度 $O(kn+nlogk+n^2)$O(kn+nlogk+n2)或 $O(kn+n+k+n^2)$O(kn+n+k+n2)。

$60pts$60pts

代入几个 $k$k，发现数列通项是一个多项式，故 $S_n$Sn​也有一个通项；观察次数，可知 $a_n$an​等于一个 $k$k次多项式，那么 $S_n$Sn​等于一个 $k+1$k+1次方多项式，拉格朗日插值+高斯消元解出 $S_n$Sn​表达式即可，当然也要预处理逆元，时间复杂度为 $O\left(k^3\right)$O(k3)。

$80pts$80pts

不要被 $n$n吓到，还是先算表达式，代入时高精度取模即可，时间复杂度为 $O(k^3+klgn)$O(k3+klgn)，其中lg为以10为底的对数。

$100pts$100pts

手推！发现 $S_n=C_{n+k}^{k+1}$Sn​=Cn+kk+1​，那么就可以 $O\left(klgn\right)$O(klgn)出答案了。