多项式全家桶

博主： tony102
发布时间：2021 年 01 月 31 日
1787 次浏览
暂无评论
781字数
分类：总结

## **FFT / NTT**

**总而言之，思想是差不多的，都是分治。但是为什么FFT这么牛逼，是因为傅里叶先发明了这种变化，而NTT只是恰好原根也满足单位根类似的性质，所以只是实现上的差异。下次你搞一个性质类似的东西说不定就叫TTT**

### **FFT**

**板子还是要贴的**

```
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 4e6 + 5;
const double pi = acos(-1);

int n, m;
int b[SIZE];

struct c {
    double r, i;
    c() { r = i = 0.00; }
    c(double a, double b) { r = a, i = b; }
    c operator+ (c &a) { return c(r + a.r, i + a.i); }
    c operator- (c &a) { return c(r - a.r, i - a.i); }
    c operator* (c &a) { return c((r * a.r - i * a.i), (i * a.r + r * a.i)); }
    void operator+= (c &a) { r += a.r, i += a.i; }
    void operator*= (c &a) { double t = r; r = r * a.r - i * a.i; i = t * a.i + i * a.r; }
} f[SIZE];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

void FFT(c *a, int opt) {
    c W, w, t, *a0, *a1;
    for (int i = 0; i < n; ++ i) if (i < b[i]) t = a[i], a[i] = a[b[i]], a[b[i]] = t;
    for (int i = 1, j = 0, k = 0; i < n; i <<= 1)
        for (W = c(cos(pi / i), sin(pi / i) * opt), j = 0; j < n; j += (i << 1)) 
            for (w = c(1, 0), a1 = i + (a0 = a + j), k = 0; k < i; ++ k, ++ a0, ++ a1, w *= W) 
                t = *a1 * w, *a1 = *a0 - t, *a0 += t;
}

int main() {
    n = read(), m = read(); int len = 0;
    for (int i = 0; i <= n; ++ i) f[i].r = (double) read();
    for (int i = 0; i <= m; ++ i) f[i].i = (double) read();
    for (m += n, n = 1; n <= m; n <<= 1, ++ len);
    for (int i = 0; i < n; ++ i) b[i] = (b[i >> 1] >> 1 | ((i & 1) << (len - 1)));
    FFT(f, 1); for (int i = 0; i < n; ++ i) f[i] = f[i] * f[i]; FFT(f, -1);
    for (int i = 0; i <= m; ++ i) printf("%.0lf ", fabs(f[i].i) / (double) n / 2.000);
    return 0;
}

```

### **NTT**

**区别就是没有区别**

```
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 4e6 + 5;
const int g = 3, gi = 332748118, mod = 998244353;

int n, m;
int f[SIZE], h[SIZE], b[SIZE];

int qPow(int a, int b) {
    int ans = 1;
    for ( ; b; b >>= 1, a = a * a % mod) {
        if (b & 1) ans = ans * a % mod;
    }
    return ans;
}

void NTT(int *a, int opt) {
    int W, w, t, *a0, *a1;
    for (int i = 0; i < n; ++ i) if (i < b[i]) t = a[i], a[i] = a[b[i]], a[b[i]] = t;
    for (int i = 1, j = 0, k = 0; i < n; i <<= 1)
        for (W = qPow(opt == 1 ? g : gi, (mod - 1) / (i << 1)), j = 0; j < n; j += (i << 1))
            for (w = 1, k = 0, a1 = i + (a0 = a + j); k < i; ++ k, ++ a1, ++ a0, (w *= W) %= mod) 
                t = *a1 * w % mod, *a1 = (*a0 - t + mod) % mod, (*a0 += t) %= mod;
}

signed main() {
    // freopen("code.in", "r", stdin);
    n = read(), m = read(); int len = 0;
    for (int i = 0; i <= n; ++ i) f[i] = read();
    for (int i = 0; i <= m; ++ i) h[i] = read();
    for (m += n, n = 1; n <= m; n <<= 1, ++ len);
    for (int i = 0; i < n; ++ i) b[i] = (b[i >> 1] >> 1 | ((i & 1) << (len - 1)));
    NTT(f, 1); NTT(h, 1);
    for (int i = 0; i < n; ++ i) f[i] = f[i] * h[i] % mod;
    NTT(f, -1); int inv = qPow(n, mod - 2);
    for (int i = 0; i <= m; ++ i) printf("%lld ", f[i] * inv % mod); puts("");
    return 0;
}
```

