题解 P5170 【【模板】类欧几里得算法】

Cyhlnj

2019-01-06 14:47:27

Solution

提供一个推导第二个式子的比较 $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; } ```