[洛谷P4238]【模板】多项式求逆

题目大意:多项式求逆

题解:$ A^{-1}(x) = (2 - B(x) * A(x)) \times B(x) \pmod{x^n} $ ($B(x)$ 为$A(x)$在$x^{\lceil \dfrac{n}{2} \rceil}$下的逆元)

卡点:

C++ Code:

#include <cstdio>
#define int long long
#define maxn 262144
using namespace std;
const int mod = 998244353;
const int P = 3, invP = (mod + 1) / P;
int n, l, dig;
int a[maxn], b[maxn], tmp[maxn], rev[maxn];
int pw(int base, int p) {
int ans = 1;
for (p <<= 1; p >>= 1; base = (base * base) % mod) if (p & 1) ans = (ans * base) % mod;
return ans;
}
int inv(int x) {
return pw(x, mod - 2);
}
void swap(int &a, int &b) {a ^= b ^= a ^= b;}
void NTT(int *a, int op) {
int Yx;
if (op == 1) Yx = P; else Yx = invP;
for (int i = 0; i < l; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int mid = 1; mid < l; mid <<= 1) {
int Wn = pw(Yx, (mod - 1) / (mid << 1));
for (int i = 0; i < l; i += mid << 1) {
int W = 1;
for (int j = 0; j < mid; j++, W = W * Wn % mod) {
int X = a[i + j], Y = W * a[i + j + mid] % mod;
a[i + j] = (X + Y) % mod;
a[i + j + mid] = (X - Y + mod) % mod;
}
}
}
if (op == -1) {
int invl = inv(l);
for (int i = 0; i < l; i++) a[i] = a[i] * invl % mod;
}
}
void INV(int *a, int *b, int n) {
if (n == 1) {b[0] = inv(a[0]); return ;}
INV(a, b, n + 1 >> 1);
l = 1; dig = 0; while (l < n << 1) l <<= 1, dig++;
rev[0] = 0; for (int i = 1; i < l; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (dig - 1));
for (int i = 0; i < n; i++) tmp[i] = a[i];
for (int i = n; i < l; i++) tmp[i] = 0;
NTT(b, 1); NTT(tmp, 1);
for (int i = 0; i < l; i++)
b[i] = (2 - tmp[i] * b[i] % mod + mod) % mod * b[i] % mod;
NTT(b, -1);
for (int i = n; i < l; i++) b[i] = 0;
}
signed main() {
scanf("%lld", &n);
for (int i = 0; i < n; i++) scanf("%lld", &a[i]), a[i] %= mod;
INV(a, b, n);
for (int i = 0; i < n; i++) printf("%lld ", b[i]);
return 0;
}

  

上一篇:刚买个炼狱蝰蛇1800dpi的下完驱动提示没有发现鼠标


下一篇:团队作业4——第一次项目冲刺(Alpha版本)第三次