## **FMT/FWT**

**网上的教程非常好懂，这玩意儿非常简单。取或和与的实际叫做FMT（快速莫比乌斯变换）， 只有异或的叫做FWT（快速沃尔什变换）**

```
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = (1 << 17) + 5;
const int mod = 998244353;

int n, m;
int f[SIZE], g[SIZE], a[SIZE], b[SIZE];

namespace GTR {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf)  + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (c < 48 || c > 57) b ^= c == '-', c = fetch();
        while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
        return b ? a : -a;
    }
} using namespace GTR;

void OR(int *a, int x) {
    for (int a0 = 2, a1 = 1; a0 <= m; a0 <<= 1, a1 <<= 1) 
        for (int i = 0; i < m; i += a0) 
            for (int j = 0; j < a1; ++ j) (a[i + j + a1] += (a[i + j] * x % mod) % mod) %= mod;
}

void AND(int *a, int x) {
    for (int a0 = 2, a1 = 1; a0 <= m; a0 <<= 1, a1 <<= 1) 
        for (int i = 0; i < m; i += a0) 
            for (int j = 0; j < a1; ++ j) (a[i + j] += (a[i + j + a1] * x % mod) % mod) %= mod;
}

void XOR(int *a, int x) {
    for (int a0 = 2, a1 = 1; a0 <= m; a0 <<= 1, a1 <<= 1)
        for (int i = 0; i < m; i += a0)
            for (int j = 0; j < a1; ++ j) {
                a[i + j] = (a[i + j] + a[i + j + a1]) % mod;
                (a[i + j + a1] = (((a[i + j] - a[i + j + a1] + mod) % mod - a[i + j + a1]) + mod) % mod) %= mod;
                a[i + j] = (a[i + j] * x) % mod, a[i + j + a1] = (a[i + j + a1] * x) % mod;
            }
}

int qPow(int a, int b) {
    int ans = 1;
    for ( ; b; b >>= 1, a = a * a % mod) {
        if (b & 1) ans = ans * a % mod;
    }
    return ans % mod;
}

signed main() {
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    n = read(), m = (1 << n);
    for (int i = 0; i < m; ++ i) f[i] = a[i] = read() % mod;
    for (int i = 0; i < m; ++ i) g[i] = b[i] = read() % mod;
    OR(f, 1), OR(g, 1);
    for (int i = 0; i < m; ++ i) (f[i] *= g[i]) %= mod;
    OR(f, -1);
    for (int i = 0; i < m; ++ i) printf("%lld ", (f[i] + mod) % mod);
    puts("");

for (int i = 0; i < m; ++ i) f[i] = a[i];
    for (int i = 0; i < m; ++ i) g[i] = b[i];

AND(f, 1), AND(g, 1);
    for (int i = 0; i < m; ++ i) (f[i] *= g[i]) %= mod;
    AND(f, -1);
    for (int i = 0; i < m; ++ i) printf("%lld ", (f[i] + mod) % mod);
    puts("");
    for (int i = 0; i < m; ++ i) f[i] = a[i];
    for (int i = 0; i < m; ++ i) g[i] = b[i];

XOR(f, 1), XOR(g, 1);
    for (int i = 0; i < m; ++ i) (f[i] *= g[i]) %= mod;
    int inv = qPow(2, mod - 2);
    XOR(f, inv);
    for (int i = 0; i < m; ++ i) printf("%lld ", (f[i] + mod) % mod);
    puts("");
    return 0;
}
```

