暴力算不解释,时间复杂度。
我们观察到很大,杨辉三角会T,直接算会上溢,所以需要预处理出~逆元再算,时间复杂度或。
代入几个,发现数列通项是一个多项式,故也有一个通项;观察次数,可知等于一个次多项式,那么等于一个次方多项式,拉格朗日插值+高斯消元解出表达式即可,当然也要预处理逆元,时间复杂度为。
不要被吓到,还是先算表达式,代入时高精度取模即可,时间复杂度为,其中lg为以10为底的对数。
手推!发现,那么就可以出答案了。
暴力算不解释,时间复杂度。
我们观察到很大,杨辉三角会T,直接算会上溢,所以需要预处理出~逆元再算,时间复杂度或。
代入几个,发现数列通项是一个多项式,故也有一个通项;观察次数,可知等于一个次多项式,那么等于一个次方多项式,拉格朗日插值+高斯消元解出表达式即可,当然也要预处理逆元,时间复杂度为。
不要被吓到,还是先算表达式,代入时高精度取模即可,时间复杂度为,其中lg为以10为底的对数。
手推!发现,那么就可以出答案了。