类欧几里得算法

· · 算法·理论

P5170 【模板】类欧几里德算法

给出 n,a,b,c,分别求解

\begin{aligned} f(a,b,c,n)&=\sum_{i=0}^n \left\lfloor \dfrac{ai+b}{c} \right\rfloor\\ g(a,b,c,n)&=\sum_{i=0}^n \left\lfloor \dfrac{ai+b}{c} \right\rfloor^2\\ h(a,b,c,n)&=\sum_{i=0}^n i\left\lfloor \dfrac{ai+b}{c} \right\rfloor\\ \end{aligned}

多测,T \le 10^5,0 \le n,a,b,c \le 10^9,2 秒,125 MB。

:::::success[题解]

以 f 的求解为例。

  1. 当 a=0 时
f(a,b,c,n)=(n+1) \left\lfloor \dfrac{b}{c} \right\rfloor
  1. 当 a \ge c \lor b \ge c 时

    \begin{aligned} f(a,b,c,n)&=\sum_{i=0}^n \left(\left\lfloor \dfrac{(a \bmod c)i+(b \bmod c)}{c}\right\rfloor+i\left\lfloor \dfrac{a}{c} \right\rfloor+\left\lfloor \dfrac{b}{c} \right\rfloor \right)\\ &=f(a \bmod c, b \bmod c, c, n) + \dfrac{n(n+1)}{2}\left\lfloor \dfrac{a}{c} \right\rfloor+(n+1) \left\lfloor \dfrac{b}{c} \right\rfloor \end{aligned}
  2. 当 a,b < c 时,记 m 为 j 的上界

    \begin{aligned} f(a,b,c,n)&= \sum_{i=0}^n \sum_{j=0}^{m} \left[j \le \left\lfloor \dfrac{ai+b}{c} \right\rfloor\right]\\ &= \sum_{i=0}^n \sum_{j=0}^{m-1} \left[i > \left\lfloor \dfrac{jc+c-b+1}{a} \right\rfloor\right]\\ &= \sum_{j=0}^{m-1}\sum_{i=0}^n \left[i > \left\lfloor \dfrac{jc+c-b+1}{a} \right\rfloor\right]\\ &= \sum_{j=0}^{m-1} \left(n-\left\lfloor \dfrac{jc+c-b+1}{a} \right\rfloor\right)\\ &= nm-f(c,c-b-1,a,m-1) \end{aligned}

每次递归 a,b,c 辗转相除,a=0 终止,由欧几里得的复杂度分析,上述递归式的复杂度也是 O(\log n) 的。