## **inv**

**非常简单，跟普通的数求逆元用快速幂一样，分治推式子。**

```
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 1e6 + 5;
const int g = 3, gi = 332748118, mod = 998244353;

int n;
int a[SIZE], b[SIZE], c[SIZE], pos[SIZE];

int qPow(int a, int b) {
    int ans = 1;
    for ( ; b; b >>= 1, a = a * a % mod) {
        if (b & 1) ans = ans * a % mod;
    } 
    return ans % mod;
}

void NTT(int *a, int n, int opt) {
    int wn, w, t, *a0, *a1;
    for (int i = 0; i < n; ++ i) if (i < pos[i]) std::swap(a[i], a[pos[i]]);
    for (int i = 1, j, k; i < n; i <<= 1) 
        for (wn = qPow(opt == 1 ? g : gi, (mod - 1) / (i << 1)), j = 0; j < n; j += (i << 1))
            for (w = 1, k = 0, a1 = i + (a0 = a + j); k < i; ++ k, ++ a0, ++ a1, (w *= wn) %= mod)
                t = *a1 * w % mod, *a1 = (*a0 - t + mod) % mod, (*a0 += t) %= mod;
    if (opt == 1) return;
    int inv = qPow(n, mod - 2) % mod;
    for (int i = 0; i < n; ++ i) (a[i] *= inv) %= mod;
}

void inverse(int ind, int *a, int *b) {
    if (ind == 1) { b[0] = qPow(a[0], mod - 2) % mod; return; }
    inverse((ind + 1) >> 1, a, b);  
    int N = 1, len = 0, m = ind << 1;
    for ( ; N <= m; N <<= 1, ++ len);
    for (int i = 0; i < N; ++ i) pos[i] = (pos[i >> 1] >> 1 | ((i & 1) << (len - 1)));
    for (int i = 0; i < N; ++ i) c[i] = (i >= ind ? 0 : a[i]);
    NTT(c, N, 1); NTT(b, N, 1);
    for (int i = 0; i < N; ++ i) b[i] = (2ll - (b[i] * c[i] % mod) + mod) % mod * b[i] % mod;
    NTT(b, N, -1);
    for (int i = ind; i < N; ++ i) b[i] = 0;
}

signed main() {
    // freopen("code.in", "r", stdin);
    n = read();
    for (int i = 0; i < n; ++ i) a[i] = read();
    inverse(n, a, b);
    for (int i = 0; i < n; ++ i) printf("%lld ", b[i] % mod); puts("");
    return 0;
}
```

## **sqrt**

**非常简单，列个式子运用分治的思想从底向上更新答案即可。**

