ZJOI 2019 了,机房同学也差不多都会基本多项式了,就写篇有关简单的多项式操作复习笔记吧 QAQ

约定:以下操作默认 n = \deg(F(x)) + 1 ,等号一般表示在 \bmod\ {x^n} 的意义下同余。

多项式乘法

可以先把多项式的系数转为点值,各位分别乘起来以后再插值出原多项式。考虑到单位根 / 原根的性质,我们有 FFT / NTT 。

分治 + NTT

分治维护,用 F(l, r) 表示从 A_{l..r}(x) 的连乘积,mid = \frac {l + r} 2 ,则 F(l, r) = F(l, mid) \times F(mid + 1, r)

分治 NTT

考虑 CDQ 分治,每次考虑左边区间对右边的贡献。

多项式牛顿迭代

已知 G(F(x)) = 0, F(x) \bmod x^{\frac n2} ,求 F(x) \bmod x^n ,则 F'(x) = F(x) - \dfrac {G(F(x))} {G'(F(x))}

多项式求逆

已知 A(x) ,求 F(x) 使得 A(x) \times F(x) \equiv 0 \pmod {x^n}

F(x)A(x) = 1 \Rightarrow F(x) A(x) - 1 = 0

G(F(x)) = F(x) A(x) - 1 ,则:

F'(x) = F(x) - \dfrac {F(x) A(x) - 1} {A(x)} = F(x) - F(x) (F(x) A(x) - 1) = 2F(x) - F^2(x) A(x)

多项式对数函数

已知 A(x) ,求 F(x) 使得 F(x) \equiv \ln A(x) \pmod {x^n}

