当前位置：首页 > 编程资源 > 编程问答 >内容正文

编程问答

洛谷团队月赛题:题解

发布时间：2023/12/13 编程问答 44 豆豆

生活随笔收集整理的这篇文章主要介绍了洛谷团队月赛题:题解小编觉得挺不错的,现在分享给大家,帮大家做个参考.

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

转载于:https://www.cnblogs.com/ShineEternal/p/10834278.html

以上是生活随笔为你收集整理的洛谷团队月赛题:题解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。