```
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 2e6 + 5;
const int G = 3, Gi = 332748118, mod = 998244353, inv2 = (mod + 1) >> 1;

int n;
int f[SIZE], g[SIZE], c[SIZE], iv[SIZE], pos[SIZE];

namespace GTR {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (c < 48 || c > 57) b ^= c == '-', c = fetch();
        while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using GTR::read;

int qPow(int a, int b) {
    int ans = 1;
    for ( ; b; b >>= 1, a = a * a % mod) {
        if (b & 1) ans = ans * a % mod;
    }
    return ans % mod;
}

namespace poly {
    void NTT(int *a, int n, int opt) {
        int g, gn, t, *a0, *a1;
        for (int i = 0; i < n; ++ i) if (i < pos[i]) std::swap(a[i], a[pos[i]]);
        for (int i = 1, j, k; i < n; i <<= 1) 
            for (gn = qPow(opt == 1 ? G : Gi, (mod - 1) / (i << 1)), j = 0; j < n; j += (i << 1))
                for (g = 1, k = 0, a1 = i + (a0 = a + j); k < i; ++ k, ++ a0, ++ a1, (g *= gn) %= mod)  
                    t = *a1 * g % mod, *a1 = (*a0 - t + mod) % mod, (*a0 += t) %= mod;
        if (opt == 1) return;
        int inv = qPow(n, mod - 2);
        for (int i = 0; i < n; ++ i) (a[i] *= inv) %= mod;
    }

void inv(int ind, int *a, int *b) {
        if (ind == 1) { return b[0] = qPow(a[0], mod - 2), void(); }
        inv((ind + 1) >> 1, a, b);
        int N = 1, M = ind << 1, len = 0;
        for ( ; N <= M; N <<= 1, ++ len);
        for (int i = 0; i < N; ++ i)
            pos[i] = (pos[i >> 1] >> 1 | ((i & 1) << (len - 1))), c[i] = (i >= ind ? 0 : a[i]);
        NTT(c, N, 1); NTT(b, N, 1);
        for (int i = 0; i < N; ++ i) b[i] = (2ll - (b[i] * c[i] % mod) + mod) % mod * b[i] % mod;
        NTT(b, N, -1);
        for (int i = ind; i < N; ++ i) b[i] = 0;
    }

void sqrt(int ind, int *a, int *b) {
        if (ind == 1) { return b[0] = 1, void(); }
        sqrt((ind + 1) >> 1, a, b);
        for (int i = 0; i <= (ind << 2); ++ i) iv[i] = 0;
        inv(ind, b, iv);
        int N = 1, M = ind << 1, len = 0;
        for ( ; N <= M; N <<= 1, ++ len);
        for (int i = 0; i < N; ++ i)
            pos[i] = (pos[i >> 1] >> 1 | ((i & 1) << (len - 1))), c[i] = (i >= ind ? 0 : a[i]);
        NTT(c, N, 1); NTT(iv, N, 1);
        for (int i = 0; i < N; ++ i) c[i] = c[i] * iv[i] % mod;
        NTT(c, N, -1);
        for (int i = 0; i < N; ++ i) b[i] = (b[i] + c[i]) % mod * inv2 % mod;
        for (int i = ind; i < N; ++ i) b[i] = 0;
    }
} using namespace poly;

signed main() {
    // freopen("code.in", "r", stdin);
    n = read();
    for (int i = 0; i < n; ++ i) f[i] = read() % mod;
    poly::sqrt(n, f, g);
    for (int i = 0; i < n; ++ i) printf("%lld ", g[i] % mod);
    puts("");
    return 0;
}
```

## **ln**

**非常简单，可以用牛顿迭代，也可以直接暴力过**