模仿上面的推导写出 g 的求解:

  1. 当 a=0 时

    g(a,b,c,n)=(n+1) \left\lfloor \dfrac{b}{c} \right\rfloor^2
  2. 当 a \ge c \land b \ge c 时

    \begin{aligned} g(a,b,c,n)&=\sum_{i=0}^n \left(\left\lfloor \dfrac{(a \bmod c)i+(b \bmod c)}{c}\right\rfloor+i\left\lfloor \dfrac{a}{c} \right\rfloor+\left\lfloor \dfrac{b}{c} \right\rfloor \right)^2\\ &=\sum_{i=0}^n \left(\left\lfloor \dfrac{(a \bmod c)i+(b \bmod c)}{c}\right\rfloor^2 + i^2 \left\lfloor \dfrac{a}{c} \right\rfloor^2 + \left\lfloor \dfrac{b}{c} \right\rfloor^2 + 2i \left\lfloor \dfrac{a}{c} \right\rfloor \left\lfloor \dfrac{(a \bmod c)i+(b \bmod c)}{c}\right\rfloor + 2\left\lfloor \dfrac{b}{c} \right\rfloor \left\lfloor \dfrac{(a \bmod c)i+(b \bmod c)}{c}\right\rfloor + 2i \left\lfloor \dfrac{a}{c} \right\rfloor \left\lfloor \dfrac{b}{c} \right\rfloor\right)\\ &=g(a \bmod c, b\bmod c, c, n) +\left\lfloor \dfrac{a}{c} \right\rfloor^2 \sum_{i=0}^n i^2+(n+1) \left\lfloor \dfrac{b}{c} \right\rfloor^2 +2\left\lfloor \dfrac{a}{c} \right\rfloor h(a \bmod c, b\bmod c, c, n) + 2\left\lfloor \dfrac{b}{c} \right\rfloor f(a \bmod c, b\bmod c, c, n) + 2 \left\lfloor \dfrac{a}{c} \right\rfloor \left\lfloor \dfrac{b}{c} \right\rfloor \sum_{i=0}^n i\\ &= g(a \bmod c, b\bmod c, c, n) +\left\lfloor \dfrac{a}{c} \right\rfloor^2 \dfrac{n(n+1)(2n+1)}{6} +(n+1) \left\lfloor \dfrac{b}{c} \right\rfloor^2 +2\left\lfloor \dfrac{a}{c} \right\rfloor h(a \bmod c, b\bmod c, c, n) + 2\left\lfloor \dfrac{b}{c} \right\rfloor f(a \bmod c, b\bmod c, c, n) + 2 \left\lfloor \dfrac{a}{c} \right\rfloor \left\lfloor \dfrac{b}{c} \right\rfloor \dfrac{n(n+1)}{2} \end{aligned}
  3. 当 a,b<c 时

    \begin{aligned} g(a,b,c,n)&= \sum_{i=0}^n \sum_{j=0}^{m} \left[j \le \left\lfloor \dfrac{ai+b}{c} \right\rfloor^2\right]\\ \end{aligned}

    处理平方项的方法是 x^2=2 \dbinom{x}{2}+x=2\sum\limits_{i=0}^{x-1}i+x。代入:

    \begin{aligned} g(a,b,c,n)&= \sum_{i=0}^n \left(2\sum_{j=0}^{m-1} j \left[j<\left\lfloor \dfrac{ai+b}{c} \right\rfloor\right]+\left\lfloor \dfrac{ai+b}{c} \right\rfloor\right)\\ &=2 \sum_{i=0}^n \sum_{j=0}^{m-1} j \left[j<\left\lfloor \dfrac{ai+b}{c} \right\rfloor\right]+f(a,b,c,n)\\ &=2 \sum_{j=0}^{m-1} j \sum_{i=0}^n \left[i > \left\lfloor \dfrac{jc+c-b+1}{a} \right\rfloor\right]+f(a,b,c,n)\\ &= 2 \sum_{j=0}^{m-1} j \left(n-\left\lfloor \dfrac{jc+c-b+1}{a} \right\rfloor\right)+f(a,b,c,n)\\ &= 2n \sum_{j=0}^{m-1} j-2\sum_{j=0}^{m-1}j\left\lfloor \dfrac{jc+c-b+1}{a} \right\rfloor+f(a,b,c,n)\\ &=nm(m-1)-2h(c,c-b-1, a,m-1)+f(a,b,c,n)\\ \end{aligned}

