好文收藏夹

比赛总结 \mathsf{MtOI2019(Math~theory~OI)} M t O I 2 0 1 9 ( M a t h   t h e o r y   O I )  结束了，各位蓝名神仙(wlp等)爆踩众多红名(包括出题人)的现象，再次在这炼狱般的比赛中出现！ 难度请以实际题目为准，比赛描述纯属放p！ 本次比赛非常好的区分了数学水平高和数学水平低的OIer们，为洛谷贡献了6道宝(du)贵(liu)的数学题，堪比洛谷公开赛的一个模范。（ 不要脸 ） 希望本次比赛能为各位数学水平不那么好的OIer们敲响警钟，为各大OIer提供数学题在OI中大量出现的例子，并锻炼OIer们的卡常数技巧。 本次比赛的  \mathsf{Rank} R a n k  前5：  \mathsf m \color{red} \mathsf{oorhsum} m o o r h s u m  ，  \mathsf J \color{red} \mathsf{OHNKRAM} J O H N K R A M  ，  \mathsf k \color{red} \mathsf{imi0503} k i m i 0 5 0 3  ，  \mathsf R \color{red} \mathsf{ehtafGniyduts} R e h t a f G n i y d u t s  ，  \mathsf l \color{red} \mathsf{jc1301} l j c 1 3 0 1 本次比赛有  1 1  个人  \color{red} \mathsf{AK} A K  ：  \mathsf m \color{red} \mathsf{oorhsum} m o o r h s u m  ， dmy txdy! ， prprpr 请获奖的选手在2019/8/31前联系disangan233，QQ：451954765（请备注信息），逾期作废。 虽然神仙们都不屑于进团队和拿那点小钱。 题目总结 A. 永夜的报应 此题以签到为出题目标，为暴力选手提供了...

upd：之前式子有一点锅，现已修复。 这其实是一个很水的套路题。。 首先容易看出来  f(x,0) f ( x , 0 )  是个线性递推的形式，要求的是其  k k  阶前缀积。 要求乘积不太好搞，可以对  2 2  取一下对数，化乘为加。 于是问题转化为： 一个数列  a a  ： \large a_n=n\space(n\le42) a n ​ = n   ( n ≤ 4 2 ) \large a_n=\sum\limits_{i=1}^{42}ia_{n-i}\space(n\ge 43) a n ​ = i = 1 ∑ 4 2 ​ i a n − i ​   ( n ≥ 4 3 ) 求它  k k  阶前缀和的第  n n  项。 关于线性递推式的高阶前缀和有一个优美的性质。 设数列  a a  的递推系数为  f f  ，那么在  f f  前面加个  -1 − 1  ，然后做  k k  阶差分得到的序列即  a a  的  k k  阶前缀和的递推式。( 当然要在后面扩展  k k  项，同时最后去掉  -1 − 1  ) 在此简短证明一下，设： \large a_n=\sum\limits_{i=1}^kf_ia_{n-i} a n ​ = i = 1 ∑ k ​ f i ​ a n − i ​ \large b_n=\sum\limits_{i=1}^na_i b n ​ = i = 1 ∑ n ​ a i ​ \large b_n=b_{n-1}+a_n=b_{n-1}+\sum\limits_{i=1}^kf_ia_{n-i} b n ​ = b n − 1 ​ + a n ​ = b n − 1 ​ + i = 1 ∑ k ​ f i ​ a n − i ​ \large = b_{n-1}+\sum\limits_{i=1}^kf_i(b_{n-i}-b_{n-i-1}) = b n − ...