嘘~ 正在从服务器偷取页面 . . .

OI模板-多项式

总结 多项式
OI
发布日期:   2024-02-21
更新日期:   2024-07-19
文章字数:   1.9k

OI模板-多项式

快速傅里叶变换 FFT

传送门：快速傅里叶变换 FFT

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef complex<double> Complex;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e7 + 15))

const double pi = acos(-1.0);
Complex a[N], b[N];
int l, r[N], limit = 1;
void FFT(Complex *A, int type)
{
    for(int i = 0; i < limit; i++) if(i < r[i]) swap(A[i], A[r[i]]);
    for(int mid = 1; mid < limit; mid *= 2)
    {
        Complex Wn(cos(pi / mid), type * sin(pi / mid));
        for(int j = 0; j < limit; j += (mid * 2))
        {
            Complex w(1, 0);
            for(int k = 0; k < mid; k++, w = w * Wn)
            {
                Complex x = A[j + k], y = w * A[j + k + mid];
                A[j + k] = x + y; A[j + k + mid] = x - y;
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m;
    for(int i = 0, x; i <= n; i++) cin >> x, a[i] = x;
    for(int i = 0, x; i <= m; i++) cin >> x, b[i] = x;
    for(; limit <= n + m; l++, limit *= 2);
    for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    FFT(a, 1); FFT(b, 1);
    for(int i = 0; i < limit; i++) a[i] = a[i] * b[i];
    FFT(a, -1);
    for(int i = 0; i <= n + m; i++)
        cout << (int)(a[i].real() / limit + 0.5) << " \n"[i == n + m];
    return 0;
}

快速数论变换 NTT

传送门：快速数论变换 NTT

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e7 + 15))

const int P = 998244353;
const int G = 3, Gi = 332748118;
int a[N], b[N];
int l, r[N], limit = 1;
int qpow(int a, int b)
{
    int r = 1;
    while(b)
    {
        if(b & 1) r = r * a % P;
        b >>= 1; a = a * a % P;
    }
    return r;
}
void NTT(int *A, int type)
{
    for(int i = 0; i < limit; i++) if(i < r[i]) swap(A[i], A[r[i]]);
    for(int mid = 1; mid < limit; mid *= 2)
    {
        int Wn = qpow((type == 1 ? G : Gi), (P - 1) / (mid * 2));
        for(int j = 0; j < limit; j += (mid * 2))
        {
            int w = 1;
            for(int k = 0; k < mid; k++, w = (w * Wn) % P)
            {
                int x = A[j + k], y = w * A[j + k + mid] % P;
                A[j + k] = (x + y) % P; A[j + k + mid] = (x - y + P) % P;
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m;
    for(int i = 0, x; i <= n; i++) cin >> x, a[i] = (x + P) % P;
    for(int i = 0, x; i <= m; i++) cin >> x, b[i] = (x + P) % P;
    for(; limit <= n + m; l++, limit *= 2);
    for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    NTT(a, 1); NTT(b, 1);
    for(int i = 0; i < limit; i++) a[i] = a[i] * b[i] % P;
    NTT(a, -1);
    int Inv = qpow(limit, P - 2);
    for(int i = 0; i <= n + m; i++)
        cout << a[i] * Inv % P << " \n"[i == n + m];
    return 0;
}

多项式初等函数

传送门：多项式初等函数 。

因为篇幅限制，所以请查看链接内容。

目录：

  1. 多项式求逆
  2. 多项式开根
  3. 多项式除法 & 带余除法
  4. 多项式对数函数 & 指数函数
  5. 多项式三角函数
  6. 多项式反三角函数

分治 FFT / 分治 NTT

参考 洛谷P4721 【模板】分治 FFT 题解

// 2024年07月19日 23:21:54
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e5 + 15))

namespace NTT
{
    #define NTT_N ((N + N) * 2)
    const int P = 998244353;
    const int G = 3, Gi = 332748118;
    void add(int &x, int y) { (x += y) >= P ? x -= P : 0; }
    int qpow(int a, int b)
    {
        int r = 1;
        for(a %= P; b; b >>= 1, a = 1ll * a * a % P)
            if(b & 1) r = 1ll * r * a % P;
        return r;
    }
    int l, limit, r[NTT_N], a[NTT_N], b[NTT_N];
    void init(int len) // size(a) plus size(b)
    {
        for(limit = 1, l = 0; limit <= len; limit *= 2, ++l);
        for(int i = 0; i < limit; i++)
            r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    }
    void NTT(int *A, int type)
    {
        for(int i = 0; i < limit; i++) if(i < r[i]) swap(A[i], A[r[i]]);
        for(int mid = 1; mid < limit; mid *= 2)
        {
            int Wn = qpow((type == 1 ? G : Gi), (P - 1) / (mid * 2));
            for(int j = 0; j < limit; j += (mid * 2))
            {
                int w = 1;
                for(int k = 0; k < mid; k++, w = 1ll * w * Wn % P)
                {
                    int x = A[j + k], y = 1ll * w * A[j + k + mid] % P;
                    A[j + k] = (x + y) % P; A[j + k + mid] = (x - y + P) % P;
                }
            }
        }
        if(type != 1)
        {
            const int Inv = qpow(limit, P - 2);
            for(int i = 0; i < limit; i++) A[i] = 1ll * A[i] * Inv % P;
        }
    }
    int* convolution(int *A, int n, int *B, int m)
    {
        rep(i, 0, limit - 1) a[i] = b[i] = 0;
        rep(i, 0, n) a[i] = A[i]; rep(i, 0, m) b[i] = B[i];
        init(n + m + 1); NTT(a, 1); NTT(b, 1);
        for(int i = 0; i < limit; i++) a[i] = 1ll * a[i] * b[i] % P;
        NTT(a, -1); return a;
    }
}
using NTT::qpow, NTT::P, NTT::add;
#define inv(x) (qpow(x, P - 2))
int n, a[N], b[N], f[N], g[N];
void solve(int l, int r)
{
    if(r - l < 2) return;
    int mid = (l + r) >> 1; solve(l, mid);
    memset(a + (r - l) / 2, 0, (r - l) / 2 * sizeof(int));
    memcpy(a, f + l, (r - l) / 2 * sizeof(int));
    memcpy(b, g, (r - l) * sizeof(int));
    int *c = NTT::convolution(a, r - l, b, r - l);
    rep(i, mid, r - 1) add(f[i], c[i - l]);
    solve(mid, r);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; g[0] = 0; f[0] = 1;
    rep(i, 1, n - 1) cin >> g[i];
    solve(0, n);
    rep(i, 0, n - 1) cout << f[i] << " \n"[i == n - 1];
    return 0;
}

快速沃尔什变换 FWT

参考 快速沃尔什变换 FWT

// 2024年07月18日 18:21:10
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 998244353;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1 << 17) + 15)

