类欧几里得算法

未分类

---

给定$n,a,b,c,k_1,k_2$,求

$$\sum_{i=0}^ni^{k_1}{\lfloor\frac{ai+b}{c}\rfloor^{k_2}}$$
输出结果对$10^9+7$取模.
$(1\leq n,a,b,c \leq 10^9,0\leq k_1+k_2 \leq 10).$
特殊的,这里定义$0^0=1$.

解析:

考虑$f(n,a,b,c)$计算全部满足$k_1+k_2\leq 10$的$(k_1,k_2)$有序二元组.
定义$S(k,n)=\sum_{i=0}^ni^k.$

在这里断定可以把式子等价转换成$a<c, b<c$的情况,下面给出证明:

$$\begin{align*} ans&=\sum_{i=0}^ni^{k_1}\lfloor\frac{ai+b}{c}\rfloor^{k_2} \\ &= \sum_{i=0}^ni^{k_1}\lfloor\frac{ (a\%c+\lfloor\frac{a}{c}\rfloor *c)i+(b\%c+\lfloor\frac{b}{c}\rfloor*c) }{c}\rfloor^{k_2} \\ &= \sum_{i=0}^ni^{k_1}(\lfloor \frac{(a\%c)*i+b\%c}{c} \rfloor + \lfloor \frac{a}{c}\rfloor *i + \lfloor \frac{b}{c} \rfloor)^{k_2} \\ & = \sum_{i=0}^ni^{k_1} \sum_{j=0}^{k_2} C_{k_2}^{j} \lfloor \frac{(a\%c)*i+b\%c}{c} \rfloor^j (\lfloor \frac{a}{c}\rfloor *i + \lfloor \frac{b}{c} \rfloor)^{k_2-j} \\ &= \sum_{i=0}^ni^{k_1} \sum_{j=0}^{k_2} C_{k_2}^{j} \lfloor \frac{(a\%c)*i+b\%c}{c} \rfloor^j \sum_{k=0}^{k_2-j}C_{k_2-j}^{k}(\lfloor \frac{a}{c}\rfloor *i)^k(\lfloor \frac{b}{c} \rfloor)^{k_2-j-k} \\ &=\sum_{j=0}^{k_2}\sum_{k}^{k_2-j}C_{k_2}^{j}C_{k_2-j}^{k}\lfloor \frac{a}{c}\rfloor^k\lfloor \frac{b}{c}\rfloor^{k_2-j-k}\sum_{i=0}^{n}i^{k_1+k}\lfloor \frac{(a\%c)*i+b\%c}{c} \rfloor^j \end{align*}$$

显然把计算$f(n,a,b,c)$转换成计算了$f(n,a\%c,b\%c,c).$下面只讨论$a<c,b<c$的情况.

令$m=\lfloor\frac{a*n+b}{c}\rfloor-1.$

特殊处理$a=0$的情况:

$$\begin{align*} ans&=\sum_{i=0}^ni^{k_1}\lfloor \frac{b}{c} \rfloor^{k_2} \\ &= \lfloor \frac{b}{c} \rfloor^{k_2}S(k_1,n) \end{align*}$$

在$a\neq0$时:

特殊处理$k_2=0$的情况:

$$\begin{align*} ans=\sum_{i=0}^ni^{k_1}=S(k_1,n) \end{align*}$$

在$k_2>0$时:

