多项式全家桶学习笔记
Warriors_Cat
2020-08-24 09:42:27
# 多项式全家桶
## -1.说明
这个东西是给自己看的，建议不要当做多项式参考资料，大家能看得懂就看吧qaq
to do list:
too many……
## 0.参考资料
[初学 FFT 专用](https://www.luogu.com.cn/blog/command-block/fft-xue-xi-bi-ji)
[NTT 和全家桶](https://www.luogu.com.cn/blog/command-block/ntt-yu-duo-xiang-shi-quan-jia-tong)
## 1. 前置模板
NTT 模板加上一堆东西。
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define dingyi int mid = l + r >> 1, ls = p << 1, rs = p << 1 | 1
#define y0 y_csyakioi_0
#define y1 y_csyakioi_1
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define per(i, x, y) for(int i = x; i >= y; --i)
#define repg(i, u) for(int i = head[u]; i; i = e[i].nxt)
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 600010, mod = 998244353, g_ = 3, invg = 332748118, I = 86583718, inv2 = 449122177, inv2I = 954952494;
int n, A[N], B[N], C[N], D[N], a[N], b[N], c[N], d[N], e[N], f[N], g[N], h[N], r[N], rev, inv[N]; bool isinv;
inline int fpow(int x, int p){ int ans = 1; for(; p; p >>= 1, x = 1ll * x * x % mod) if(p & 1) ans = 1ll * ans * x % mod; return ans; }
inline void clr(int *A, int x){ memset(A, 0, sizeof(int)*x); }
inline void cpy(int *A, int *B, int x){ memcpy(A, B, sizeof(int)*x); }
inline void NTT(int typ, int *a, int lim){
if(rev != lim){ rev = lim; rep(i, 0, lim - 1) r[i] = (r[i >> 1] >> 1) | ((i & 1) ? (lim >> 1) : 0); }
rep(i, 0, lim - 1) if(i < r[i]) swap(a[i], a[r[i]]);
for(int mid = 1; mid < lim; mid <<= 1){
int R = mid << 1, rt = fpow(typ == 1 ? g_ : invg, (mod - 1) / R);
for(int j = 0; j < lim; j += R){
int w = 1;
for(int k = 0; k < mid; ++k, w = 1ll * w * rt % mod){
int x = a[j | k], y = 1ll * w * a[j | k | mid] % mod;
a[j | k] = (x + y) % mod; a[j | k | mid] = (x - y + mod) % mod;
}
}
}
if(typ < 0){ int k = fpow(lim, mod - 2); rep(i, 0, lim - 1) a[i] = 1ll * a[i] * k % mod; }
}
inline void ptm(int *A, int *B, int len){ rep(i, 0, len - 1) A[i] = 1ll * A[i] * B[i] % mod; }
inline void print(int *A, int len){ rep(i, 0, len - 1) printf("%d ", A[i]); puts(""); }
inline void Polymul(int *A, int *B, int len, int m){
int lim = 1; while(lim < len) lim <<= 1;
cpy(e, B, lim); clr(e + m, lim - m);
NTT(1, A, lim); NTT(1, e, lim); ptm(A, e, lim);
NTT(-1, A, lim); clr(A + m, lim - m);
}
inline void mian(){
}
int main(){ int qwq = 1; while(qwq--) mian(); return 0; }
```
## 2. 多项式求逆
[模板题](https://www.luogu.com.cn/problem/P4238)
递归思想。
记
$$R(x) F(x)\equiv1(\!\!\!\!\!\!\mod\ x^n)$$
若有一个多项式 $R^{-1}(x)$，使得
$$R^{-1}(x)F(x)\equiv1(\!\!\!\!\!\!\mod\ x^{\frac{n}{2}})$$
显然有
$$R(x)-R^{-1}(x)\equiv0(\!\!\!\!\!\!\mod\ x^{\frac{n}{2}})$$
平方可得：
$$R(x)^2-2R(x)R^{-1}(x)+R^{-1}(x)^2\equiv0(\!\!\!\!\!\!\mod\ x^n)$$
等式两边乘上 $F(x)$，由 $R(x)F(x)\equiv 1(\!\!\!\!\mod\ x^n)$ 可得
$$R(x)\equiv2R^{-1}(x)-R^{-1}(x)^2F(x)(\!\!\!\!\!\!\mod\ x^n)$$
于是可以递归了。
边界条件就是 $R(x)$ 只有一项，求个逆元即可。
```cpp
inline void Polyinv(int *A, int len){
int lim = 1; while(lim < len) lim <<= 1;
a[0] = fpow(A[0], mod - 2);
for(int m = 2; m <= lim; m <<= 1){
rep(i, 0, (m >> 1) - 1) b[i] = (a[i] << 1) % mod;
cpy(f, A, m);
NTT(1, a, m << 1); ptm(a, a, m << 1);
NTT(1, f, m << 1); ptm(a, f, m << 1);
NTT(-1, a, m << 1); clr(a + m, m);
rep(i, 0, m - 1) a[i] = (b[i] - a[i] + mod) % mod;
}
cpy(A, a, len); clr(a, lim << 1); clr(b, lim << 1); clr(f, lim << 1);
}
```
[AC记录](https://www.luogu.com.cn/record/36451701)
## 3. 多项式求导/积分
无模板，为后面很多多项式操作做铺垫。
求导没多大学，[参考资料](https://www.luogu.com.cn/paste/k9i6ktfv)，通过这个东西知道了一些皮毛。
求导定义：
记 $\Delta y=F(x+\Delta x)-F(x)$。
那么
$$F'(x) = \lim_{\Delta x\rightarrow 0}\dfrac{\Delta y}{\Delta x}$$
比如对 $F(x)=x^3$ 求导：
$$\Delta y=F(x+\Delta x)-F(x)$$
$$=x^3+3x^2\Delta x+3x\Delta x^2+\Delta x^3-x^3$$
$$=3x^2\Delta x+3x\Delta x^2+\Delta x^3$$
那么
$$F'(x) = \lim_{\Delta x\rightarrow0}{\dfrac{\Delta y}{\Delta x}}$$
$$=\lim_{\Delta x\rightarrow0}(3x^2+3x\Delta x+\Delta x^2)$$
$$=3x^2$$
简单结论：
>1. 若 $F(x) = kx^n(n \in \operatorname N^*)$，则 $F'(x)=knx^{n-1}$。
>证明：二项式定理展开即可。
>2. $F'(x)+G'(x)=(F(x)+G(x))'$，即求导具有**线性性**。
>证明：显然 $F(x)$ 与 $G(x)$ 互不干扰，或者手玩一下即可。
>3. $kF'(x)=(kF(x))'$
>证明：同上。
积分为求导的逆运算，记为 $\int \!F(x)dx$。
结论 1 与结论 2 结合即可求导成功。
```cpp
inline void Polyder(int *A, int len){ rep(i, 1, len - 1) A[i - 1] = 1ll * A[i] * i % mod; A[len - 1] = 0; }
inline void initinv(){ if(isinv) return; isinv = inv[0] = inv[1] = 1; rep(i, 2, N - 10) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod; }
inline void Polyint(int *A, int len){ initinv(); per(i, len, 1) A[i] = 1ll * A[i - 1] * inv[i] % mod; A[0] = 0; }
```
## 4.多项式牛顿迭代
若 $G(F(x))\equiv 0(\!\!\!\!\mod\ x^n)$，且 $G(F^{-1}(x))\equiv0(\!\!\!\!\mod x^\frac{n}{2})$
那么有：
$$F(x)\equiv F^{-1}(x)-\frac{G(F^{-1}(x))}{G'(F^{-1}(x))}(\!\!\!\!\!\!\mod\ x^n)$$
证明：
$$F(x)\equiv F^{-1}(x)(\!\!\!\!\!\!\mod\ x^n)$$
将 $G(F(x))$ 在 $F^{-1}(x)$ 处进行[泰勒展开](https://baike.baidu.com/item/%E6%B3%B0%E5%8B%92%E5%85%AC%E5%BC%8F/7681487?fr=aladdin)：
$$G(F(x))=\sum_{i=0}\frac{G^{(i)}(F^{-1}(x))}{i!}(F(x)-F^{-1}(x))^i$$
其中 $i\ge 2$ 那些项的次数大于等于 $n$，于是在模 $x^n$ 意义下全没了。
$$G(F(x))=G(F^{-1}(x))+G'(F^{-1}(x))(F(x)-F^{-1}(x))$$
由 $G(F(x))=0$ 和魔怔化简就可以得到
$$F(x)\equiv F^{-1}(x)-\frac{G(F^{-1}(x))}{G'(F^{-1}(x))}(\!\!\!\!\!\!\mod\ x^n)$$
证毕。
## 5. 多项式开根
[模板题](https://www.luogu.com.cn/problem/P5205)
递归思想。
记 $G(B(x))=B(x)^2-A(x)$，那么 $G'(B(x))=2B(x)$
由多项式牛顿迭代可得
$$B(x)\equiv B^{-1}(x)-\frac{G(B^{-1}(x))}{G'(B^{-1}(x))}(\!\!\!\!\!\!\mod\ x^n)$$
由于上面两个式子可得：
$$B(x)\equiv B^{-1}(x)-\frac{B^{-1}(x)^2-A(x)}{2B^{-1}(x)}(\!\!\!\!\!\!\mod\ x^n)$$
化简可得
$$B(x)\equiv\frac{A(x)+B^{-1}(x)^2}{2B^{-1}(x)}(\!\!\!\!\!\!\mod\ x^n)$$
加强版先咕着，以后搞。
```cpp
inline void Polysqrt(int *A, int len){
int lim = 1; while(lim < len) lim <<= 1; c[0] = 1;
for(int m = 2; m <= lim; m <<= 1){
rep(i, 0, (m >> 1) - 1) d[i] = (c[i] << 1) % mod;
Polyinv(d, m);
NTT(1, c, m); ptm(c, c, m); NTT(-1, c, m);
rep(i, 0, m - 1) c[i] = (A[i] + c[i]) % mod;
Polymul(c, d, m << 1, m);
}
cpy(A, c, len); clr(c, lim << 1); clr(d, lim << 1);
}
```
[AC记录](https://www.luogu.com.cn/record/36454587)
## 6. 多项式除法
[模板题](https://www.luogu.com.cn/problem/P4512)
由于有余数，我们就不能用求逆来计算了。
于是重新推导式子。
$$F(x)=Q(x)G(x)+R(x)$$
$$x^nF(x^{-1})=x^nQ(x^{-1})G(x^{-1})+x^nR(x^{-1})$$
我们定义 $k$ 次多项式 $F^R(x)=x^kF(x^{-1})$
易证 $F(x)$ 与 $F^R(x)$ 系数翻转了一下
将上面的式子用翻转式来表示：
$$F^R(x)=Q^R(x)G^R(x)+x^{n-m+1}R^R(x)$$
模一个 $x^{n-m+1}$ 可得
$$F^R(x)\equiv Q^R(x)G^R(x)(\!\!\!\!\!\!\mod\ x^{n-m+1})$$
$$Q^R(x)\equiv \frac{F^R(x)}{G^R(x)}$$
于是 $Q^R(x)$ 求出来了，那么 $Q(x)$ 也有了。
$Q(x)$ 求出来后 $R(x)$ 也很显然了，$R(x)=F(x)-Q(x)G(x)$。
```cpp
inline void Rev(int *A, int len){ rep(i, 0, (len >> 1) - 1) swap(A[i], A[len - i - 1]); }
inline void Polydiv(int *A, int *B, int n, int m){
int len = n - m + 1;
Rev(B, m); cpy(c, B, len); Rev(B, m);
Rev(A, n); cpy(d, A, len); Rev(A, n);
Polyinv(c, len); Polymul(c, d, len << 1, len); Rev(c, len);
Polymul(B, c, n << 1, n);
rep(i, 0, m - 2) B[i] = (A[i] - B[i] + mod) % mod;
clr(B + m - 1, n - m + 1); cpy(A, c, len); clr(A + len, n - len);
}
```
[AC记录](https://www.luogu.com.cn/record/36463935)
## 7.多项式 ln
这里的 ln 是通过求导+积分得到的。
$$B(x)\equiv \ln A(x)(\!\!\!\!\!\!\mod\ x^n)$$
$$B'(x)\equiv \ln 'A(x)A'(x)(\!\!\!\!\!\!\mod\ x^{n-1})$$
$$B'(x)\equiv\frac{A'(x)}{A(x)}(\!\!\!\!\!\!\mod\ x^{n-1})$$
$$B(x)\equiv\int\frac{A'(x)}{A(x)}dx(\!\!\!\!\!\!\mod\ x^n)$$
没了。
```cpp
inline void Polyln(int *A, int len){
cpy(c, A, len); Polyinv(c, len); Polyder(A, len);
Polymul(A, c, len << 1, len); Polyint(A, len - 1); clr(c, len);
}
```
[AC记录](https://www.luogu.com.cn/record/36562082)
## 8. 多项式 exp
递归 + 牛顿迭代，推式子吧。
$$B(x)\equiv e^{A(x)}(\!\!\!\!\!\!\mod\ x^n)$$
$$\ln B(x)-A(x)\equiv0(\!\!\!\!\!\!\mod\ x^n)$$
记 $G(B(x))=\ln B(x)-A(x)$，那么 $G'(B(x))=\frac{1}{B(x)}$。
由多项式牛顿迭代可得
$$B(x)\equiv B^{-1}(x)-\frac{G(B^{-1}(x))}{G'(B^{-1}(x))}(\!\!\!\!\!\!\mod\ x^n)$$
将上面式子带入
$$B(x)=\equiv B^{-1}(x)-\frac{\ln B^{-1}(x)-A(x)}{\frac{1}{B^{-1}(x)}}(\!\!\!\!\!\!\mod\ x^n)$$
$$B(x)\equiv B^{-1}(x)(1-\ln B^{-1}(x)+A(x))(\!\!\!\!\!\!\mod\ x^n)$$
可以递推了。
```cpp
inline void Polyexp(int *A, int len){
int lim = 1; while(lim < len) lim <<= 1; g[0] = 1;
for(int m = 2; m <= lim; m <<= 1){
cpy(h, g, m >> 1); Polyln(h, m);
rep(i, 0, m - 1) h[i] = (A[i] - h[i] + mod) % mod;
h[0] = (h[0] + mod) % mod; Polymul(g, h, m << 1, m);
}
cpy(A, g, len); clr(g, lim << 1); clr(h, lim << 1);
}
```
[AC记录](https://www.luogu.com.cn/record/36643078)
## 9. 多项式快速幂
应该是一个最为简单的板子了。
核心式子：
$$A^k(x)=e^{\ln A(x) \times k}$$
没了。
```cpp
inline void Polypow(int *A, int len, int k){
Polyln(A, len);
rep(i, 0, len - 1) A[i] = 1ll * A[i] * k % mod;
Polyexp(A, len);
}
```
[AC记录](https://www.luogu.com.cn/record/36694673)
## 10. 多项式快速幂加强版
一堆细节，烦死了（
首先，由于 $a_0\neq 1$，所以无法直接求。
于是考虑把原多项式同时除一个 $a_0$，最后再乘回来。
但有可能 $a_0 = 0$，所以我们要找到第一个 $t$ 满足 $a_t\neq0$，然后进行计算。
具体一些：
$$B(x)\equiv \left[\dfrac{A(x)}{a_tx^t}\right ]^m\times {a_t}^mx^{tm}(\bmod\ x^n)$$
然后就是细节了：
1. 一次加强后 $m$ 变为高精度数，所以原来用低精度读入会锅。
2. 很多题解直接将 $m$ 模了 $998244353$，但当普通多项式快速幂做完需要补零的时候，这个 $m$ 可能变得很小很小，导致补零不够，可实际上 $m$ 是一个极大数，所以应当全部为 $0$。
3. 这道题主要思路就是找到第一个 $a_t \neq 0$，然后计算 $[\dfrac{A(x)}{a_tx^t}]^m \times {a_t}^m\times x^{tm}$。然而在这里计算 ${a_t}^m$ 时，$m$ 要取模的不是 $998244353$ 而是 $998244352$。
然后没了。
[AC记录](https://www.luogu.com.cn/record/37409552)
## 11. 多项式三角函数
直接套用欧拉公式：
$$e^{ix}=\cos x + i\sin x$$
$$e^{-ix}=\cos x - i\sin x$$
代入 $x = A(x)$ 可得：
$$\sin A(x)=\dfrac{e^{iA(x)}-e^{-iA(x)}}{2i}$$
$$\cos A(x)=\dfrac{e^{iA(x)}+e^{-iA(x)}}{2}$$
在模意义下 $i\equiv\omega_4^1\equiv g^{\frac{p - 1}{4}}(\bmod\ p)$，当 $p=998244353$ 时 $i=86583718$。
于是这题没了。
```cpp
inline void Polysincos(int *A, int len, int opt){//0:sin
cpy(C, A, len); cpy(D, A, len);
rep(i, 0, len - 1) C[i] = 1ll * C[i] * I % mod;
rep(i, 0, len - 1) D[i] = 1ll * D[i] * (mod - I) % mod;
Polyexp(C, len); Polyexp(D, len);
if(opt) rep(i, 0, len - 1) A[i] = 1ll * (C[i] + D[i]) % mod * inv2 % mod;
else rep(i, 0, len - 1) A[i] = 1ll * (C[i] - D[i] + mod) % mod * inv2I % mod;
clr(C, len); clr(D, len);
}
```
[AC记录](https://www.luogu.com.cn/record/40221257)
## 12. 多项式反三角函数
如同多项式 $\ln$，求导再积分。
先是 $\arcsin :$
$$F(x)\equiv \arcsin A(x)(\bmod \ x^n)$$
$$F'(x)\equiv\dfrac{A'(x)}{\sqrt{1 - A(x)^2}}(\bmod\ x^{n-1})$$
$$F(x)\equiv\int\dfrac{A'(x)}{\sqrt{1-A(x)^2}}dx(\bmod \ x^n)$$
然后是 $\arctan :$
$$F(x)\equiv \arctan A(x)(\bmod \ x^n)$$
$$F'(x)\equiv \dfrac{A'(x)}{1 + A(x)^2}(\bmod \ x^{n-1})$$
$$F(x)\equiv \int \dfrac{A'(x)}{1+A(x)^2}dx(\bmod\ x^n)$$
没了。
```cpp
inline void Polyasin(int *A, int len){
cpy(C, A, len); Polyder(A, len);
Polymul(C, C, len << 1, len);
rep(i, 0, len - 1) C[i] = mod - C[i];
C[0] = (C[0] + 1) % mod;
Polysqrt(C, len); Polyinv(C, len);
Polymul(A, C, len << 1, len);
Polyint(A, len - 1); clr(C, len);
}
inline void Polyatan(int *A, int len){
cpy(C, A, len); Polyder(A, len);
Polymul(C, C, len << 1, len); C[0] = (C[0] + 1) % mod;
Polyinv(C, len); Polymul(A, C, len << 1, len);
Polyint(A, len - 1); clr(C, len);
}
```
## inf. 全 家 桶
这一版会跟着学习进度更新。
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define dingyi int mid = l + r >> 1, ls = p << 1, rs = p << 1 | 1
#define y0 y_csyakioi_0
#define y1 y_csyakioi_1
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define per(i, x, y) for(int i = x; i >= y; --i)
#define repg(i, u) for(int i = head[u]; i; i = e[i].nxt)
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 300010, mod = 998244353, g_ = 3, invg = 332748118, I = 86583718, inv2 = 449122177, inv2I = 954952494;
int n, m, A[N], B[N], C[N], D[N], a[N], b[N], c[N], d[N], e[N], f[N], g[N], h[N], r[N], rev, inv[N]; bool isinv;
inline int fpow(int x, int p){ int ans = 1; for(; p; p >>= 1, x = 1ll * x * x % mod) if(p & 1) ans = 1ll * ans * x % mod; return ans; }
inline void clr(int *A, int x){ memset(A, 0, sizeof(int)*x); }
inline void cpy(int *A, int *B, int x){ memcpy(A, B, sizeof(int)*x); }
inline void NTT(int typ, int *a, int lim){
if(rev != lim){ rev = lim; rep(i, 0, lim - 1) r[i] = (r[i >> 1] >> 1) | ((i & 1) ? (lim >> 1) : 0); }
rep(i, 0, lim - 1) if(i < r[i]) swap(a[i], a[r[i]]);
for(int mid = 1; mid < lim; mid <<= 1){
int R = mid << 1, rt = fpow(typ == 1 ? g_ : invg, (mod - 1) / R);
for(int j = 0; j < lim; j += R){
int w = 1;
for(int k = 0; k < mid; ++k, w = 1ll * w * rt % mod){
int x = a[j | k], y = 1ll * w * a[j | k | mid] % mod;
a[j | k] = (x + y) % mod; a[j | k | mid] = (x - y + mod) % mod;
}
}
}
if(typ < 0){ int k = fpow(lim, mod - 2); rep(i, 0, lim - 1) a[i] = 1ll * a[i] * k % mod; }
}
inline void ptm(int *A, int *B, int len){ rep(i, 0, len - 1) A[i] = 1ll * A[i] * B[i] % mod; }
inline void print(int *A, int len){ rep(i, 0, len - 1) printf("%d ", A[i]); puts(""); }
inline void Polymul(int *A, int *B, int len, int m){
int lim = 1; while(lim < len) lim <<= 1;
cpy(e, B, lim); clr(e + m, lim - m);
NTT(1, A, lim); NTT(1, e, lim); ptm(A, e, lim);
NTT(-1, A, lim); clr(A + m, lim - m);
}
inline void Polyinv(int *A, int len){
int lim = 1; while(lim < len) lim <<= 1;
a[0] = fpow(A[0], mod - 2);
for(int m = 2; m <= lim; m <<= 1){
rep(i, 0, (m >> 1) - 1) b[i] = (a[i] << 1) % mod;
cpy(f, A, m);
NTT(1, a, m << 1); ptm(a, a, m << 1);
NTT(1, f, m << 1); ptm(a, f, m << 1);
NTT(-1, a, m << 1); clr(a + m, m);
rep(i, 0, m - 1) a[i] = (b[i] - a[i] + mod) % mod;
}
cpy(A, a, len); clr(a, lim << 1); clr(b, lim << 1); clr(f, lim << 1);
}
inline void Polysqrt(int *A, int len){
int lim = 1; while(lim < len) lim <<= 1; c[0] = 1;
for(int m = 2; m <= lim; m <<= 1){
rep(i, 0, (m >> 1) - 1) d[i] = (c[i] << 1) % mod;
Polyinv(d, m);
NTT(1, c, m); ptm(c, c, m); NTT(-1, c, m);
rep(i, 0, m - 1) c[i] = (A[i] + c[i]) % mod;
Polymul(c, d, m << 1, m);
}
cpy(A, c, len); clr(c, lim << 1); clr(d, lim << 1);
}
inline void Rev(int *A, int len){ rep(i, 0, (len >> 1) - 1) swap(A[i], A[len - i - 1]); }
inline void Polydiv(int *A, int *B, int n, int m){
int len = n - m + 1;
Rev(B, m); cpy(c, B, len); Rev(B, m);
Rev(A, n); cpy(d, A, len); Rev(A, n);
Polyinv(c, len); Polymul(c, d, len << 1, len); Rev(c, len);
Polymul(B, c, n << 1, n);
rep(i, 0, m - 2) B[i] = (A[i] - B[i] + mod) % mod;
clr(B + m - 1, n - m + 1); cpy(A, c, len); clr(A + len, n - len);
}
inline void Polyder(int *A, int len){ rep(i, 1, len - 1) A[i - 1] = 1ll * A[i] * i % mod; A[len - 1] = 0; }
inline void initinv(){ if(isinv) return; isinv = inv[0] = inv[1] = 1; rep(i, 2, N - 10) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod; }
inline void Polyint(int *A, int len){ initinv(); per(i, len, 1) A[i] = 1ll * A[i - 1] * inv[i] % mod; A[0] = 0; }
inline void Polyln(int *A, int len){
cpy(c, A, len); Polyinv(c, len); Polyder(A, len);
Polymul(A, c, len << 1, len); Polyint(A, len - 1); clr(c, len);
}
inline void Polyexp(int *A, int len){
int lim = 1; while(lim < len) lim <<= 1; g[0] = 1;
for(int m = 2; m <= lim; m <<= 1){
cpy(h, g, m >> 1); Polyln(h, m);
rep(i, 0, m - 1) h[i] = (A[i] - h[i] + mod) % mod;
h[0] = (h[0] + 1) % mod; Polymul(g, h, m << 1, m);
}
cpy(A, g, len); clr(g, lim << 1); clr(h, lim << 1);
}
inline void Polypow(int *A, int len, int k){
Polyln(A, len);
rep(i, 0, len - 1) A[i] = 1ll * A[i] * k % mod;
Polyexp(A, len);
}
inline void Polysincos(int *A, int len, int opt){//0:sin
cpy(C, A, len); cpy(D, A, len);
rep(i, 0, len - 1) C[i] = 1ll * C[i] * I % mod;
rep(i, 0, len - 1) D[i] = 1ll * D[i] * (mod - I) % mod;
Polyexp(C, len); Polyexp(D, len);
if(opt) rep(i, 0, len - 1) A[i] = 1ll * (C[i] + D[i]) % mod * inv2 % mod;
else rep(i, 0, len - 1) A[i] = 1ll * (C[i] - D[i] + mod) % mod * inv2I % mod;
clr(C, len); clr(D, len);
}
inline void Polyasin(int *A, int len){
cpy(C, A, len); Polyder(A, len);
Polymul(C, C, len << 1, len);
rep(i, 0, len - 1) C[i] = mod - C[i];
C[0] = (C[0] + 1) % mod;
Polysqrt(C, len); Polyinv(C, len);
Polymul(A, C, len << 1, len);
Polyint(A, len - 1); clr(C, len);
}
inline void Polyatan(int *A, int len){
cpy(C, A, len); Polyder(A, len);
Polymul(C, C, len << 1, len); C[0] = (C[0] + 1) % mod;
Polyinv(C, len); Polymul(A, C, len << 1, len);
Polyint(A, len - 1); clr(C, len);
}
inline void mian(){
}
int main(){ int qwq = 1; while(qwq--) mian(); return 0; }
```
哦对了如果有锅请 D 死这个彩笔（