【模板】多項式乘法逆

/*Author : lifehappy */ #include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 1e6 + 10, mod = 998244353, G = 3;int r[N], n;ll a[N], b[N], c[N];ll quick_pow(ll a, int n) {ll ans = 1;while(n) {if(n & 1) ans = ans * a % mod;a = a * a % mod;n >>= 1;}return ans; }void NTT(ll *f, int lim, int rev) {for(int i = 0; i < lim; i++) {if(r[i] < i) {swap(f[i], f[r[i]]);}}for(int i = 1; i < lim; i <<= 1) {ll wn = quick_pow(G, (mod - 1) / (i << 1));for(int p = i << 1, j = 0; j < lim; j += p) {ll w = 1;for(int k = 0; k < i; k++, w = w * wn % mod) {ll x = f[j + k], y = w * f[i + j + k] % mod;f[j + k] = (x + y) % mod, f[i + j + k] = (x - y + mod) % mod;}}}if(rev == -1) {ll inv = quick_pow(lim, mod - 2);reverse(f + 1, f + lim);for(int i = 0; i < lim; i++) {f[i] = f[i] * inv % mod;}} }void get_r(int lim) {for(int i = 0; i < lim; ++i) {r[i] = (i & 1) * (lim >> 1) + (r[i >> 1] >> 1);} }void solve(ll *a, ll *b, int n) {if(n == 1) {b[0] = quick_pow(a[0], mod - 2);return ;}solve(a, b, n + 1 >> 1);int lim = 1;n <<= 1;while(lim < n) lim <<= 1;n >>= 1;get_r(lim);for(int i = 0; i < n; i++) c[i] = a[i];for(int i = n; i < lim; i++) c[i] = 0;NTT(b, lim, 1);NTT(c, lim, 1);for(int i = 0; i < lim; i++) {ll temp = (2ll - c[i] * b[i] % mod + mod) % mod;b[i] = b[i] * temp % mod;}NTT(b, lim, -1);for(int i = n; i < lim; i++) {b[i] = 0;} }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf("%d", &n);for(int i = 0; i < n; i++) {scanf("%lld\n", &a[i]);}solve(a, b, n);for(int i = 0; i < n; i++) {printf("%lld%c", b[i], i + 1 == n ? '\n' : ' ');}return 0; }

總結(jié)

以上是生活随笔為你收集整理的多项式求逆模板（NTT + mod）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。