如何求(sum_{i=0}^ni^{k1}lfloorfrac{ai+b}{c} floor^{k2})？((1leqslant n,a,b,cleqslant10^9,k1+k2leqslant 10))
设(f(n,a,b,c)[k1][k2])表示原式的值，则：
若(ageqslant c)，设(a=pc+q(0leqslant q<c))，则
[egin{align}
&;;;;;f(n,a,b,c)[k1][k2]\
&=sum_{i=0}^ni^{k1}lfloorfrac{ai+b}{c}
floor^{k2}\
&=sum_{i=0}^ni^{k1}(pi+lfloorfrac{qi+b}{c}
floor)^{k2}\
&=sum_{i=0}^ni^{k1}sum_{j=0}^{k2} ext{C}_{k2}^jp^ji^jlfloorfrac{qi+b}{c}
floor^{k2-j}\
&=sum_{j=0}^{k2} ext{C}_{k2}^jp^jsum_{i=0}^ni^{k1+j}lfloorfrac{qi+b}{c}
floor^{k2-j}\
&=sum_{j=0}^{k2} ext{C}_{k2}^jp^jf(n,q,b,c)[k1+j][k2-j]
end{align}]
只需递归计算(f(n,q,b,c))并(O(k^3))处理即可。
若(bgeqslant c)，设(b=pc+q(0leqslant q<c))，则
[egin{align}
&;;;;;f(n,a,b,c)[k1][k2]\
&=sum_{i=0}^ni^{k1}lfloorfrac{ai+b}{c}
floor^{k2}\
&=sum_{i=0}^ni^{k1}(p+lfloorfrac{ai+q}{c}
floor)^{k2}\
&=sum_{i=0}^ni^{k1}sum_{j=0}^{k2} ext{C}_{k2}^jp^jlfloorfrac{ai+q}{c}
floor^{k2-j}\
&=sum_{j=0}^{k2} ext{C}_{k2}^jp^jsum_{i=0}^ni^{k1}lfloorfrac{ai+q}{c}
floor^{k2-j}\
&=sum_{j=0}^{k2} ext{C}_{k2}^jp^jf(n,a,q,c)[k1][k2-j]
end{align}]
只需递归计算(f(n,a,q,c))并(O(k^3))处理即可。
若(c>a)且(c>b)，则有：
[egin{align}
&;;;;;f(n,a,b,c)[k1][k2]\
&=sum_{i=0}^ni^{k1}sum_{j=0}^{lfloorfrac{ai+b}{c}
floor-1}((j+1)^{k2}-[j
eq0]j^{k2})\
&=sum_{j=0}^{lfloorfrac{an+b}{c}
floor-1}((j+1)^{k2}-[j
eq0]j^{k2})sum_{i=0}^n[j<lfloorfrac{ai+b}{c}
floor]i^{k1}\
end{align}]
又
[egin{align}
&;;;;;j<lfloorfrac{ai+b}{c}
floor\
&Leftrightarrow j+1leqslantlfloorfrac{ai+b}{c}
floor\
&Leftrightarrow jc+cleqslant ai+b\
&Leftrightarrow jc+c-b-1<ai\
&Leftrightarrow lfloorfrac{jc+c-b-1}{a}
floor<i
end{align}]
于是，设(T_{i,j})为(sum_{w=0}^{x}w^i)的多项式表达式的(j)次项系数
[egin{align}
&;;;;;f(n,a,b,c)[k1][k2]\
&=sum_{j=0}^{lfloorfrac{an+b}{c}
floor-1}((j+1)^{k2}-[j
eq0]j^{k2})sum_{i=0}^n[i>lfloorfrac{jc+c-b-1}{a}
floor]i^{k1}\
&=sum_{j=0}^{lfloorfrac{an+b}{c}
floor-1}((j+1)^{k2}-[j
eq0]j^{k2})(sum_{i=0}^ni^{k1}-sum_{i=0}^{lfloorfrac{jc+c-b-1}{a}
floor}i^{k1})\
&=lfloorfrac{an+b}{c}
floor^{k2}sum_{i=0}^ni^{k1}-sum_{j=0}^{lfloorfrac{an+b}{c}
floor-1}sum_{p=0}^{k2-1}sum_{q=0}^{k1+1} ext{C}_{k2}^{p}T_{k1,q}j^plfloorfrac{jc+c-b-1}{a}
floor^q\
&=lfloorfrac{an+b}{c}
floor^{k2}sum_{i=0}^ni^{k1}-sum_{p=0}^{k2-1}sum_{q=0}^{k1+1} ext{C}_{k2}^{p}T_{k1,q}sum_{j=0}^{lfloorfrac{an+b}{c}
floor-1}j^plfloorfrac{jc+c-b-1}{a}
floor^q\
&=lfloorfrac{an+b}{c}
floor^{k2}sum_{i=0}^ni^{k1}-sum_{p=0}^{k2-1}sum_{q=0}^{k1+1} ext{C}_{k2}^{p}T_{k1,q}f(lfloorfrac{an+b}{c}
floor-1,c,c-b-1,a)[p][q]
end{align}]
只需递归计算(f(lfloorfrac{an+b}{c} floor-1,c,c-b-1,a))并(O(k^4))处理即可。
当(a=0)或(n)很小时可直接计算。