疯狂函数

给定整数a、b、c，定义疯狂函数$F(n)$如下： $$F(n)=\begin{cases}n-c & n>b, \\ F(a+F(a+F(a+F(a+n)))) & n\le b. \end{cases}$$ 此外，定义 $$S(a,b,c)=\sum_{n=0}^b F(n).$$ 例如$a=50, b=2000, c=40$时有$F(0)=3240, F(2000)=2040$，以及$S(50,2000,40)=5204240$。

求$S(21^7,7^{21},12^7)$的最后9位数字。

本题难度:

解答

显然$n>b$时F是线性函数。经过尝试可以发现$n\le b$时F是分段线性的函数，每段的斜率都为1，且自变量的跨度为a，相邻的段之间满足 $$F(n+a)=F(n)+3(a-c),$$ 因此事实上只需要作两次等差数列求和即可，结果是$291504964$。

a,b,c,m=21**7, 7**21,12**7, 10**9

s=lambda x,d,n:n*(x+x+(n-1)*d)/2

q,r=(b+1)/a,(b+1)%a
print (s(s(b+4*(a-c),-1,a),a*3*(a-c),q)+s(b+4*(a-c)+q*3*(a-c),-1,r))%m