多项式全集
Code
#pragma GCC optimize(2, "inline", "Ofast")
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 500;
const int Md = 998244353;
typedef long long ll;
typedef vector<int> Vec;
namespace {
inline int Add(const int &x, const int &y) {return (x + y >= Md) ? (x + y - Md) : (x + y);}
inline int Sub(const int &x, const int &y) {return (x - y < 0) ? (x - y + Md) :(x - y);}
inline int Mul(const int &x, const int &y) {return (ll)x * y % Md;}
int Powe(int x, int y) {
int ans = 1;
while(y) {
if(y & 1) ans = Mul(ans, x);
x = Mul(x, x);
y >>= 1;
}
return ans;
}
}
void read(int &x) {
x = 0; int f = 1; char ch = getchar();
while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
x *= f;
}
int n, m, a, b;
namespace Poly {
int rev[N << 2 | 1], inv[N];
int Iv2;
void Init() {
inv[0]=0; inv[1]=1;
for(int i = 2; i < N; i++) {
inv[i] = ((ll)(Md - Md / i) * inv[Md % i]) % Md;
}
Iv2 = Powe(2, Md - 2);
}
void DFT(Vec &A, int len) {
for(int i = 0; i < len; i++) if(i < rev[i]) swap(A[i], A[rev[i]]);
for(int i = 1; i < len; i <<= 1) {
int wn = Powe(3, (Md - 1) / (i << 1));
for(int j = 0; j < len; j += i << 1) {
int nw = 1, x, y;
for(int k = 0; k < i; k++, nw = Mul(nw, wn)) {
x = A[j + k], y = Mul(nw, A[i + j + k]);
A[j + k] = Add(x, y); A[i + j + k] = Sub(x, y);
}
}
}
}
void IDFT(Vec &A, int len) {
reverse(A.begin() + 1, A.end());
int Iv = Powe(len, Md - 2);
DFT(A, len);
for(int i = 0; i < len; i++) A[i] = Mul(A[i], Iv);
}
Vec MUL(Vec A, Vec B) {
int n = A.size(), m = B.size(), len;
for(len = 1; len < n + m - 1; len <<= 1);
A.resize(len), B.resize(len);
for(int i = 0; i < len; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? len >> 1 : 0);
DFT(A, len), DFT(B, len);
for(int i = 0; i < len; i++) A[i] = Mul(A[i], B[i]);
IDFT(A, len);
A.resize(n + m - 1);
return A;
}
Vec GetInv(Vec A, int len) {
Vec C, B(1, Powe(A[0], Md - 2));
for(int i = 2; (i >> 1) < len; i <<= 1) {
for(int j = 0; j < (i << 1); j++) rev[j] = (rev[j >> 1] >> 1) | ((j & 1) ? i : 0);
C = A; C.resize(i);
C.resize(i << 1); DFT(C, i << 1);
B.resize(i << 1); DFT(B, i << 1);
for(int j = 0; j < (i << 1); j++) B[j] = Mul(B[j], Sub(2, Mul(C[j], B[j])));
IDFT(B, i << 1);
B.resize(i);
}
B.resize(len);
return B;
}
void GetDiv(Vec A, Vec B, Vec &Q, Vec &R) {
Q.resize(n + 1); Vec Gr; Gr.clear(); Gr.resize(m + 1);
for(int i = 0; i <= n; i++) Q[i] = A[n - i];
for(int i = 0; i <= m; i++) Gr[i] = B[m - i];
for(int i = n - m + 2; i <= m; i++) Gr[i] = 0;
Vec Iv; Iv.clear();
Gr.resize(n - m + 1); Iv.resize(n - m + 1);
Iv = GetInv(Gr, n - m + 1);
Q = MUL(Q, Iv);
Q.resize(n - m + 1);
reverse(Q.begin(), Q.end());
for(int i = n - m + 1; i <= n; i++) Q[i] = 0;
R = MUL(Q, B);
for(int i = 0; i <= m - 1; i++) R[i] = Add(A[i], Sub(Md, R[i]));
}
Vec Dir(Vec A) {
Vec B = A; int len = A.size(); B.resize(len);
for(int i = 1; i < len; i++) B[i - 1] = Mul(A[i], i);
B[len - 1] = 0;
return B;
}
Vec Inter(Vec A) {
Vec B = A; int len = A.size(); B.resize(len);
for(int i = 1; i < len; i++) B[i] = Mul(A[i - 1], inv[i]);
B[0] = 0;
return B;
}
Vec Ln(Vec A, int len) {
A = Inter(MUL(Dir(A), GetInv(A, len)));
A.resize(len);
return A;
}
Vec Exp(Vec A, int len) {
Vec B(1, 1), F;
for(int i = 2; (i >> 1) < len; i <<= 1) {
if((int)A.size() < i) A.resize(i);
F = Ln(B, i);
for(int j = 0; j < i; j++) F[j] = Sub(A[j], F[j]);
F[0] = Add(F[0], 1);
B = MUL(B, F);
B.resize(i);
}
B.resize(len);
return B;
}
Vec Powe(Vec A, int len, int k) {
k %= Md;
int x = ::Powe(A[0], Md - 2);
int y = ::Powe(A[0], k);
Vec B = A;
for(int i = 0; i < len; i++) B[i] = Mul(B[i], x);
B = Ln(B, len);
for(int i = 0; i < len; i++) B[i] = Mul(B[i], k);
B = Exp(B, len);
for(int i = 0; i < len; i++) B[i] = Mul(B[i], y);
return B;
}
Vec Sqrt(Vec A, int len) {
assert(A[0] == 4);
Vec C, D, B(1, 2);
for (int i = 2; (i >> 1) < len; i <<= 1) {
C = A, C.resize(i);
D = GetInv(B, i);
C = MUL(C, D);
B.resize(i);
for (int j = 0; j < i; j++) B[j] = Mul(Add(C[j], B[j]), Iv2);
}
B.resize(len);
return B;
}
}
int main() {
Poly::Init();
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/10279531.html
相关资源：JAVA上百实例源码以及开源项目