const int inv2 = 499122177;
int n, A[N], B[N], a[N], b[N];
void OR(int *f, int x = 1)
{
    for(int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
        for(int i = 0; i < n; i += o)
            for(int j = 0; j < k; j++) add(f[i + j + k], f[i + j] * x % mod);
}
void AND(int *f, int x = 1)
{
    for(int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
        for(int i = 0; i < n; i += o)
            for(int j = 0; j < k; j++) add(f[i + j], f[i + j + k] * x % mod);
}
void XOR(int *f, int x = 1)
{
    for(int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
        for(int i = 0; i < n; i += o)
            for(int j = 0; j < k; j++)
            {
                f[i + j] = (f[i + j] + f[i + j + k]) % mod;
                f[i + j + k] = (f[i + j] + mod - 2 * f[i + j + k] % mod) % mod;
                f[i + j] = f[i + j] * x % mod; f[i + j + k] = f[i + j + k] * x % mod;
            }
}
void init() { rep(i, 0, n - 1) { a[i] = A[i]; b[i] = B[i]; } }
void print(int *f) { rep(i, 0, n - 1) cout << f[i] << " \n"[i == n - 1]; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int m; cin >> m; n = 1 << m;
    rep(i, 0, n - 1) { cin >> A[i], A[i] %= mod; }
    rep(i, 0, n - 1) { cin >> B[i], B[i] %= mod; }
    
    init(); OR(a); OR(b);
    rep(i, 0, n - 1) a[i] = a[i] * b[i] % mod;
    OR(a, mod - 1); print(a);

    
    init(); AND(a); AND(b);
    rep(i, 0, n - 1) a[i] = a[i] * b[i] % mod;
    AND(a, mod - 1); print(a);

    init(); XOR(a); XOR(b);
    rep(i, 0, n - 1) a[i] = a[i] * b[i] % mod;
    XOR(a, inv2); print(a);
    return 0;
}
文章作者: q779
文章链接: https://q779.cn/2024/02/21/oi-mo-ban-duo-xiang-shi/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 q779 !
总结 多项式
评论
  目录