```
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 2e6 + 5;
const int G = 3, Gi = 332748118, mod = 998244353;

int n;
int f[SIZE], g[SIZE], pos[SIZE], c[SIZE], ca[SIZE], iv[SIZE];

namespace GTR {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (c < 48 || c > 57) b ^= c == '-', c = fetch();
        while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using GTR::read;

int qPow(int a, int b) {
    int ans = 1;
    for ( ; b; b >>= 1, a = a * a % mod) {
        if (b & 1) ans = ans * a % mod;
    }
    return ans % mod;
}

void derive(int n, int *a, int *b) {
        for (int i = 1; i < n; ++ i) b[i - 1] = a[i] * i % mod; b[n - 1] = 0;
    }

void calculus(int n, int *a, int *b) {
        for (int i = 1; i < n; ++ i) b[i] = a[i - 1] * qPow(i, mod - 2) % mod; b[0] = 0;
    }

void inv(int ind, int *a, int *b) {
        if (ind == 1) { b[0] = qPow(a[0], mod - 2); return; }
        inv((ind + 1) >> 1, a, b);
        int N = 1, M = ind << 1, len = 0;
        for ( ; N <= M; N <<= 1, ++ len);
        for (int i = 0; i < N; ++ i)
            pos[i] = (pos[i >> 1] >> 1 | ((i & 1) << (len - 1))), c[i] = (i >= ind ? 0 : a[i]);
        NTT(c, N, 1); NTT(b, N, 1);
        for (int i = 0; i < N; ++ i) b[i] = (2ll - (b[i] * c[i] % mod) + mod) % mod * b[i] % mod;
        NTT(b, N, -1);
        for (int i = ind; i < N; ++ i) b[i] = 0;
    }

void ln(int bas, int *a, int *b) {
        derive(bas, a, ca); inv(bas, a, iv);
        int N = 1, M = bas << 1, len = 0;
        for ( ; N <= M; N <<= 1, ++ len);
        for (int i = 0; i < N; ++ i) pos[i] = (pos[i >> 1] >> 1 | ((i & 1) << (len - 1)));
        NTT(ca, N, 1); NTT(iv, N, 1);
        for (int i = 0; i < N; ++ i) ca[i] = ca[i] * iv[i] % mod;
        NTT(ca, N, -1);
        calculus(N, ca, b);
    }
} using namespace poly;

signed main() {
    // freopen("code.in", "r", stdin);
    n = read();
    for (int i = 0; i < n; ++ i) f[i] = read() % mod;
    ln(n, f, g);
    for (int i = 0; i < n; ++ i) printf("%lld ", g[i] % mod);
    puts("");
    return 0;
}
```

## **exp**

**牛顿迭代根本就不叫牛顿迭代，这个东西本来就叫做牛顿法。具体的，你可以看做泰勒展开只做一阶导的近似。具体地，你可以看下麦克劳林级数，这家伙就是牛顿的学生。在用泰勒展开推式子的时候，忽略那一些补的项。因为现在是无界地，所以根本不存在余**

```
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 2e6 + 5;
const int G = 3, Gi = 332748118, mod = 998244353;

int n;
int f[SIZE], g[SIZE], c[SIZE], lne[SIZE], iv[SIZE], cal[SIZE], pos[SIZE], W[SIZE], WN[SIZE];

namespace GTR {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (c < 48 || c > 57) b ^= c == '-', c = fetch();
        while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using GTR::read;

int qPow(int a, int b) {
    int ans = 1;
    for ( ; b; b >>= 1, a = a * a % mod) {
        if (b & 1) ans = ans * a % mod;
    }
    return ans % mod;
}

namespace poly {
    void NTT(int *a, int n, int opt) {
        int w, wn, t, *a0, *a1;
        for (int i = 0; i < n; ++ i) if (i < pos[i]) std::swap(a[i], a[pos[i]]);
        for (int i = 1, j, k; i < n; i <<= 1) {
            if (opt == 1) W[i << 1] ? wn = W[i << 1] : W[i << 1] = wn = qPow(G, (mod - 1) / (i << 1));
            else if (opt == -1) WN[i << 1] ? wn = WN[i << 1] : WN[i << 1] = wn = qPow(Gi, (mod - 1) / (i << 1));
            for (j = 0; j < n; j += (i << 1))
                for (w = 1, k = 0, a1 = i + (a0 = a + j); k < i; ++ k, ++ a0, ++ a1, (w *= wn) %= mod)
                    t = *a1 * w % mod, *a1 = (*a0 - t + mod) % mod, (*a0 += t) %= mod;
        }
        if (opt == 1) return;
        int inv = qPow(n, mod - 2);
        for (int i = 0; i < n; ++ i) (a[i] *= inv) %= mod;
    }

void derive(int n, int *a, int *b) {
        for (int i = 1; i < n; ++ i) b[i - 1] = i * a[i] % mod; b[n - 1] = 0;
    }

void calculus(int n, int *a, int *b) {
        for (int i = 1; i < n; ++ i) b[i] = a[i - 1] * qPow(i, mod - 2) % mod; b[0] = 0;
    }

void ln(int bas, int *a, int *b) {
        derive(bas, a, cal); inv(bas, a, iv);
        int N = 1, M = bas << 1, len = 0;
        for ( ; N <= M; N <<= 1, ++ len);
        for (int i = 0; i < N; ++ i) pos[i] = (pos[i >> 1] >> 1 | ((i & 1) << (len - 1)));
        NTT(cal, N, 1); NTT(iv, N, 1);
        for (int i = 0; i < N; ++ i) cal[i] = cal[i] * iv[i] % mod;
        NTT(cal, N, -1);
        calculus(N, cal, b);
    }

void exp(int ind, int *a, int *b) {
        if (ind == 1) { return b[0] = 1, void(); }
        exp((ind + 1) >> 1, a, b);
        int N = 1, M = ind << 1, len = 0;
        for ( ; N <= M; N <<= 1, ++ len);
        for (int i = 0; i < (M << 1); ++ i) iv[i] = lne[i] = 0;
        ln(ind, b, lne);
        for (int i = 0; i < N; ++ i) pos[i] = (pos[i >> 1] >> 1 | ((i & 1) << (len - 1)));
        for (int i = 0; i < N; ++ i) c[i] = (i >= ind ? 0 : a[i]);
        NTT(b, N, 1); NTT(lne, N, 1); NTT(c, N, 1);
        for (int i = 0; i < N; ++ i) b[i] = (1ll - (lne[i] - c[i] + mod) % mod + mod) % mod * b[i] % mod;
        NTT(b, N, -1);
        for (int i = ind; i < N; ++ i) b[i] = 0;
    }
} using namespace poly;

signed main() {
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    n = read();
    for (int i = 0; i < n; ++ i) f[i] = read();
    poly::exp(n, f, g);
    for (int i = 0; i < n; ++ i) printf("%lld ", g[i] % mod);
    puts("");
    return 0;
}
```

