成都网站建设推广在,寓意好的装饰公司名称,网站备案流程详解,杭州公司网站建设套餐前言
这里的全家桶目前只包括了ln,exp,sqrtln,exp,sqrtln,exp,sqrt。还有一些类似于带余数模#xff0c;快速幂之类用的比较少的有时间再更#xff0c;NTTNTTNTT这种前置知识这里不多说。
还有一些基本的导数和微积分内容要了解#xff0c;建议不懂的可以先去翻翻高二数学…前言
这里的全家桶目前只包括了ln,exp,sqrtln,exp,sqrtln,exp,sqrt。还有一些类似于带余数模快速幂之类用的比较少的有时间再更NTTNTTNTT这种前置知识这里不多说。
还有一些基本的导数和微积分内容要了解建议不懂的可以先去翻翻高二数学书。
之后多项式算法基本是一环扣一环的所以前面的看不懂对于后面的理解会造成很大影响。
本博客涉及内容偏浅 Tips
这里是一些我个人的模板书写习惯
习惯相关的问题默认将读入的nnn变为222的整数次幂形式目前为止这样的做法都不会影响正确性正确性相关的问题模板书写应满足使用的中间变量不重复如在求lnlnln和逆元时不应该使用重复的中间变量可能会导致信息丢失正确性相关的问题在每次进行任意操作前应保证在操作值域内不会有上次的信息参与要清零 参考资料
[command-block]NTT与多项式全家桶[CYJian]浅谈多项式[隔壁的张栩嘉]浅谈牛顿迭代法洛谷各模板题解 正题 文章目录前言Tips参考资料正题多项式求逆题目大意分析code多项式导数相关多项式求导多项式积分多项式复合泰勒公式牛顿迭代多项式复合零点多项式开根题目大意分析code多项式ln题目大意分析code多项式exp题目大意解题思路code多项式求逆
题目大意
给出一个多项式FFF求出一个GGG使得 F(x)∗G(x)≡1(modxn)F(x)*G(x)\equiv1(mod\ x^n)F(x)∗G(x)≡1(mod xn)
分析
利用经典的倍增思想假设我们已知多项式G′(x)G(x)G′(x)满足 F(x)G′(x)≡1(modxn2)F(x)G(x)\equiv1(mod\ x^{\frac{n}{2}})F(x)G′(x)≡1(mod x2n) 又有 F(x)G(x)≡1(modxn2)F(x)G(x)\equiv 1(mod\ x^{\frac{n}{2}})F(x)G(x)≡1(mod x2n) 就有了 F(x)(G(x)−G′(x))≡0(modxn2)⇒G(x)−G′(x)≡0(modxn2)F(x)(G(x)-G(x))\equiv 0(mod\ x^{\frac{n}{2}})\Rightarrow G(x)-G(x)\equiv 0(mod\ x^{\frac{n}{2}})F(x)(G(x)−G′(x))≡0(mod x2n)⇒G(x)−G′(x)≡0(mod x2n) 然后两边同时平方后面的模数同理也要平方 G(x)2−2G(x)G′(x)G′(x)2≡0(modxn)G(x)^2-2G(x)G(x)G(x)^2\equiv 0(mod\ x^n)G(x)2−2G(x)G′(x)G′(x)2≡0(mod xn) 再乘上一个F(x)F(x)F(x) F(x)G(x)2−2F(x)G(x)G′(x)F(x)G′(x)2≡0(modxn)F(x)G(x)^2-2F(x)G(x)G(x)F(x)G(x)^2\equiv 0(mod\ x^n)F(x)G(x)2−2F(x)G(x)G′(x)F(x)G′(x)2≡0(mod xn) 又因为F(x)G(x)≡1(modxn)F(x)G(x)\equiv 1(mod\ x^n)F(x)G(x)≡1(mod xn)所以就有 G(x)−2G′(x)F(x)G′(x)2≡0(modxn)⇒G(x)≡2G′(x)−F(x)G′(x)2(modxn)G(x)-2G(x)F(x)G(x)^2\equiv0(mod\ x^n)\Rightarrow G(x)\equiv 2G(x)-F(x)G(x)^2(mod\ x^n)G(x)−2G′(x)F(x)G′(x)2≡0(mod xn)⇒G(x)≡2G′(x)−F(x)G′(x)2(mod xn) 然后倍增就好了时间复杂度是类似于T(n)T(n2)nlognT(n)T(\frac{n}{2})n\log nT(n)T(2n)nlogn的形式所以是O(nlogn)O(n\log n)O(nlogn)的。
code
比较远古的代码所以码风有点不同
// luogu-judger-enable-o2
#includecstdio
#includealgorithm
#includecstring
#includecmath
#define ll long long
using namespace std;
const ll N1e6100,XJQ998244353,G3,Gi332748118;
const double Piacos(-1);
ll n,m,l,a[N2],b[N2],c[N2],r[N2];
ll power(ll x,ll b)
{ll ans1;while(b){if(b1) ansans*x%XJQ;xx*x%XJQ;b1;}return ans;
}
void ntt(ll *f,ll n,ll op)
{for(ll i0;in;i)if(ir[i])swap(f[i],f[r[i]]);for(ll p2;pn;p1){ll lenp1,tmppower(G,(XJQ-1)/p);for(ll k0;kn;kp){ll buf1;for(ll ik;iklen;i){ll ttbuf*f[leni]%XJQ;f[leni](f[i]-ttXJQ)%XJQ;f[i](f[i]tt)%XJQ;bufbuf*tmp%XJQ;}}}if(op1) return;int invpower(n,XJQ-2);reverse(f1,fn);for(int i0;in;i) f[i]f[i]*inv%XJQ;
}
void work(ll *a,ll *b,ll l)
{if(l1){b[0]power(a[0],XJQ-2);return;}work(a,b,(l1)1);ll cnt;for(cnt1;cnt(l1);cnt1);for(ll i1;icnt;i)r[i](r[i1]1)|((i1)?cnt1:0);for(ll i0;il;i) c[i]a[i];for(ll il;icnt;i) c[i]0;ntt(c,cnt,1);ntt(b,cnt,1);for(ll i0;icnt;i)b[i](2-b[i]*c[i]%XJQXJQ)%XJQ*b[i]%XJQ;ntt(b,cnt,-1);for(ll il;icnt;i) b[i]0;
}
int main()
{scanf(%lld,n);for(ll i0;in;i)scanf(%lld,a[i]);work(a,b,n);for(ll i0;in;i)printf(%lld ,b[i]);
}多项式导数相关
后面就要开始用到高二的知识了
多项式求导
后面定义f′ff′表示多项式fff的求导定义aif(x)[i]a_if(x)[i]aif(x)[i]那么有 f′(x)∑i0nai1(i1)xif(x)\sum_{i0}^na_{i1}(i1)x^if′(x)i0∑nai1(i1)xi 大体就是把所有位乘上iii再往前移动对导数有了解的话应该能理解这里就不给出推导了
多项式积分
同理定义aif(x)[i]a_if(x)[i]aif(x)[i]那fff的积分ggg就有 g(x)∑i0nai−1ixig(x)\sum_{i0}^n\frac{a_{i-1}}{i}x^ig(x)i0∑niai−1xi 和上面同理需要知道积分和求导是逆运算。
多项式复合
定义复合函数 F(G(x))∑i0F[i]G(x)iF(G(x))\sum_{i0}F[i]G(x)^iF(G(x))i0∑F[i]G(x)i 看上去没什么用之后再说
泰勒公式
这里开始就暂时不和多项式有多挂钩了。 f(x)limn→∞∑i0nf(n)(x0)i!(x−x0)iRn(x)f(x)\lim_{n\to \infty}\sum_{i0}^{n}\frac{f^{(n)}(x_0)}{i!}(x-x_0)^iR_n(x)f(x)n→∞limi0∑ni!f(n)(x0)(x−x0)iRn(x) 其中f(n)f^{(n)}f(n)表示fff的nnn阶求导Rn(x)R_n(x)Rn(x)是余项。 看上去没有什么用是牛迭的基础可以直接记牛迭的结论。 到时候会有泰勒公式的常用写法
牛顿迭代
这里就不用泰勒公式的推导了直接感性点理解快速过一下。 我们知道导数 f′(x)limΔx→0f(xΔx)−f(x)Δxf(x)\lim_{\Delta x\to0}\frac{f(x\Delta x)-f(x)}{\Delta x}f′(x)Δx→0limΔxf(xΔx)−f(x) 是可以理解为求某个函数在(x,f(x))(x,f(x))(x,f(x))处的切点而牛顿迭代正是利用这个原理求函数的近似零点可以先看一张生动的图来自维基百科。 就是先找一个点(x,f(x))(x,f(x))(x,f(x))然后求它在函数图像上的切线之后这条切线与xxx有交的位置x′xx′再带入xxx之后继续这个过程。
这个过程中求得的xxx在不断逼近原点这样就可以求出一个函数000点的近似解。
当然牛顿迭代显然并不是对所有函数都适用的但是对于我们需要解决的多项式问题来说足够了。
然后要上泰勒公式了 f(x)limn→∞∑i0nf(n)(x0)i!(x−x0)iRn(x)f(x)\lim_{n\to \infty}\sum_{i0}^{n}\frac{f^{(n)}(x_0)}{i!}(x-x_0)^iR_n(x)f(x)n→∞limi0∑ni!f(n)(x0)(x−x0)iRn(x) 这里只拿i1i1i1的情况来展开一下再定义一个ϕ(x)≈f(x)\phi(x)\approx f(x)ϕ(x)≈f(x)就是 f(x)≈ϕ(x)f′(x0)(x−x0)−f(x0)f(x)\approx \phi(x)f(x_0)(x-x_0)-f(x_0)f(x)≈ϕ(x)f′(x0)(x−x0)−f(x0) 然后如果求f(x)0f(x)0f(x)0就是近似的求ϕ(x)0\phi(x)0ϕ(x)0也就是 f′(x0)(x−x0)−f(x0)0f(x_0)(x-x_0)-f(x_0)0f′(x0)(x−x0)−f(x0)0 就有 xx0−f(x0)f′(x0)⇒xn1xn−f(xn)f′(xn)xx_0-\frac{f(x_0)}{f(x_0)}\Rightarrow x_{n1}x_{n}-\frac{f(x_n)}{f(x_n)}xx0−f′(x0)f(x0)⇒xn1xn−f′(xn)f(xn) 这个递推式子。
然后就可以快速近似求解了。
多项式复合零点
那么现在就是牛顿迭代的实战时间了题目是给出一个多项式G(x)G(x)G(x)要求求出一个f(x)f(x)f(x)使得G(f(x))≡0(modxn)G(f(x))\equiv 0(mod\ x^n)G(f(x))≡0(mod xn)。
拿多项式来泰勒展开推导或者直接用上面的牛迭结论。设ftf_tft满足G(ft)≡0(modx2t)G(f_t)\equiv 0(mod\ x^{2^t})G(ft)≡0(mod x2t)那么就有结论 ft≡ft−1−G(ft−1)G′(ft−1)(modx2t)f_t\equiv f_{t-1}-\frac{G(f_{t-1})}{G(f_{t-1})}(mod\ {x^{2^t}})ft≡ft−1−G′(ft−1)G(ft−1)(mod x2t) 这里还是推导一下吧先把fff给泰勒展开了这里换成了一个比较常用的写法 G(ft)≡G(ft−1)∑i1∞G(i)(ft−1)i!∗(ft−ft−1)i(modx2t)G(f_t)\equiv G(f_{t-1})\sum_{i1}^\infty\frac{G^{(i)}(f_{t-1})}{i!}*(f_t-f_{t-1})^i(mod\ x^{2^t})G(ft)≡G(ft−1)i1∑∞i!G(i)(ft−1)∗(ft−ft−1)i(mod x2t) 又因为G(ft−1)≡0(modx2t−1)G(f_{t-1})\equiv 0(mod\ x^{2^{t-1}})G(ft−1)≡0(mod x2t−1)和G(ft)≡0(modx2t)G(f_t)\equiv 0(mod\ x^{2^t})G(ft)≡0(mod x2t)。所以ft−ft−1f_t-f_{t-1}ft−ft−1的前2t−12^{t-1}2t−1项都是000那么(ft−ft−1)2(f_t-f_{t-1})^2(ft−ft−1)2的前2t2^t2t都是0也就当i≥2i\geq 2i≥2的时候后面的项都被模掉了所以式子就变得很简单了。 G(ft)≡G(ft−1)G′(ft−1)∗(ft−ft−1)(modx2t)G(f_t)\equiv G(f_{t-1})G(f_{t-1})*(f_t-f_{t-1})(mod\ x^{2^t})G(ft)≡G(ft−1)G′(ft−1)∗(ft−ft−1)(mod x2t) 把G(ft)0G(f_t)0G(ft)0带入就有 ftft−1−G(ft−1)G′(ft−1)(modx2t)f_tf_{t-1}-\frac{G(f_{t-1})}{G(f_{t-1})}(mod\ x^{2^t})ftft−1−G′(ft−1)G(ft−1)(mod x2t) 式子到这里就得根据具体情况化简了然后练练手 多项式开根
题目大意
给出一个多项式FFF求一个多项式GGG满足 G(x)2F(x)(modxn)G(x)^2F(x)(mod\ x^{n})G(x)2F(x)(mod xn)
分析
下面的GGG和上面的要求的GGG不同 如果我们求出一个多项式G(f)f2−F(x)G(f)f^2-F(x)G(f)f2−F(x)。如果G(f)≡0(modxn)G(f)\equiv 0(mod\ x^n)G(f)≡0(mod xn)的解就是f(x)≡F(x)(modxn)f(x)\equiv \sqrt{F(x)}(mod\ x^n)f(x)≡F(x)(mod xn)的解了。 之后直接代前面多项式零点求值的东西就有 ftft−1−G(ft−1)G′(ft−1)⇒ftft−1−ft−12−F(x)2ft−1f_tf_{t-1}-\frac{G(f_{t-1})}{G(f_{t-1})}\Rightarrow f_tf_{t-1}-\frac{f_{t-1}^2-F(x)}{2f_{t-1}}ftft−1−G′(ft−1)G(ft−1)⇒ftft−1−2ft−1ft−12−F(x) 嗯那个2ft−12f_{t-1}2ft−1是对GGG手动求导的结果 时间复杂度也是类T(n)T(n2)nlognT(n)T(\frac{n}{2})n\log nT(n)T(2n)nlogn的形式所以还是O(nlogn)O(n\log n)O(nlogn)
code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N6e510,P998244353,inv2(P1)/2;
ll n,a[N],b[N],r[N];
ll t1[N],t2[N],t3[N],t4[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
ll GetL(ll len){ll n1;while(nlen)n1;for(ll i0;in;i)r[i](r[i1]1)|((i1)?(n1):0);return n;
}
void NTT(ll *f,ll n,ll op){for(ll i0;in;i)if(ir[i])swap(f[i],f[r[i]]);for(ll p2;pn;p1){ll lenp1,tmppower(3,(P-1)/p);if(op-1)tmppower(tmp,P-2);for(ll k0;kn;kp){ll buf1;for(ll ik;iklen;i){ll ttf[ilen]*buf%P;f[ilen](f[i]-ttP)%P;f[i](f[i]tt)%P;bufbuf*tmp%P;}}}if(op-1){ll invnpower(n,P-2);for(ll i0;in;i)f[i]f[i]*invn%P;}return;
}
void GetInv(ll *f,ll *g,ll n){if(n1){g[0]power(f[0],P-2);return;}GetInv(f,g,n1);ll lGetL(n);for(ll i0;in;i)t1[i]f[i],t2[i]g[i];for(ll in;il;i)t1[i]t2[i]0;NTT(t1,l,1);NTT(t2,l,1);for(ll i0;il;i)t1[i]t1[i]*t2[i]%P*t2[i]%P;NTT(t1,l,-1);for(ll i0;in;i)g[i](2*g[i]-t1[i]P)%P;return;
}
void Sqrt(ll *f,ll *g,ll n){if(n1){g[0]1;return;}Sqrt(f,g,n1);ll lGetL(n1);for(ll i0;in;i)t3[i]f[i],t4[i]0;for(ll in;il;i)t3[i]t4[i]0;GetInv(g,t4,n);lGetL(n1);NTT(t3,l,1);NTT(t4,l,1);for(ll i0;il;i)t3[i]t3[i]*t4[i]%P;NTT(t3,l,-1);for(ll i0;in;i)g[i](g[i]t3[i])*inv2%P;return;
}
signed main()
{scanf(%lld,n);for(ll i0;in;i)scanf(%lld,a[i]);ll mGetL(n);Sqrt(a,b,m);for(ll i0;in;i)printf(%lld ,b[i]);return 0;
}多项式ln
题目大意
给出一个多项式FFF求一个多项式GGG满足 G(x)≡ln(F(x))(modxn)G(x)\equiv ln(F(x))(mod\ x^n)G(x)≡ln(F(x))(mod xn)
分析
这个题不用牛顿迭代对GGG求个导因为是复合函数直接展开 G′(x)≡ln′(F(x))∗F′(x)(modxn)⇒G′(x)≡F′(x)F(x)(modxn)G(x)\equiv ln(F(x))*F(x)(mod\ x^n)\Rightarrow G(x)\equiv\frac{F(x)}{F(x)}(mod\ x^n)G′(x)≡ln′(F(x))∗F′(x)(mod xn)⇒G′(x)≡F(x)F′(x)(mod xn) 这个推导要用到的有ln′(x)1xln(x)\frac{1}{x}ln′(x)x1。
就是算F′(x)F(x)\frac{F(x)}{F(x)}F(x)F′(x)再积分就好了 时间复杂度O(nlogn)O(n\log n)O(nlogn)
code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N4e510,P998244353;
ll n,r[N],f[N],g[N];
ll t1[N],t2[N],t3[N],t4[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
ll GetL(ll len){ll n1;while(nlen)n1;for(ll i0;in;i)r[i](r[i1]1)|((i1)?(n1):0);return n;
}
void NTT(ll *f,ll n,ll op){for(ll i0;in;i)if(ir[i])swap(f[i],f[r[i]]);for(ll p2;pn;p1){ll lenp1,tmppower(3,(P-1)/p);if(op-1)tmppower(tmp,P-2);for(ll k0;kn;kp){ll buf1;for(ll ik;iklen;i){ll ttf[ilen]*buf%P;f[ilen](f[i]-ttP)%P;f[i](f[i]tt)%P;bufbuf*tmp%P;}}}if(op-1){ll invnpower(n,P-2);for(ll i0;in;i)f[i]f[i]*invn%P;}return;
}
void GetInv(ll *f,ll *g,ll n){if(n1){g[0]power(f[0],P-2);return;}GetInv(f,g,n1);ll mGetL(n);for(ll i0;in;i)t1[i]f[i],t2[i]g[i];for(ll in;im;i)t1[i]t2[i]0;NTT(t1,m,1);NTT(t2,m,1);for(ll i0;im;i)t1[i]t1[i]*t2[i]%P*t2[i]%P;NTT(t1,m,-1);for(ll i0;in;i)g[i](2*g[i]-t1[i]P)%P;return;
}
void GetD(ll *f,ll *g,ll n){for(ll i0;in;i)g[i]f[i1]*(i1)%P;g[n-1]0;return;
}
void GetJ(ll *f,ll *g,ll n){for(ll i1;in;i)g[i]f[i-1]*power(i,P-2)%P;g[0]0;return;
}
void GetLn(ll *f,ll *g,ll n){nGetL(n);GetD(f,t3,n);GetInv(f,t4,n);nGetL(n);NTT(t3,n,1);NTT(t4,n,1);for(ll i0;in;i)t3[i]t3[i]*t4[i]%P;NTT(t3,n,-1);GetJ(t3,g,n);return;
}
signed main()
{scanf(%lld,n);for(ll i0;in;i)scanf(%lld,f[i]);GetLn(f,g,n);for(ll i0;in;i)printf(%lld ,g[i]);return 0;
}多项式exp
题目大意
给出多项式FFF求一个多项式GGG满足 G(x)≡eF(x)(modxn)G(x)\equiv e^{F(x)}(mod\ x^n)G(x)≡eF(x)(mod xn)
解题思路
这个应该是最麻烦的了和开根一样的思路 定义一个复合函数G(f)ln(f)−F(x)G(f)ln(f)-F(x)G(f)ln(f)−F(x)那么当G(f)0G(f)0G(f)0的解就是答案了。 然后同理直接上倍增加泰勒展开 ft≡ft−1−G(ft−1)G′(ft−1)(modx2t)⇒ft≡ft−1−(ln(ft−1)−F(x))∗ft−1(modx2t)f_t\equiv f_{t-1}-\frac{G(f_{t-1})}{G(f_{t-1})}(mod\ x^{2^t})\Rightarrow f_t\equiv f_{t-1}-(ln(f_{t-1})-F(x))*f_{t-1}(mod\ x^{2^t})ft≡ft−1−G′(ft−1)G(ft−1)(mod x2t)⇒ft≡ft−1−(ln(ft−1)−F(x))∗ft−1(mod x2t) 然后时间复杂度依旧是T(n)T(n2)nlognT(n)T(\frac{n}{2})n\log nT(n)T(2n)nlogn所以还是O(nlogn)O(n\log n)O(nlogn)的
然后上个lnlnln和求逆就好了 code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N8e510,P998244353;
ll n,m,r[N],a[N],b[N];
ll t1[N],t2[N],t3[N],t4[N],t5[N],t6[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
void GetL(ll len){n1;while(nlen)n1;for(ll i0;in;i)r[i](r[i1]1)|((i1)?(n1):0);return;
}
void NTT(ll *f,ll op){for(ll i0;in;i)if(ir[i])swap(f[i],f[r[i]]);for(ll p2;pn;p1){ll lenp1,tmppower(3,(P-1)/p);if(op-1)tmppower(tmp,P-2);for(ll k0;kn;kp){ll buf1;for(ll ik;iklen;i){ll ttf[ilen]*buf%P;f[ilen](f[i]-ttP)%P;f[i](f[i]tt)%P;bufbuf*tmp%P;}}}if(op-1){ll invnpower(n,P-2);for(ll i0;in;i)f[i]f[i]*invn%P;}return;
}
void GetInv(ll *f,ll *g,ll m){if(m1){g[0]power(f[0],P-2);return;}GetInv(f,g,m1);GetL(m);for(ll i0;im;i)t1[i]f[i],t2[i]g[i];for(ll im;in;i)t1[i]t2[i]0;NTT(t1,1);NTT(t2,1);for(ll i0;in;i)t1[i]t1[i]*t2[i]%P*t2[i]%P;NTT(t1,-1);for(ll i0;im;i)g[i](2*g[i]-t1[i]P)%P;return;
}
void GetD(ll *f,ll *g,ll n){for(ll i0;in-1;i)g[i]f[i1]*(i1)%P;g[n-1]0;return;
}
void GetJ(ll *f,ll *g,ll n){for(ll i1;in;i)g[i]f[i-1]*power(i,P-2)%P;g[0]0;return;
}
void GetLn(ll *f,ll *g,ll m){GetL(m);GetD(f,t3,n);GetInv(f,t4,n);GetL(m);GetL(n);NTT(t3,1);NTT(t4,1);for(ll i0;in;i)t3[i]t3[i]*t4[i]%P;NTT(t3,-1);GetJ(t3,g,n);for(int i0;in;i)t3[i]t4[i]0;return;
}
void GetExp(ll *f,ll *g,ll m){if(m1){g[0]1;return;}GetExp(f,g,m1);GetLn(g,t5,m);GetL(m);for(ll i0;im;i)t6[i]f[i];for(ll im;in;i)t5[i]t6[i]0;NTT(t5,1);NTT(t6,1);NTT(g,1);for(ll i0;in;i)g[i]g[i]*(1-t5[i]t6[i]P)%P;NTT(g,-1);for(ll im;in;i)g[i]0;return;
}
signed main()
{scanf(%lld,m);for(ll i0;im;i)scanf(%lld,a[i]);GetL(m);GetExp(a,b,n);for(ll i0;im;i)printf(%lld ,b[i]);return 0;
}
