還不會這題的多項式求逆的算法。

發現每一項都是一個卷積的形式，那么我們可以使用$NTT$來加速，直接做是$O(n^2logn)$的，我們考慮如何加速轉移。

可以采用$cdq$分治的思想，對于區間$[l, r]$中的數，先計算出$[l, mid]$中的數對$[mid + 1, r]$中的數的貢獻，然后直接累加到右邊去。

容易發現，這樣子每一次需要用向量$[l,l + 1, l +? 2, \dots, mid]$卷上$g$中$[1, 2, \dots, r - l]$。

時間復雜度$O(nlog^2n)$，感覺這東西跑得并不慢鴨。

Code：

#include <cstdio> #include <cstring> using namespace std; typedef long long ll;const int N = 3e5 + 5; const ll P = 998244353LL;int n, lim, pos[N]; ll f[N], g[N], a[N], b[N];template <typename T> inline void read(T &X) {X = 0; char ch = 0; T op = 1;for (; ch > '9'|| ch < '0'; ch = getchar())if (ch == '-') op = -1;for (; ch >= '0' && ch <= '9'; ch = getchar())X = (X << 3) + (X << 1) + ch - 48;X *= op; }template <typename T> inline void swap(T &x, T &y) {T t = x; x = y; y = t; }inline ll fpow(ll x, ll y) {ll res = 1LL;for (; y > 0; y >>= 1) {if (y & 1) res = res * x % P;x = x * x % P;}return res; }inline void prework(int len) {int l = 0;for (lim = 1; lim <= len; lim <<= 1, ++l);for (int i = 0; i < lim; i++)pos[i] = (pos[i >> 1] >> 1) | ((i & 1) << (l - 1)); }inline void ntt(ll *c, int opt) {for (int i = 0; i < lim; i++)if (i < pos[i]) swap(c[i], c[pos[i]]);for (int i = 1; i < lim; i <<= 1) {ll wn = fpow(3, (P - 1) / (i << 1));if (opt == -1) wn = fpow(wn, P - 2);for (int len = i << 1, j = 0; j < lim; j += len) {ll w = 1;for (int k = 0; k < i; k++, w = w * wn % P) {ll x = c[j + k], y = c[j + k + i] * w % P;c[j + k] = (x + y) % P, c[j + k + i] =(x - y + P) % P;}}}if (opt == -1) {ll inv = fpow(lim, P - 2);for (int i = 0; i < lim; i++) c[i] = c[i] * inv % P;} }void solve(int l, int r) {if (l == r) {a[l] = (a[l] + b[l]) % P;return;}int mid = ((l + r) >> 1);solve(l, mid);prework(r - l + 1);for (int i = 0; i < lim; i++) g[i] = f[i] = 0;for (int i = l; i <= mid; i++) f[i - l] = a[i];for (int i = 1; i <= r - l; i++) g[i - 1] = b[i];ntt(f, 1), ntt(g, 1);for (int i = 0; i < lim; i++) f[i] = f[i] * g[i] % P;ntt(f, -1);for (int i = mid + 1; i <= r; i++) a[i] = (a[i] + f[i - l - 1]) % P;solve(mid + 1, r); }int main() {read(n); n--;for (int i = 1; i <= n; i++) read(b[i]);a[0] = 1;solve(1, n);for (int i = 0; i <= n; i++)printf("%lld%c", a[i], i == n ? '\n' : ' ');return 0; } View Code

?

轉載于:https://www.cnblogs.com/CzxingcHen/p/10197696.html

總結

以上是生活随笔為你收集整理的Luogu 4721 【模板】分治 FFT的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。