$$\begin{align*} ans &= \sum_{i=0}^ni^{k_1}{\lfloor\frac{ai+b}{c}\rfloor^{k_2}} \\ &= \sum_{i=0}^ni_{k_1}\sum_{y=0}^m[y<\lfloor\frac{ai+b}{c}\rfloor]((y+1)^{k_2}-y^{k_2}) \end{align*}$$
在这里单独处理一下$y<\lfloor\frac{ai+b}{c}\rfloor$:
$$\begin{align*} & y<\lfloor\frac{ai+b}{c}\rfloor \\ <=>& y+1 \leq \lfloor\frac{ai+b}{c}\rfloor \\ <=>& c(y+1)\leq ai+b \\ <=>& cy+c-b-1 < ai \\ <=>& i>\lfloor \frac{cy+c-b-1}{a} \rfloor \end{align*}$$
替换原式得:
$$\begin{align*} ans &= \sum_{i=0}^ni^{k_1}\sum_{y=0}^m[i>\lfloor \frac{cy+c-b-1}{a} \rfloor]((y+1)^{k_2}-y^{k_2}) \\ &= \sum_{y=0}^{m}((y+1)^{k_2}-y^{k_2})\sum_{i=0}^{n}i^{k_1}[i>\lfloor \frac{cy+c-b-1}{a} \rfloor] \\ &= \sum_{y=0}^m\sum_{i=0}^{k_2-1}C_{k_2}^{i}y^{i}\sum_{i=0}^{n}i^{k_1}[i>\lfloor \frac{cy+c-b-1}{a} \rfloor] \\ &= \sum_{y=0}^m\sum_{i=0}^{k_2-1}C_{k_2}^{i}y^{i}(S(k_1,n)-S(k_1,\lfloor \frac{cy+c-b-1}{a} \rfloor)) \\ &= \sum_{y=0}^m\sum_{i=0}^{k_2-1}C_{k_2}^{i}y^{i}S(k_1,n)-\sum_{y=0}^m\sum_{i=0}^{k_2-1}C_{k_2}^{i}y^{i}S(k_1,\lfloor \frac{cy+c-b-1}{a} \rfloor) \\ &= \sum_{i=0}^{k_2-1}C_{k_2}^{i}S(i,m)S(k_1,n)-\sum_{y=0}^m\sum_{i=0}^{k_2-1}C_{k_2}^{i}y^{i}S(k_1,\lfloor \frac{cy+c-b-1}{a} \rfloor) \\ \end{align*}$$

这里引用一个结论:
$S(k,n)$是一个与$n$相关的$k+1$次多项式,也就是:

$$S(k,n)=\sum_{i=0}^{k+1}H_{(k,i)}n^i$$
$H_{(k,i)}$是待定系数,可以用高斯消元法求解该系数(还可以用拉格朗日插值法,伯努利数等方法求解).
上式前部分可以直接求解,接下来只考虑后半部分式子.
使用该结论,上式后部分可以转换成:
$$\begin{align*} last&= \sum_{y=0}^m\sum_{i=0}^{k_2-1}C_{k_2}^{i}y^{i}S(k_1,\lfloor \frac{cy+c-b-1}{a} \rfloor) \\ &= \sum_{y=0}^{m}\sum_{i=0}^{k_2-1}C_{k_2}^{i}y^i\sum_{j=0}^{k_1+1}H_{(k_1,j)}\lfloor \frac{cy+c-b-1}{a} \rfloor^{j} \\ &= \sum_{i=0}^{k_2-1}\sum_{j=0}^{k_1+1} C_{k_2}^iH_{(k_1,j)} \sum_{y=0}^my^i\lfloor \frac{cy+c-b-1}{a} \rfloor^{j} \end{align*}$$
这里就把计算$f(n,a,b,c)$转换成了计算$f(m,c,c-b-1,a)$.
这里考虑$m$有可能退化成负数,所以需要在$f(n,a,b,c)$函数体里面特判$n<0$的情况,此时返回值全部是$0$.
可以通过上述式子看出在全部计算过程$k_1,k_2$的和不会超过$10$,所以只计算$k_1+k_2\leq 10$的情况是足够的.
该递归算法的递归层数和欧几里得算法的递归层数是一样的,即是$O(logn)$层,递归计算每层需要$O((k_1+k_2)^4)$的时间,所以总时间复杂度是$O((k_1+k_2)^4logn)$.

原题:$LibreOJ-138$,链接:https://loj.ac/problem/138
参考$AC$代码:https://loj.ac/submission/125368