洛谷团队月赛题:题解

$10 p t s$

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

$30 p t s$

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

$60 p t s$

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

$80 p t s$

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

$100 p t s$

手推！发现 $S_n=C_{n+k}^{k+1}$ ，那么就可以 $O (k l g n)$ 出答案了。