## **总结**

**为什么这玩意儿写的这么短，第一是因为他们催我更博，为了不鸽。第二是因为已经22:28了，只有两分钟就要下班了。这些东西都非常简单，初学可能需要一些微积分导数作为基础会更加容易理解。**

**总而言之，我很不喜欢一些人的板子，reverse来reverse去的，非常麻烦。愣头小青年，我非常不满意！！！我的板子非常地快，用上寻址优化就可以了**

**现在已经下班10分钟了，我要加班费了**

最后修改：2021 年 09 月 07 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

xbieygztgu
不错不错，我喜欢看 https://www.ea55.com/
ojvrnvtsvs
看的我热血沸腾啊https://www.ea55.com/
orzaztmfuh
不错不错，我喜欢看 https://www.ea55.com/
mzcwdjqqxe
不错不错，我喜欢看 https://www.ea55.com/
Yanws
牢师求更新

多项式全家桶

tony102 • 2021 年 01 月 31 日

## **FFT / NTT**

### **FFT**

**板子还是要贴的**

```
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 4e6 + 5;
const double pi = acos(-1);

int n, m;
int b[SIZE];

```

### **NTT**

**区别就是没有区别**

```
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 4e6 + 5;
const int g = 3, gi = 332748118, mod = 998244353;

int n, m;
int f[SIZE], h[SIZE], b[SIZE];

int qPow(int a, int b) {
    int ans = 1;
    for ( ; b; b >>= 1, a = a * a % mod) {
        if (b & 1) ans = ans * a % mod;
    }
    return ans;
}

## **FMT/FWT**

**网上的教程非常好懂，这玩意儿非常简单。取或和与的实际叫做FMT（快速莫比乌斯变换）， 只有异或的叫做FWT（快速沃尔什变换）**

```
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = (1 << 17) + 5;
const int mod = 998244353;

int n, m;
int f[SIZE], g[SIZE], a[SIZE], b[SIZE];

int qPow(int a, int b) {
    int ans = 1;
    for ( ; b; b >>= 1, a = a * a % mod) {
        if (b & 1) ans = ans * a % mod;
    }
    return ans % mod;
}

