类欧几里得
类欧几里得
对于给定的元 \(a,b,c,n\)：
设 \(f(i)=\lfloor\frac{ai+b}{c}\rfloor\)。
求：
- \(F(a,b,c,n)=\sum_0^nf(i)\)，
- \(G(a,b,c,n)=\sum_0^nf(i)^2\)，
- \(H(a,b,c,n)=\sum_0^ni\cdot f(i)\)。
Part1
\(a\ge c\) 或 \(b\ge c\)
$=+i+$
\(\displaystyle F(a,b,c,n)=F(a\mod c,b\mod c,c,n)+\frac{n(n+1)\lfloor\frac{a}{c}\rfloor}{2}+(n+1)\lfloor\frac{b}{c}\rfloor\)
\(a<c\) 且 \(b<c\)
\[ \begin{aligned} F(a,b,c,n) =&\sum_0^n f(i) \\ = &\sum_{i=0}^n\sum_{j=0}^{f(i)-1} 1 \\ = &\sum_{i=0}^n\sum_{j=0}^{\infty}[j<f(i)] \\ = &\sum_{j=0}^{f(n) -1}\sum_{i=0}^{n}[j<f(i)] \end{aligned} \]
其中:
\[ \begin{aligned} \ [j<\lfloor\frac{ai+b}{c}\rfloor] &=[j<\lceil\frac{ai+b-c+1}{c}\rceil] \\ &=[cj<ai+b-c+1] \\ &=[ai>cj-b+c-1] \\ &=[i>\lfloor\frac{cj-b+c-1}{a}\rfloor] \\ F(a,b,c,n)&= \sum_{j=0}^{f(n)-1 }\sum_{i=0}^{n}[i>\lfloor\frac{cj-b+c-1}{a}\rfloor \\ &=\sum_{j=0}^{f(n)-1} n-\lfloor\frac{cj-b+c-1}{a}\rfloor \\ F(a,b,c,n)&=n\cdot f(n)-F(c,-b+c-1,a,f(n)-1) \end{aligned} \]
每次操作交换了 \(a,c\) 然后再次取模，递归边界是 \(a=0\)，复杂度是 \(O(\log n)\)。
Part2
\(G(a,b,c,n)=\sum_0^nf(i)^2\)
\(a\ge c\) 或 \(b\ge c\)
设\(\lfloor \frac{a}{c}\rfloor=x,\lfloor \frac{b}{c}\rfloor=y\)
\(\lfloor\frac{ai+b}{c}\rfloor^2=(\lfloor\frac{(a \mod c)i+(b \mod c)}{c}\rfloor+ix+y)^2\)
\(=\lfloor\frac{(a \mod c)i+(b \mod c)}{c}\rfloor^2+2\lfloor\frac{(a \mod c)i+(b \mod c)}{c}\rfloor\cdot (ix+y)+(ix+y)^2\)
\(G(a,b,c,n)=\)
\(G(a\mod c,b\mod c,c,n)+2x H(a\mod c,b\mod c,n)+2y F(a\mod c,b\mod c,c,n)\)
\(+\frac{n(n+1)(2n+1)x^2}{6}+(n+1)y^2+n(n+1)xy\)
\(a<c\) 且 \(b<c\)
\[ \begin{aligned} G(a,b,c,n) &=\sum_0^nf(i)^2 \\ &= 2 \sum_{i=0}^n\frac{f(i)(f(i)-1)}{2}+\frac{f(i)}{2} \\ &=2 \sum_{i=0}^n\sum_{j=0}^{f(i)-1}j+\frac{1}{2} \\ &= 2\sum_{i=0}^n\sum_{j=0}^{\infty}(j+\frac{1}{2})[j<f(i)] \\ &= 2\sum_{j=0}^{f(n)-1}\sum_{i=0}^{n}(j+\frac{1}{2})[j<f(i)] \\ &=2 \sum_{j=0}^{f(n)-1}\sum_{i=0}^{n}(j+\frac{1}{2})[i>\lfloor\frac{cj-b+c-1}{a}\rfloor] \\ &=2\sum_{j=0}^{f(n)-1} (j+\frac{1}{2})(n-\lfloor\frac{cj-b+c-1}{a}\rfloor) \\ G(a,b,c,n)&=nf(n)^2-2H(c,-b+c-1,a,f(n)-1)-F(c,-b+c-1,a,f(n)-1) \end{aligned} \]
Part3
\(H(a,b,c,n)=\sum_0^ni\cdot f(i)\)
\(a\ge c\) 或 \(b\ge c\)
$i=i(+i+) $
\(i\cdot \lfloor\frac{ai+b}{c}\rfloor=i\cdot \lfloor\frac{(a \mod c)i+(b \mod c)}{c}\rfloor+i^2\lfloor \frac{a}{c}\rfloor +i\lfloor \frac{b}{c}\rfloor\)
\(H(a,b,c,n)=H(a\mod c,b\mod c,c,n)+\frac{n(n+1)(2n+1)\lfloor\frac{a}{c}\rfloor}{6}+\frac{n(n+1)\lfloor\frac{b}{c}\rfloor}{2}\)
\(a<c\) 且 \(b<c\)
$$ \[\begin{aligned} H(a,b,c,n)=\sum_i^n i\cdot f(i) \\ &= \sum_{i=0}^n\sum_{j=0}^{f(i)-1} i \\ &= \sum_{j=0}^{f(n) -1}\sum_{i=0}^{n}i\cdot [j<\lfloor\frac{ai+b}{c}\rfloor] \\ &=\sum_0^{f(n)-1}\sum_{i=0}^n i\cdot [i>\lfloor\frac{cj-b+c-1}{a}\rfloor] \end{aligned}\]$$
设 \(f'(i)=\lfloor\frac{ci-b+c-1}{a}\rfloor\)。
\[ \begin{aligned} H(a,b,c,n)&= \sum_{j=0}^{f(n)-1 }\sum_{i=f'(j)+1}^{n}i \\ &= \sum_{j=0}^{f(n)-1 }\frac{(f'(j)+1+n)(n-f'(j))}{2} \\ &= \sum_{j=0}^{f(n)-1 } \frac{-f'(j)^2-f'(j)+n(n+1)}{2} \\ H(a,b,c,n)&=\frac{f(n)n(n+1)-G(c,-b+c-1,a,f(n)-1)-F(c,-b+c-1,a,f(n)-1)}{2} \end{aligned} \]
Tip:
这个多个函数的情况，如果直接递归写复杂度极高
所以需要把访问到的所有状态存下来递推，就能保证复杂度 \(O(\log n)\)。
1 | const int N=1010,P=998244353; |