要求出满足\(F(x)∗G(x)≡1 (mod x^n)\) 假设已知\(F(x)*H(x) ≡1 (mod x^\lceil \frac{n}{2} \rceil)\) 又\(F(x)*G(x) ≡1 (mod x^\lceil \frac{n}{2} \rceil)\) 所以\(F(x)*(G(x)-H(x)) ≡ 0 (mod x^\lceil \frac{n}{2} \rceil)\) 两边平方\(G(x)^2+H(x)^2-2G(x)H(x) ≡ 0 (mod x^n)\) 两边同时乘F(x) \(F(x)G(x)^2+H(x)^2F(x)-2F(x)G(x)H(x) ≡ 0 (mod x^n)\) 可得\(G(x) ≡ 2H(x)-H(x)^2*F(x) (mod x^n)\) 然后用NTT做多项式乘法...因为第一次写这个，而且NTT也不是很熟练，所以是连写带贺的QWQ过段时间再来重构
#include <bits/stdc++.h> using namespace std; const int Mo = 998244353; const int MAXN = 2100000; int n, a[MAXN], b[MAXN], d[MAXN], rev[MAXN]; inline int read() { char ch; bool f = false; int res = 0; while (((ch = getchar()) < '0' || ch > '9') && ch != '-'); if (ch == '-') f = true; else res = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') res = (res << 3) + (res << 1) + ch - '0'; return f? ~res + 1 : res; } inline int ksm (int x, int y) { int sum = 1; for (; y; ) { if (y & 1) sum = 1LL * sum * x % Mo; y >>= 1; x = 1LL * x * x % Mo; } return sum; } void NTT (int *a, int n, int x){ for (int i = 0; i < n; ++ i) if (i < rev[i]) swap(a[i], a[rev[i]]); for (int i = 1; i < n; i <<= 1) { int y = ksm(3, (Mo - 1) / (i << 1)); for (int j = 0; j < n; j += (i << 1)) { int x1, x2, x3 = 1; for (int k = 0; k < i; ++ k, x3 = 1LL * x3 * y % Mo) { x1 = a[j + k]; x2 = 1LL * x3 * a[j + k + i] % Mo; a[j + k] = (x1 + x2) % Mo; a[j + k + i] = (x1 - x2 + Mo) % Mo; } } } if (x == 1) return; int z = ksm(n, Mo - 2); reverse(a + 1, a + n); for (int i = 0; i < n; ++ i) a[i] = 1LL * a[i] * z % Mo; } void work (int c, int *a, int *b) { if (c == 1) { b[0] = ksm(a[0], Mo - 2); return; } work((c + 1) >> 1, a, b); int len = 0, x = 1; while (x < (c << 1)) x <<= 1, ++ len; for (int i = 1; i < x; ++ i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1)); for (int i = 0; i < c; ++ i) d[i] = a[i]; for (int i = c; i < x; ++ i) d[i] = 0; NTT(d, x, 1); NTT(b, x, 1); for (int i = 0; i < x; ++ i) b[i] = 1LL * (2 - 1LL * d[i] * b[i] % Mo + Mo) % Mo * b[i] % Mo; NTT(b, x, -1); for (int i = c; i < x; ++ i) b[i] = 0; } int main() { n = read(); for (int i = 0; i < n; ++ i) a[i] = read(); work(n, a, b); for (int i = 0; i < n; ++ i) printf("%d ", b[i]); return 0; }转载于:https://www.cnblogs.com/wjnclln/p/10576231.html
相关资源：数据结构—成绩单生成器