我们发现 g 的求解依赖于 h。继续推 h 的式子

  1. 当 a=0 时

    h(a,b,c,n)=\left\lfloor \dfrac{b}{c} \right\rfloor \sum_{i=0}^n i= \left\lfloor \dfrac{b}{c} \right\rfloor \dfrac{n(n+1)}{2}
  2. 当 a \ge c \land b \ge c 时

    \begin{aligned} h(a,b,c,n)&=\sum_{i=0}^n i\left(\left\lfloor \dfrac{(a \bmod c)i+(b \bmod c)}{c}\right\rfloor+i\left\lfloor \dfrac{a}{c} \right\rfloor+\left\lfloor \dfrac{b}{c} \right\rfloor \right)\\ &=\sum_{i=0}^n i\left\lfloor \dfrac{(a \bmod c)i+(b \bmod c)}{c}\right\rfloor+i^2\left\lfloor \dfrac{a}{c} \right\rfloor+i\left\lfloor \dfrac{b}{c} \right\rfloor \\ &=h(a \bmod c, b\bmod c, c, n)+\left\lfloor \dfrac{a}{c} \right\rfloor \sum_{i=0}^n i^2+\left\lfloor \dfrac{b}{c} \right\rfloor \sum_{i=0}^n i\\ &=h(a \bmod c, b\bmod c, c, n)+\left\lfloor \dfrac{a}{c} \right\rfloor \dfrac{n(n+1)(2n+1)}{6}+\left\lfloor \dfrac{b}{c} \right\rfloor \dfrac{n(n+1)}{2} \end{aligned}
  3. 当 a,b<c 时

    \begin{aligned} h(a,b,c,n)&=\sum_{i=0}^n i\sum_{j=0}^m \left[j \le \left\lfloor \dfrac{ai+b}{c} \right\rfloor \right]\\ &= \sum_{i=0}^n i\sum_{j=0}^m \left[i > \left\lfloor \dfrac{jc+c-b+1}{a} \right\rfloor\right]\\ &= \sum_{j=0}^m \sum_{i=0}^n i \left[i > \left\lfloor \dfrac{jc+c-b+1}{a} \right\rfloor\right] \end{aligned}

    内层求和的本质是等差数列求和。记 x_j=\left\lfloor \dfrac{jc+c-b+1}{a} \right\rfloor 代入求和公式

    \begin{aligned} h(a,b,c,n) &= \sum_{j=0}^m \dfrac{(x_j+n+1)(n-x_j)}{2}\\ &= \dfrac{1}{2}\sum_{j=0}^m (-x_j^2+n^2+n-x_j)\\ &= \dfrac{ (n^2+n)(m+1)}{2}-\dfrac{1}{2} \sum_{j=0}^{m-1} (x_j^2+x_j)\\ &= \dfrac{ (n^2+n)m}{2}-\dfrac{1}{2} g(c,c-b-1, a,m-1)-\dfrac{1}{2} f(c,c-b-1, a,m-1) \end{aligned}

注意到 f,g,h 子问题的规模相同。我们的实现方式时,在递归时传递三元组 (f,g,h),大常数 O(\log n)。

:::::

:::::info[代码]

const mint i2 = ~mint(2), i6 = ~mint(6);
tuple<mint, mint, mint> solve(int a, int b, int c, int n) {
    auto f2 = [&](int n) -> mint {
        return mint(n) * (n + 1) * i2;
    };
    auto f6 = [&](int n) -> mint {
        return mint(n) * (n + 1) * (2 * n + 1) * i6;
    };
    if (a == 0) {
        return {
            mint(n+1) * (b/c),
            mint(n+1) * (b/c) * (b/c), 
            f2(n) * (b/c)
        };
    }
    if (a >= c || b >= c) {
        auto [f, g, h] = solve(a % c, b % c, c, n);
        return {
            f + f2(n) * (a/c) + mint(n+1) * (b/c),
            g + f6(n) * (a/c) * (a/c) + mint(n+1) * (b/c) * (b/c) + h * (a/c) * 2 + f * (b/c) * 2 + f2(n) * (a/c) * (b/c) * 2,
            h + f6(n) * (a/c) + f2(n) * (b/c)
        };
    }
    int m = (1LL * a * n + b) / c;
    auto [f, g, h] = solve(c, c - b - 1, a, m - 1);
    return {
        mint(n) * m - f,
        mint(n) * m * (m - 1) - 2 * h + mint(n) * m - f,
        (mint(n) * n + n) * m * i2 - g * i2 - f * i2
    };
}

int n, a, b, c;
void _main() {
    cin >> n >> a >> b >> c;
    auto [f, g, h] = solve(a, b, c, n);
    cout << f << ' ' << g << ' ' << h << '\n';
}

:::::

ABC313G Redistribution of Piles