for (int i = 0; i < m; ++ i) f[i] = a[i];
    for (int i = 0; i < m; ++ i) g[i] = b[i];

## **inv**

**非常简单，跟普通的数求逆元用快速幂一样，分治推式子。**

```
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 1e6 + 5;
const int g = 3, gi = 332748118, mod = 998244353;

int n;
int a[SIZE], b[SIZE], c[SIZE], pos[SIZE];

int qPow(int a, int b) {
    int ans = 1;
    for ( ; b; b >>= 1, a = a * a % mod) {
        if (b & 1) ans = ans * a % mod;
    } 
    return ans % mod;
}

## **sqrt**

**非常简单，列个式子运用分治的思想从底向上更新答案即可。**

```
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 2e6 + 5;
const int G = 3, Gi = 332748118, mod = 998244353, inv2 = (mod + 1) >> 1;

int n;
int f[SIZE], g[SIZE], c[SIZE], iv[SIZE], pos[SIZE];

namespace GTR {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (c < 48 || c > 57) b ^= c == '-', c = fetch();
        while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using GTR::read;

int qPow(int a, int b) {
    int ans = 1;
    for ( ; b; b >>= 1, a = a * a % mod) {
        if (b & 1) ans = ans * a % mod;
    }
    return ans % mod;
}

## **ln**

**非常简单，可以用牛顿迭代，也可以直接暴力过**

```
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 2e6 + 5;
const int G = 3, Gi = 332748118, mod = 998244353;

int n;
int f[SIZE], g[SIZE], pos[SIZE], c[SIZE], ca[SIZE], iv[SIZE];

namespace GTR {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (c < 48 || c > 57) b ^= c == '-', c = fetch();
        while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using GTR::read;

int qPow(int a, int b) {
    int ans = 1;
    for ( ; b; b >>= 1, a = a * a % mod) {
        if (b & 1) ans = ans * a % mod;
    }
    return ans % mod;
}

void derive(int n, int *a, int *b) {
        for (int i = 1; i < n; ++ i) b[i - 1] = a[i] * i % mod; b[n - 1] = 0;
    }

void calculus(int n, int *a, int *b) {
        for (int i = 1; i < n; ++ i) b[i] = a[i - 1] * qPow(i, mod - 2) % mod; b[0] = 0;
    }

## **exp**

```
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 2e6 + 5;
const int G = 3, Gi = 332748118, mod = 998244353;

int n;
int f[SIZE], g[SIZE], c[SIZE], lne[SIZE], iv[SIZE], cal[SIZE], pos[SIZE], W[SIZE], WN[SIZE];

namespace GTR {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (c < 48 || c > 57) b ^= c == '-', c = fetch();
        while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using GTR::read;

int qPow(int a, int b) {
    int ans = 1;
    for ( ; b; b >>= 1, a = a * a % mod) {
        if (b & 1) ans = ans * a % mod;
    }
    return ans % mod;
}

void derive(int n, int *a, int *b) {
        for (int i = 1; i < n; ++ i) b[i - 1] = i * a[i] % mod; b[n - 1] = 0;
    }

void calculus(int n, int *a, int *b) {
        for (int i = 1; i < n; ++ i) b[i] = a[i - 1] * qPow(i, mod - 2) % mod; b[0] = 0;
    }

## **总结**

**总而言之，我很不喜欢一些人的板子，reverse来reverse去的，非常麻烦。愣头小青年，我非常不满意！！！我的板子非常地快，用上寻址优化就可以了**

**现在已经下班10分钟了，我要加班费了**

多项式全家桶

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

扫描线初探

写在 CSP-S2021 前

20211016 收集 (collection)

Luogu3426 [POI2005]SZA-Template

跟不同的人聊天的收获

多项式全家桶

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

多项式全家桶

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款