板子:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
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 };View Code
标签:eres,int,多项式,void,++,res,相关,mod From: https://www.cnblogs.com/ORzyzRO/p/17971157