类欧几里得算法
stripe_python · · 算法·理论
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[题解]
以
- 当
a=0 时
-
当
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} -
当
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=0 时g(a,b,c,n)=(n+1) \left\lfloor \dfrac{b}{c} \right\rfloor^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} -
当
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}
我们发现
-
当
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} -
当
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} -
当
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}
注意到
:::::
:::::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[题解]
考察操作序列的形态。不难发现
先对
顺序扫描
其中
上面那个求和式是类欧几里得的形式,可以做到
:::::
:::::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[题解]
不难发现,题目所求的是一个等差数列的
如果只有
在位运算的意义下考虑,我们要求的是 x >> d & 1,将其等价为 x >> d - (x >> (d + 1)) << 1 即可。原因是,我们只要保留 x >> d 的末位,将低
代入得
两部分都可以类欧。复杂度
:::::
:::::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;
}
:::::