给出一个长为 n 的序列 a_i。初始有变量 s=0,你可以进行任意次以下操作:

  • 令所有 a_i \ge 1 的 a_i 减去 1,并将这些值加到 s 上。
  • 若 s \ge n,令 s \gets s-n 并令 a_i \gets a_i+1。

求所有可能得到的本质不同序列数,对 998244353 取模。

:::::success[题解]

考察操作序列的形态。不难发现 \tt{21} 是没有意义的,那么有效的操作序列必然形如 \tt{11\cdots122 \cdots 2}。

先对 a_i 升序排序,并设其差分 d_i=a_i-a_{i-1}。那么操作一就是对 d_i 中第一个非零位置减 1,操作二是对 d_1 加 1。

顺序扫描 i=2,3,\cdots,n 并处理差分项 d_i。设在当前消耗 d_i 的过程中是第 j 次操作一,式子是

\sum_{j=1}^{d_i} \left(1+\left\lfloor \dfrac{s+j(n-i+1)}{n}\right\rfloor\right)

其中 s 是我们动态维护的值,初始 s=d_1n,每轮操作结束后 s \gets s+d_i c_i。

上面那个求和式是类欧几里得的形式,可以做到 O(n \log V) 求解。

:::::

:::::info[代码]

void _main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) d[i] = a[i] - a[i - 1];
    mint res = 1 + d[1];
    i64 s = 1LL * d[1] * n;
    for (int i = 2; i <= n; i++) {
        if (d[i] == 0) continue;
        res += d[i] + $0(solve(n-i+1, s, n, d[i])) - s/n;
        s += d[i] * (n-i+1);
    } cout << res;
} 

:::::

ABC283Ex Popcount Sum

给出 n,m,r。求

\sum_{i=1}^n \operatorname{popcount}(i) \times [i \bmod m =r]

多测,T \le 10^5,n,m \le 10^9,4 秒,1024 MB。

:::::success[题解]

不难发现,题目所求的是一个等差数列的 \operatorname{popcount} 之和。写成等差数列的形式并拆位:

\begin{aligned} &\sum_{i=0}^N \operatorname{popcount}(im+r)\\ =& \sum_{i=0}^N \sum_{d \ge 0} \left\lfloor \dfrac{im+r}{2^d}\right\rfloor \bmod 2\\ =& \sum_{d \ge 0} \sum_{i=0}^N \left\lfloor \dfrac{im+r}{2^d}\right\rfloor \bmod 2 \end{aligned}

如果只有 \left\lfloor \dfrac{im+r}{2^d}\right\rfloor 可以用类欧处理,我们要设法转化掉 \bmod 2。

在位运算的意义下考虑,我们要求的是 x >> d & 1,将其等价为 x >> d - (x >> (d + 1)) << 1 即可。原因是,我们只要保留 x >> d 的末位,将低 d+1 位删去后补 0,二者作差即可答案。

代入得

\begin{aligned} & \sum_{d \ge 0} \sum_{i=0}^N \left\lfloor \dfrac{im+r}{2^d}\right\rfloor \bmod 2\\ &=\sum_{d \ge 0} \sum_{i=0}^N \left(\left\lfloor \dfrac{im+r}{2^d}\right\rfloor -2\left\lfloor \dfrac{im+r}{2^{d+1}}\right\rfloor\right)\\ &=\sum_{d \ge 0}\left( \sum_{i=0}^N \left\lfloor \dfrac{im+r}{2^d}\right\rfloor -2\sum_{i=0}^N\left\lfloor \dfrac{im+r}{2^{d+1}}\right\rfloor\right)\\ \end{aligned}

两部分都可以类欧。复杂度 O(T\log^2 V)。

:::::

:::::info[代码]

#define int long long
using atcoder::floor_sum;
int n, m, r;

void _main() {
    cin >> n >> m >> r; 
    int N = (n - r) / m + 1, res = 0;
    for (int d = 0; d < 30; d++) 
        res += floor_sum(N, 1 << (d + 1), m, r + (1 << d))
               - floor_sum(N, 1 << (d + 1), m, r);
    cout << res;
}

:::::