多项式相关

板子：

  1 const int N = 4e5 + 5;
  2 
  3 struct NTT {
  4     const int mod = 998244353, G = 3, invG = 332748118;
  5     int rev[N], res[N], Inv[N], Res[N], eres[N], Eres[N];
  6 
  7     void preinv(int n) {
  8         Inv[0] = Inv[1] = 1;
  9         for (int i = 2; i <= n; i++) {
 10             Inv[i] = 1ll * (mod - mod / i) * Inv[mod % i] % mod;
 11         }
 12     }
 13 
 14     NTT() {
 15         preinv(2e5);
 16     }
 17 
 18     int qpow(int x, int y) {
 19         int a = 1;
 20 
 21         while (y) {
 22             if (y & 1) a = 1ll * a * x % mod;
 23             x = 1ll * x * x % mod;
 24             y /= 2;
 25         }
 26 
 27         return a;
 28     }
 29 
 30     void init(int n) {
 31         rev[0] = 0;
 32 
 33         for (int i = 1; i < n; i++) {
 34             rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
 35         }
 36     }
 37 
 38     void DFT(int f[], int n, int flag) {
 39         for (int i = 0; i < n; i++) {
 40             if (i < rev[i]) swap(f[i], f[rev[i]]);
 41         }
 42 
 43         for (int len = 2; len <= n; len <<= 1) {
 44             int Len = len >> 1;
 45             int g = qpow((flag ? invG : G), (mod - 1) / len);
 46 
 47             for (int l = 0; l < n; l += len) {
 48                 int now = 1;
 49                 for (int i = l; i < l + Len; i++) {
 50                     int lst = 1ll * f[i + Len] * now % mod;
 51                     f[i + Len] = (f[i] + mod - lst) % mod;
 52                     f[i] = (f[i] + lst) % mod;
 53                     now = 1ll * now * g % mod;
 54                 }
 55             }
 56         }
 57 
 58         if (!flag) return;
 59 
 60         int inv = qpow(n, mod - 2);
 61 
 62         for (int i = 0; i < n; i++) {
 63             f[i] = 1ll * f[i] * inv % mod;
 64         }
 65     }
 66 
 67     void Mul(int f[], int g[], int n, int flag = 0) {
 68         init(n);
 69         DFT(f, n, 0);
 70         DFT(g, n, 0);
 71         for (int i = 0; i < n; i++) {
 72             f[i] = 1ll * f[i] * g[i] % mod;
 73         }
 74         DFT(f, n, 1);
 75         if (flag) DFT(g, n, 1);
 76     }
 77 
 78     void getinv(int f[], int g[], int n) {
 79         if (n == 1) {
 80             g[0] = qpow(f[0], mod - 2);
 81             return;
 82         }
 83 
 84         getinv(f, g, n / 2);
 85 
 86         for (int i = 0; i < n; i++) res[i] = f[i];
 87         for (int i = n; i < 2 * n; i++) res[i] = 0;
 88 
 89         init(2 * n);
 90         DFT(g, 2 * n, 0);
 91         DFT(res, 2 * n, 0);
 92 
 93         for (int i = 0; i < 2 * n; i++) {
 94             g[i] = 1ll * (2 + mod - 1ll * res[i] * g[i] % mod) % mod * g[i] % mod;
 95         }
 96 
 97         DFT(g, 2 * n, 1);
 98 
 99         for (int i = n; i < 2 * n; i++) g[i] = 0;
100     }
101 
102     void Deriv(int f[], int n) {
103         for (int i = 0; i < n - 1; i++) {
104             f[i] = 1ll * f[i + 1] * (i + 1) % mod;
105         }
106         f[n - 1] = 0;
107     }
108 
109     void Integral(int f[], int n) {
110         for (int i = n - 1; i > 0; i--) {
111             f[i] = 1ll * f[i - 1] * Inv[i] % mod;
112         }
113         f[0] = 0;
114     }
115 
116     void Ln(int f[], int g[], int n) {
117         for (int i = 0; i < 2 * n; i++) Res[i] = 0;
118         getinv(f, Res, n);
119         for (int i = 0; i < n; i++) res[i] = f[i];
120         for (int i = n; i < 2 * n; i++) res[i] = 0;
121         Deriv(res, n);
122         Mul(res, Res, 2 * n);
123         Integral(res, n);
124         for (int i = 0; i < n; i++) g[i] = res[i];
125     }
126 
127     void exp(int f[], int g[], int n) {
128         if (n == 1) {
129             g[0] = 1;
130             return;
131         }
132 
133         exp(f, g, n / 2);
134         for (int i = 0; i < n; i++) eres[i] = 0;
135         Ln(g, eres, n);
136         for (int i = 0; i < n; i++) {
137             eres[i] += mod - f[i];
138             if (eres[i] >= mod) eres[i] -= mod;
139         }
140         Mul(eres, g, n * 2, 1);
141         for (int i = n; i < 2 * n; i++) eres[i] = 0;
142         for (int i = 0; i < n; i++) {
143             g[i] += mod - eres[i];
144             if (g[i] >= mod) g[i] -= mod;
145         }
146         for (int i = n; i <= 2 * n; i++) g[i] = 0;
147     }
148 };