类欧几里得

数据结构与算法
字数统计: 697字   |   阅读时长≈ 4分钟

类欧几里得的总结

类欧几里得的作用

类欧几里得主要用于加速下列三种函数（log）:

f(a,b,c,n)=∑ni=0⌊ai+bc⌋f(a,b,c,n)=∑i=0n⌊ai+bc⌋

g(a,b,c,n)=∑ni=0⌊ai+bc⌋2g(a,b,c,n)=∑i=0n⌊ai+bc⌋2

h(a,b,c,n)=∑ni=0i⌊ai+bc⌋h(a,b,c,n)=∑i=0ni⌊ai+bc⌋

模板

1
复制#pragma GCC optimize(3)
2
#include <bits/stdc++.h>
3
typedef long long ll;
4
5
constexpr int mod = 998244353;
6
7
constexpr ll inv2 = 499122177;
8
constexpr ll inv6 = 166374059;
9
10
ll f(ll a, ll b, ll c, ll n);
11
ll g(ll a, ll b, ll c, ll n);
12
ll h(ll a, ll b, ll c, ll n);
13
14
struct Query {
15
    ll f, g, h;
16
};
17
18
Query solve(ll a, ll b, ll c, ll n) {
19
    Query ans, tmp;
20
    if (a == 0) {
21
        ans.f = (n + 1) * (b / c) % mod;
22
        ans.g = (b / c) * n % mod * (n + 1) % mod * inv2 % mod;
23
        ans.h = (n + 1) * (b / c) % mod * (b / c) % mod;
24
        return ans;
25
    }
26
    if (a >= c || b >= c) {
27
        tmp = solve(a % c, b % c, c, n);
28
        ans.f = (tmp.f + (a / c) * n % mod * (n + 1) % mod * inv2 % mod + (b / c) * (n + 1) % mod) % mod;
29
        ans.g = (tmp.g + (a / c) * n % mod * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod + (b / c) * n % mod * (n + 1) % mod * inv2 % mod) % mod;
30
        ans.h = ((a / c) * (a / c) % mod * n % mod * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod +
31
                (b / c) * (b / c) % mod * (n + 1) % mod + (a / c) * (b / c) % mod * n % mod * (n + 1) % mod +
32
                tmp.h + 2 * (a / c) % mod * tmp.g % mod + 2 * (b / c) % mod * tmp.f % mod) % mod;
33
        return ans;
34
    }
35
    ll m = (a * n + b) / c;
36
    tmp = solve(c, c - b - 1, a, m - 1);
37
    ans.f = (n * (m % mod) % mod - tmp.f) % mod;
38
    ans.g = (n * (n + 1) % mod * (m % mod) % mod - tmp.f - tmp.h) % mod * inv2 % mod;
39
    ans.h = (n * (m % mod) % mod * ((m + 1) % mod) % mod - 2 * tmp.g - 2 * tmp.f - ans.f) % mod;
40
    return ans;
41
}
42
43
inline char nc() {
44
    static char buf[1000000], *p1 = buf, *p2 = buf;
45
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
46
}
47
48
inline ll read() {
49
    ll res = 0;
50
    char ch;
51
    do ch = nc(); while (ch < 48 || ch > 57);
52
    do res = res * 10 + ch - 48, ch = nc(); while (ch >= 48 && ch <= 57);
53
    return res;
54
}
55
56
char pbuf[1 << 20], *pp = pbuf;
57
inline void push(const char &c) {
58
    if (pp - pbuf == 1 << 20) fwrite(pbuf, 1, 1 << 20, stdout), pp = pbuf;
59
    *pp++ = c;
60
}
61
inline void write(int x) {
62
    static ll sta[35];
63
    ll top = 0;
64
    do {
65
        sta[top++] = x % 10, x /= 10;
66
    } while (x);
67
    while (top) push(sta[--top] + '0');
68
}
69
70
int main() {
71
    ll t = read();
72
    ll n, a, b, c;
73
    while (t--) {
74
        n = read(), a = read(), b = read(), c = read();
75
        Query ans = solve(a, b, c, n);
76
        printf("%lld %lld %lld\n", (ans.f + mod) % mod, (ans.h + mod) % mod, (ans.g + mod) % mod);
77
    }
78
    return 0;
79
}
  • © 2020 QSH
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信