类欧几里得算法学习笔记

如何求\(\sum_{i=0}^ni^{k1}\lfloor\frac{ai+b}{c}\rfloor^{k2}\)？\((1\leqslant n,a,b,c\leqslant10^9,k1+k2\leqslant 10)\)

设\(f(n,a,b,c)[k1][k2]\)表示原式的值，则：

若\(a\geqslant c\)，设\(a=pc+q(0\leqslant q<c)\)，则
\[\begin{align} &\;\;\;\;\;f(n,a,b,c)[k1][k2]\&=\sum_{i=0}^ni^{k1}\lfloor\frac{ai+b}{c}\rfloor^{k2}\&=\sum_{i=0}^ni^{k1}(pi+\lfloor\frac{qi+b}{c}\rfloor)^{k2}\&=\sum_{i=0}^ni^{k1}\sum_{j=0}^{k2}\text{C}_{k2}^jp^ji^j\lfloor\frac{qi+b}{c}\rfloor^{k2-j}\&=\sum_{j=0}^{k2}\text{C}_{k2}^jp^j\sum_{i=0}^ni^{k1+j}\lfloor\frac{qi+b}{c}\rfloor^{k2-j}\&=\sum_{j=0}^{k2}\text{C}_{k2}^jp^jf(n,q,b,c)[k1+j][k2-j] \end{align}\]
只需递归计算\(f(n,q,b,c)\)并\(O(k^3)\)处理即可。
若\(b\geqslant c\)，设\(b=pc+q(0\leqslant q<c)\)，则
\[\begin{align} &\;\;\;\;\;f(n,a,b,c)[k1][k2]\&=\sum_{i=0}^ni^{k1}\lfloor\frac{ai+b}{c}\rfloor^{k2}\&=\sum_{i=0}^ni^{k1}(p+\lfloor\frac{ai+q}{c}\rfloor)^{k2}\&=\sum_{i=0}^ni^{k1}\sum_{j=0}^{k2}\text{C}_{k2}^jp^j\lfloor\frac{ai+q}{c}\rfloor^{k2-j}\&=\sum_{j=0}^{k2}\text{C}_{k2}^jp^j\sum_{i=0}^ni^{k1}\lfloor\frac{ai+q}{c}\rfloor^{k2-j}\&=\sum_{j=0}^{k2}\text{C}_{k2}^jp^jf(n,a,q,c)[k1][k2-j] \end{align}\]
只需递归计算\(f(n,a,q,c)\)并\(O(k^3)\)处理即可。

(to be continued...)

类欧几里得算法学习笔记

原文：https://www.cnblogs.com/ztc03/p/11973996.html