国外的建筑设计案例网站,做网站一般要了解哪些,旅游网站开发说明书,免费模版网还不会这题的多项式求逆的算法。 发现每一项都是一个卷积的形式#xff0c;那么我们可以使用$NTT$来加速#xff0c;直接做是$O(n^2logn)$的#xff0c;我们考虑如何加速转移。 可以采用$cdq$分治的思想#xff0c;对于区间$[l, r]$中的数#xff0c;先计算出$[l, mid]$中…还不会这题的多项式求逆的算法。 发现每一项都是一个卷积的形式那么我们可以使用$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
