多项式求逆
一些概念
多项式的度：对于一个多项式(A(x)),称其最高项为这个多项式的度，记为(degA)
多项式除法：对于多项式(A(x), B(x)),存在唯一确定的(Q(x),R(x))满足$$A(x) = Q(x)B(x) + R(x)$$
其中(degR< degB).
那么称(Q(x))为(B(x))除(A(x))的商，(R(x))则为对应的余数，可记做：
[A(x) equiv R(x) quad (mod quad B(x))
]
多项式逆元：对于一个多项式(A(x)),如果存在(B(x))满足(degB le degA),且(A(x)B(x) equiv 1 quad (mod quad x^n)),那么称(B(x))为(A(x))在((mod quad x^n))意义下的逆元，记作(A^{-1}(x))
如何求解？
- 当(n = 1)时，有(A(x) equiv c (mod quad x)),其中(c)是一个常数，所以(A^{-1}(x) = c^{-1})
- 对于(n > 1)的情况，设
[B(x) = A^{-1}(x)(mod quad x^n), B'(x) = A^{-1}(x)(mod quad x^{lceil{frac{n}{2}}
ceil})
]
如果可以用(B')和(A)求出(B),那么我们就可以不断将求解(B)变为一个可以不断向下递归的子问题，而对于递归的终点：(n = 1)，我们是可以通过直接计算得到答案的。
因此我们来考虑如何用(A(x))和(B'(x))表示(B(x)).
由(B(x),B'(x))的定义可得：
[A(x)B(x) equiv 1(mod quad x^n) Longrightarrow A(x)B(x) equiv 1 (mod quad x^{lceil {frac{n}{2}}
ceil})
]
[A(x)B'(x) equiv 1(mod quad x^{lceil {frac{n}{2}}
ceil})
]
两式相减：
[A(x)(B(x) - B'(x)) equiv 0 (mod quad x^{lceil {frac{n}{2}}
ceil})
]
[B(x) - B'(x)equiv 0(mod quad x^{lceil {frac{n}{2}}
ceil})
]
两边平方得到：
[B^2(x) - 2B'(x)B(x) + B'^2(x) equiv 0 (mod quad x^{lceil {frac{n}{2}}
ceil})
]
为什么模数也要平方？
左边多项式在((mod quad x^n))意义下为(0),说明其(0)到(n - 1)次项系数均为0，平方后，对于第(0 le i le 2n-1)次项，有其系数(b_i = sum_{j = 0}^i a_ja_{i - j})
可以发现(j)和(i - j)中，必然有一个值小于(n),因此(b_i)必然为(0).
所以平方后在((mod quad x^n))意义下仍为(0)
继续化式子：等式两边同时乘(A(x)),得到
[B(x) - 2B'(x) + A(x)B'^2(x) equiv 0(mod quad x^n)
]
[B(x) equiv 2B'(x) - A(x)B'^2(x)(mod quad x^n)
]
因此不断向上递推即可。
从上面的推导可以发现：一个多项式有无逆元取决于其常数项有无逆元。
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 1000000
#define LL long long
#define p 998244353
const int G = 3, Gi = 332748118;
int n, m, lim = 1, len;
int a[AC], b[AC], rev[AC], c[AC];
inline int read()
{
int x = 0;char c = getchar();
while(c > '9' || c < '0') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x;
}
LL qpow(LL x, int have)
{
LL rnt = 1;
while(have)
{
if(have & 1) rnt = rnt * x % p;
x = x * x % p, have >>= 1;
}
return rnt;
}
void NTT(int *A, int opt)
{
for(R i = 0; i < lim; i ++)
if(i < rev[i]) swap(A[i], A[rev[i]]);
for(R i = 1; i < lim; i <<= 1)
{
LL W = qpow((opt == 1) ? G : Gi, (p - 1) / (i << 1));
for(R r = i << 1, j = 0; j < lim; j += r)
for(R k = 0, w = 1; k < i; k ++, w = 1LL * w * W % p)
{
LL x = A[j + k], y = 1LL * w * A[j + k + i] % p;
A[j + k] = (x + y) % p, A[j + k + i] = (x - y + p) % p;
}
}
}
void pre()
{
n = read();
for(R i = 0; i < n; i ++) a[i] = read();
}
void init(int n, int mid)
{
lim = 1, len = 0;
while(lim <= n) lim <<= 1, ++ len;//重新选定lim
for(R i = 0; i < lim; i ++) //因为重新选了lim，所以rev数组也要更新
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1));
for(R i = 0; i < mid; i ++) c[i] = a[i];//取出要参与运算的 A里面的 前mid项
for(R i = mid; i < lim; i ++) c[i] = 0;//后面清0，不然会对前面的运算有影响
}
void work(int n)//每次问题的规模都会减小一半，因为% x^k,显然大于等于k次的项都会被模掉
{
if(n == 1) {b[0] = qpow(a[0], p - 2); return;}//只剩常数项了，求这个的逆元即可
work((n + 1) >> 1); //先递归下去求解子问题
init(n << 1, n);//2个长度为n的多项式相乘……，所以n + n = 2n
NTT(c, 1), NTT(b, 1);
for(R i = 0; i < lim; i ++)//计算当前层的B值
b[i] = 1LL * b[i] * ((2LL - 1LL * c[i] * b[i] % p + p) % p) % p;
NTT(b, -1);
int inv = qpow(lim, p - 2);//把B数组还原
for(R i = 0; i < n; i ++) b[i] = 1LL * b[i] * inv % p;
for(R i = n; i < lim; i ++) b[i] = 0;//清空后面的项，防止对ans产生影响
}
int main()
{
freopen("in.in", "r", stdin);
pre();
work(n);
for(R i = 0; i < n; i ++) printf("%d ", b[i]);
printf("
");
fclose(stdin);
return 0;
}