F(x) = \ln A(x) \Rightarrow F'(x) = \dfrac {A(x)} {A'(x)} \Rightarrow F(x) = \int \dfrac {A(x)} {A'(x)}

多项式指数函数

已知 A(x) ,求 F(x) 使得 F(x) \equiv e^ {A(x)} \pmod {x^n} .

F(x) = e^{A(x)} \Rightarrow \ln F(x) = A(x) \Rightarrow \ln F(x) - A(x) = 0

G(F(x)) = \ln F(x) - A(x) ,则:

F'(x) = F(x) - \dfrac {\ln F(x) - A(x)} {\frac 1 {F(x)}} = F(x) (1 - \ln F(x) + A(x))

多项式快速幂

已知 A(x) ,求 F(x) \equiv A^n(x) \pmod {x^n}

  • 朴素做法,按照一般快速幂做,复杂度 O(n \log^2 n)

  • 进阶做法,转换为 \ln + \exp 来做:
    • A(x) 的常数项为 1 ,则 F(x) = A^n(x) \Rightarrow F(x) = \exp (n \ln A(x))
    • A(x) 的常数项不为 10 ,则 F(x) = A_0 ^ n \exp (n \ln (A(x) / A_0^n))
    • A(x) 的常数项为 0 ,则考虑平移系数并转换为上面的两种情况。

多项式多点求值和快速插值

memset0 的学习笔记

例题:挑战多项式

直接做即可。

代码:

// =================================
//   author: memset0
//   date: 2019.02.19 09:56:53
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
#define poly std::vector <int>
#define for_each(i, a) for (int i = 0, __lim = a.size(); i < __lim; ++i)
namespace ringo {
template <class T> inline void read(T &x) {
    x = 0; char c = getchar(); bool f = 0;
    while (!isdigit(c)) f ^= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    if (f) x = -x;
}
template <class T> inline void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }
inline void print(const poly &a) { for_each(i, a) print(a[i], " \n"[i == __lim - 1]); }
inline void read(poly &a, int n) { for (int i = 0, x; i < n; i++) read(x), a.push_back(x); }

const int N = 1e5 + 10, mod = 998244353;
int n, k; poly f, g;

namespace poly_namespace {
    const int M = N << 3, SIZE = sizeof(int);
    int w[M], rev[M];
    inline poly resize(poly f, int n) { return f.resize(n), f; }
    inline int dec(int a, int b) { a -= b; return a < 0 ? a + mod : a; }
    inline int sub(int a, int b) { a += b; return a >= mod ? a - mod : a; }
    inline int inv(int x) { return x < 2 ? 1 : (ll)(mod - mod / x) * inv(mod % x) % mod; }
    inline int fpow(int a, int b) { int s = 1; for (; b; b >>= 1, a = (ll)a * a % mod) if (b & 1) s = (ll)s * a % mod; return s; }
    inline poly operator + (poly f, int a) { f[0] = sub(f[0], a); return f; }
    inline poly operator + (int a, poly f) { f[0] = sub(a, f[0]); return f; }
    inline poly operator - (poly f, int a) { f[0] = dec(f[0], a); return f; }
    inline poly operator - (int a, poly f) { for_each(i, f) f[i] = dec(0, f[i]); f[0] = sub(a, f[0]); return f; }
    inline poly operator * (poly f, int a) { for_each(i, f) f[i] = (ll)f[i] * a % mod; return f; }
    inline poly operator * (int a, poly f) { for_each(i, f) f[i] = (ll)f[i] * a % mod; return f; }
    inline poly operator + (poly f, const poly &g) {
        f.resize(std::max(f.size(), g.size()));
        for_each(i, f) f[i] = sub(i < f.size() ? f[i] : 0, i < g.size() ? g[i] : 0);
        return f;
    }
    inline poly operator - (poly f, const poly &g) {
        f.resize(std::max(f.size(), g.size()));
        for_each(i, f) f[i] = dec(i < f.size() ? f[i] : 0, i < g.size() ? g[i] : 0);
        return f;
    }
    namespace cipolla_namespace {
        int t, sqr_w;
        typedef std::pair <int, int> pair;
        inline pair operator * (const pair &a, const pair &b) {
            return std::make_pair(((ll)a.first * b.first + (ll)a.second * b.second % mod * sqr_w) % mod,
                ((ll)a.first * b.second + (ll)a.second * b.first) % mod);
        }
        int cipolla(int x) {
            do t = rand() % mod; while (fpow(sqr_w = dec((ll)t * t % mod, x), (mod - 1) >> 1) != mod - 1);
            // printf(">> t = %d sqr_w %d\n", t, sqr_w);
            pair s = std::make_pair(1, 0), a = std::make_pair(t, 1);
            for (int b = (mod + 1) >> 1; b; b >>= 1, a = a * a) if (b & 1) s = s * a;
            // printf(">> %d %d\n", s.first, s.second);
            return std::min(s.first, mod - s.first);
        }
    } using cipolla_namespace::cipolla;
    void ntt(int *a, int lim) {
        for (int i = 0; i < lim; i++) if (i < rev[i]) std::swap(a[i], a[rev[i]]);
        for (int len = 1; len < lim; len <<= 1)
            for (int i = 0; i < lim; i += (len << 1))
                for (int j = 0; j < len; j++) {
                    int x = a[i + j], y = (ll)w[j + len] * a[i + j + len] % mod;
                    a[i + j] = sub(x, y), a[i + j + len] = dec(x, y);
                }
    }
    int init(int len) {
        int lim = 1, k = 0; while (lim < len) lim <<= 1, ++k;
        for (int i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
        return lim;
    }
    void main_init() {
        for (int len = 1, wn; (len << 1) < M; len <<= 1) {
            wn = fpow(3, (mod - 1) / (len << 1)), w[len] = 1;
            for (int i = 1; i < len; i++) w[i + len] = (ll)w[i + len - 1] * wn % mod;
        }
    }
    inline poly operator * (const poly &f, const poly &g) {
        static int a[M], b[M];
        int lim = init(f.size() + g.size() - 1), inv_lim = inv(lim); poly h;
        memset(&a[f.size()], 0, (lim - f.size()) * SIZE); for_each(i, f) a[i] = f[i];
        memset(&b[g.size()], 0, (lim - g.size()) * SIZE); for_each(i, g) b[i] = g[i];
        ntt(a, lim), ntt(b, lim);
        for (int i = 0; i < lim; i++) a[i] = (ll)a[i] * b[i] % mod;
        std::reverse(a + 1, a + lim), ntt(a, lim);
        for (int i = 0, l = f.size() + g.size() - 1; i < l; i++) h.push_back((ll)a[i] * inv_lim % mod);
        return h;
    }
    inline poly inv(const poly &f) {
        static int a[M], b[M];
        poly g(1, inv(f[0]));
        for (int len = 2; (len >> 1) < f.size(); len <<= 1) {
            int lim = init(len << 1), inv_lim = inv(lim);
            memset(&a[len], 0, len * SIZE); for (int i = 0; i < len; i++) a[i] = i < f.size() ? f[i] : 0;
            memset(&b[len], 0, len * SIZE); for (int i = 0; i < len; i++) b[i] = i < g.size() ? g[i] : 0;
            ntt(a, lim), ntt(b, lim);
            for (int i = 0; i < lim; i++) a[i] = (ll)a[i] * b[i] % mod * b[i] % mod;
            std::reverse(a + 1, a + lim), ntt(a, lim), g.resize(len);
            for_each(i, g) g[i] = dec(sub(g[i], g[i]), (ll)a[i] * inv_lim % mod);
        } return g.resize(f.size()), g;
    }
    inline poly sqrt(const poly &f) {
        poly g(1, cipolla(f[0]));
        for (int len = 2; (len >> 1) < f.size(); len <<= 1)
            g = resize(resize(resize(g * g, len) + f, len) * inv(resize(2 * g, len)), len);
        return g.resize(f.size()), g;
    }
    inline poly deri(const poly &f) {
        poly g;
        for (int i = 0; i < f.size() - 1; i++) g.push_back((ll)(i + 1) * f[i + 1] % mod);
        return g.push_back(0), g;
    }
    inline poly inte(poly f) {
        poly g(1, 0);
        for (int i = 0; i < f.size() - 1; i++) g.push_back((ll)inv(i + 1) * f[i] % mod);
        return g;
    }
    inline poly ln(const poly &f) { return inte(resize(deri(f) * inv(f), f.size())); }
    inline poly exp(const poly &f) {
        poly g(1, 1);
        for (int len = 2; (len >> 1) < f.size(); len <<= 1)
            g = resize(g * (1 - ln(resize(g, len)) + resize(f, len)), len);
        return g.resize(f.size()), g;
    }
    inline poly fpow(poly a, int b) {
        int n = a.size(); poly s(1, 1);
        for (; b; b >>= 1, a = resize(a * a, n))
            if (b & 1) s = resize(s * a, n);
        return s;
    }
} using namespace poly_namespace;

void main() {
    srand(20040725);
    read(n), read(k), read(f, n + 1), main_init();
    g = deri(fpow(1 + ln(2 + f - f[0] - exp(inte(inv(sqrt(f))))), k));
    for (int i = 0; i < g.size() - 1; i++) print(g[i], " \n"[i == g.size() - 2]);
}

} signed main() { return ringo::main(), 0; }

多项式求逆 NTT 多项式对数函数 多项式快速幂 多项式多点求值 多项式快速插值 多项式指数函数 多项式

ZJOI2019 Round1 游记
上一篇 «
ZJOI2019前多校联考爆零记录
» 下一篇