题解 P5170 【【模板】类欧几里得算法】
Cyhlnj
2019-01-06 14:47:27
提供一个推导第二个式子的比较 $naive$ 的暴力思路
## 定义
~~定义几个东西,方便表示~~
设
$$f(a,b,c,n)=\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor$$
$$g(a,b,c,n)=\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor^2$$
$$h(a,b,c,n)=\sum_{i=0}^{n}i\lfloor\frac{ai+b}{c}\rfloor$$
$t_1=\lfloor\frac{a}{c}\rfloor,t_2=\lfloor\frac{b}{c}\rfloor$
$S_1(n)=\sum_{i=1}^{n}i,S_2(n)=\sum_{i=1}^{n}i^2$
$m=\lfloor\frac{an+b}{c}\rfloor-1$
$[i=0]$ 表示条件,即 $i=0$ 就是 $1$,否则为 $0$
## 式子1
首先 $a\ge c~~or~~b\ge c$ 的时候
$\lfloor\frac{ai+b}{c}\rfloor=t_1i+t_2+\lfloor\frac{(a~mod~c)i+(b~mod~c)}{c}\rfloor$
那么
$f(a,b,c,n)=t_1S_1(n)+(n+1)t_2+f(a~mod~c,b~mod~c,c,n)$
然后当 $a < c~and~b < c$ 的时候
$$f(a,b,c,n)=\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor=\sum_{i=0}^{n}\sum_{j=1}^{m+1}[j\le \lfloor\frac{ai+b}{c}\rfloor]=\sum_{j=0}^{m}\sum_{i=0}^{n}[j+1\le\lfloor\frac{ai+b}{c}\rfloor]$$
$$=\sum_{j=0}^{m}\sum_{i=0}^{n}[cj+c\le ai+b]=\sum_{j=0}^{m}\sum_{i=0}^{n}[ai> cj+c-b-1]$$
$$=\sum_{j=0}^{m}\sum_{i=0}^{n}[i> \lfloor\frac{cj+c-b-1}{a}\rfloor]=\sum_{j=0}^{m}(n-\lfloor\frac{cj+c-b-1}{a}\rfloor)$$
$$=n(m+1)-\sum_{j=0}^{m}\lfloor\frac{cj+c-b-1}{a}\rfloor=n(m+1)-f(c,c-b-1,a,m)$$
## 式子2
同样的考虑 $a\ge c~~or~~b\ge c$ 的时候
$\lfloor\frac{ai+b}{c}\rfloor^2=(t_1i+t_2+\lfloor\frac{(a~mod~c)i+(b~mod~c)}{c}\rfloor)^2$
暴力拆开得到
$$g(a,b,c,n)=t_1^2S_2(n)+(n+1)t_2^2+2t_1t_2S_1(n)+2t_1h(a~mod~c,b~mod~c,c)$$
$$+2t_2f(a~mod~c,b~mod~c,c)+g(a~mod~c,b~mod~c,c)$$
然后当 $a < c~and~b < c$ 的时候,仍然可以像式子1那样
$$g(a,b,c,n)=\sum_{i=0}^{n}(\sum_{j=1}^{m+1}[j\le \lfloor\frac{ai+b}{c}\rfloor])^2=\sum_{i=0}^{n}\sum_{j=1}^{m+1}[j\le \lfloor\frac{ai+b}{c}\rfloor])\sum_{k=1}^{m+1}[k\le \lfloor\frac{ai+b}{c}\rfloor])$$
运用式子1一样的技巧,把 $k,j$ 移到前面
$$g(a,b,c,n)=\sum_{j=0}^{m}\sum_{k=0}^{m}\sum_{i=0}^{n}[i> \lfloor\frac{cj+c-b-1}{a}\rfloor~and~i> \lfloor\frac{ck+c-b-1}{a}\rfloor]$$
$$=\sum_{j=0}^{m}\sum_{k=0}^{m}\sum_{i=0}^{n}[i> max(\lfloor\frac{cj+c-b-1}{a}\rfloor,\lfloor\frac{ck+c-b-1}{a})]$$
$$=\sum_{j=0}^{m}\sum_{k=0}^{m}(n-max(\lfloor\frac{cj+c-b-1}{a}\rfloor,\lfloor\frac{ck+c-b-1}{a}))$$
$$=n(m+1)^2-\sum_{j=0}^{m}\sum_{k=0}^{m}max(\lfloor\frac{cj+c-b-1}{a}\rfloor,\lfloor\frac{ck+c-b-1}{a})$$
$max$ 不好弄,枚举大的那一个
先算强制 $k$ 的小于等于 $j$ 的,加上 $k$ 的大于等于 $j$ 的,减去相同 $j,k$ 的
前面两个情况显然一样,那么就是
$$n(m+1)^2-2\sum_{j=0}^{m}(j+1)\lfloor\frac{cj+c-b-1}{a}\rfloor+\sum_{j=0}^{m}\lfloor\frac{cj+c-b-1}{a}\rfloor$$
把 $j+1$ 拆开就变成了
$$g(a,b,c,n)=n(m+1)^2-2h(c,c-b-1,a,m)-f(c,c-b-1,a,m)$$
而仔细想一下这个东西和其它的题解实际上是一样的
~~一开始我还以为推错了~~
## 式子3
还是考虑 $a\ge c~~or~~b\ge c$ 的时候
$i\lfloor\frac{ai+b}{c}\rfloor=t_1i^2+t_2i+i\lfloor\frac{(a~mod~c)i+(b~mod~c)}{c}\rfloor$
那么
$h(a,b,c,n)=t_1S_2(n)+t_2S_1(n)+h(a~mod~c,b~mod~c,c,n)$
然后当 $a < c~and~b < c$ 的时候,还是可以像式子1那样
$$h(a,b,c,n)=\sum_{j=0}^{m}\sum_{i=0}^{n}i[i> \lfloor\frac{cj+c-b-1}{a}\rfloor]=\sum_{j=0}^{m}\sum_{i=\lfloor\frac{cj+c-b-1}{a}\rfloor+1}^{n}i$$
等差数列求个和,即
$$h(a,b,c,n)=\frac{1}{2}((m+1)n(n+1)-f(c,c-b-1,a,m)-g(c,c-b-1,a,m))$$
$f,h,g$ 显然一起处理就行了
```cpp
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod(998244353);
const int inv2((mod + 1) >> 1);
const int inv6(166374059);
inline void Inc(int &x, int y) {
x = x + y >= mod ? x + y - mod : x + y;
}
inline void Dec(int &x, int y) {
x = x - y < 0 ? x - y + mod : x - y;
}
inline int Add(int x, int y) {
return x + y >= mod ? x + y - mod : x + y;
}
inline int Sub(int x, int y) {
return x - y < 0 ? x - y + mod : x - y;
}
inline int Pow(ll x, int y) {
ll ret = 1;
for (; y; y >>= 1, x = x * x % mod)
if (y & 1) ret = ret * x % mod;
return ret;
}
inline int Gcd(int x, int y) {
return !y ? x : Gcd(y, x % y);
}
struct Info {
int f, g, h;
} ans;
int test;
inline int S1(ll x) {
return x * (x + 1) / 2 % mod;
}
inline int S2(ll x) {
return x * (x + 1) % mod * (x + x + 1) % mod * inv6 % mod;
}
Info Solve(int a, int b, int c, int n) {
Info ret, frm;
int m, t1, t2, s1, s2;
ret.f = ret.g = ret.h = 0;
if (!n) {
ret.f = b / c, ret.g = (ll)(b / c) * (b / c) % mod;
return ret;
}
if (!a) {
t1 = b / c;
ret.f = (ll)(n + 1) * t1 % mod;
ret.g = (ll)(n + 1) * t1 % mod * t1 % mod;
ret.h = (ll)S1(n) * t1 % mod;
return ret;
}
if (a >= c || b >= c) {
t1 = a / c, t2 = b / c;
frm = Solve(a % c, b % c, c, n);
s1 = S1(n), s2 = S2(n);
ret.f = Add(Add((ll)s1 * t1 % mod, (ll)(n + 1) * t2 % mod), frm.f);
ret.g = Add((ll)t1 * t1 % mod * s2 % mod, (ll)(n + 1) * t2 % mod * t2 % mod);
Inc(ret.g, Add((ll)t1 * t2 % mod * 2 * s1 % mod, (ll)t1 * 2 * frm.h % mod));
Inc(ret.g, Add(frm.g, (ll)t2 * 2 * frm.f % mod));
ret.h = Add(Add((ll)s2 * t1 % mod, (ll)s1 * t2 % mod), frm.h);
return ret;
}
m = ((ll)n * a + b) / c - 1;
frm = Solve(c, c - b - 1, a, m);
ret.f = Sub((ll)n * (m + 1) % mod, frm.f);
ret.g = Sub((ll)n * (m + 1) % mod * (m + 1) % mod, Add(frm.h * 2 % mod, frm.f));
ret.h = Sub((ll)n * (n + 1) % mod * (m + 1) % mod, Add(frm.f, frm.g));
ret.h = (ll)ret.h * inv2 % mod;
return ret;
}
int main() {
int a, b, c, n;
scanf("%d", &test);
while (test) {
scanf("%d%d%d%d", &n, &a, &b, &c);
ans = Solve(a, b, c, n), --test;
printf("%d %d %d\n", ans.f, ans.g, ans.h);
}
return 0;
}
```