一直想写个好点的多项式模板，最近终于想清楚了怎么写，于是就写了一个！代码在本文最后。
众所周知，常见的多项式模板经常有这样两个问题：速度很慢、用起来很麻烦。
速度问题是老生常谈的。NTT我们可以找一个好的板子对着抄。形式幂级数运算我们可以采用 https://negiizhao.blog.uoj.ac/blog/4671 中的优化。在线卷积我们可以使用多叉降低复杂度，循环卷积和小范围暴力降低常数。那么本文考虑的主要问题是... 如何让你的模板封装得阳间一些？
我随机选取了若干份uoj上相关题目的AC代码：
一个字，惨。
我们先考虑形式幂级数和多项式的部分。这部分我的主要做法是，将每个多项式/形式幂级数记录精确度，即记录 $\bmod x^n$ 中的 $n$，在运算时保持该精确度不变。在牛顿迭代解 $G(f)=0$ 时，我们可以使用两个 lambda 传入 $G(f)$ 和 $G'(f)$，lambda 保持 $f$ 的精确度不变即可。我的模板中具体对应的是 shrink_len 属性，-1 表示为多项式，否则为精确次幂等于该值的集合幂级数。使用这个思路实现各运算即可。
以下各题均省略推导过程，代码均省略模板部分，模数均为 $998244353$。
loj150 挑战多项式
给定 $n$ 次多项式 $F(x)$，求 $G(x)$ 满足 $\displaystyle G(x) \equiv \left({\left({1+\ln\left({2+F(x)-F(0)-{\exp\left({\int_0^x\frac{1}{\sqrt{F(t)}}\textrm{d}t}\right)}}\right)}\right)^k}\right)^\prime \pmod {x^n}$。$n\le 10^5$
int n,m,f[123456];
int main()
{
scanf("%d%d",&n,&m);
default_shrink=++n;
for(int i=0;i<n;++i) scanf("%d",f+i);
poly p(vector<int>(f,f+n));
p=p-gexp(gint(ginv(gsqrt(p,mod_sqrt(f[0],MOD)))));
p=gcorner(gln(gcorner(p,{1})),{1});
gde(gexp(mi(m)*gln(p))).print_len(n-1,'\n');
}Quite easily done! 跑了 sum 4269ms/max 228ms，在写作本文时排在ranklist第一页。
luogu6112 直接自然溢出啥事没有 加强版 (30%)
求出多项式 $F(x)$ 使得 $\left(x^{7}+x^{6}+x^{5}-2 x^{4}+x^{2}\right) F(x)^{2}+\left(x^{5}-x^{4}-2 x^{3}+2 x^{2}+x-1\right) F(x)+\left(x^{4}-2 x^{2}+1\right)\equiv 0 \pmod {x^n}$。$n\le 10^5$
int n;
int main()
{
cin>>n;
poly
p="x^7+x^6+x^5-2x^4+x^2"_p,
q="x^5-x^4-2x^3+2x^2+x-1"_p,
r="x^4-2x^2+1"_p,
a=gnewton(
[&](poly g) {
return (g*p+q)*g+r;
},
[&](poly g) {
return 2*g*p+q;
},
1,n+1);
cout<<a.get(n)<<"\n";
}C++11就是好。
uoj50 链式法则
求出多项式 $F(x)$ 使得 $F'(x) \equiv \frac{1}{2}A(x)F^2(x) + 1 \pmod {x^n}$。$n\le 200000$
模板里咋能没有一阶微分方程呢。
int n; poly a(-1);
char str[288888];
int main()
{
scanf("%d%s",&n,str);
a.reserve(n+1);
for(int i=0;i<n;++i)
if(str[i]=='1') a[i]=rfac[i];
auto g=gnewton_d(
[&](poly x) {
x=mi((MOD+1)/2)*x*x*a;
++x[0]; return x;
},
[&](poly x) {
return x*a;
},0,n+1);
for(int i=1;i<=n;++i) {
mi ans=g.get(i)*fac[i];
printf("%d\n",(int)ans);
}
}跑了 sum 2851ms/max 1464ms，在写作本文时（可以）排在ranklist第五页。
loj6684 有根无标号「奇树」计数
求出多项式 $F(x)$ 使得 $F(x) \equiv x\text{MSet}(\text{MSet}(F(x))-1) \pmod {x^n}$（$\text{MSet}$ 的定义可参见 此处）。$n\le 100000$
这里我们进行牛顿迭代，注意到 $\text{MSet} (f(z))=\exp\left(\sum_{k\ge 1}f(z^k)/k\right)$，而倍增时 $\exp\left(\sum_{k\ge 2}f(z^k)/k\right)$ 有足够的精确度，因此我们可以将该部分视为一个常多项式，认为 $\text{MSet} (f(z))=\exp f(z)~\underbrace{\exp\left(\sum_{k\ge 2}f(z^k)/k\right)}_{\text{常多项式}}$。
由于模板中显然没有提供计算 $\sum_{k\ge 2}f(z^k)/k$ 的接口，我们需要手(kao)写(bei)。
poly MSet_(poly p,int st) {
p.fit_shrink();
assert(p.get(0)==0);
poly q(p.shrink_len);
q.fit_shrink();
for(int i=st;i<p.size();++i) {
mi iv=rfac[i]*fac[i-1];
for(int j=1;i*j<p.size();++j)
q[i*j]=q[i*j]+p[j]*iv;
}
return q;
}
int n;
int main()
{
scanf("%d",&n);
poly o=gnewton(
[&](poly u) {
return gshl(MSet(gcorner(MSet(u),{0})),1)-u;
},
[&](poly u) {
poly P=MSet_(u,2),
z=gcorner(gexp(P+u),{0}),
Q=MSet_(z,2);
//x*exp(Pexp(F)-1)Q-F=0
return gcorner(gshl(gexp(z+u+P+Q),1),{-1});
},
0,n+1);
for(int i=1;i<=n;++i)
printf("%d\n",(int)o.get(i));
}在经过一些简单的常数优化（注意到 $G$ 和 $G'$ 都需要求出 $\text{MSet}$，可以进行记忆化）后，跑了 max 267ms，在写作本文时（可以）排在ranklist第一（忽略一位打表的同学）。
loj6538 烷基计数 加强版 加强版
求出多项式 $F(x)$ 使得 $F(z)\equiv z \frac{F(z)^{3}+3 F(z) F\left(z^{2}\right)+2 F\left(z^{3}\right)}{6}+1\pmod {x^n}$。$n\le 100000$
类似上题进行牛顿迭代。
int n;
int main() {
cin>>n;
cout<<gnewton(
[&](const poly& s) {
poly t=s;
t=inv(6)*(t*(t*t+3*gamp(t,2))+2*gamp(t,3));
t.insert(0); t=t+1-s; return t;
},
[&](poly t) {
t=inv(2)*(t*t+gamp(t,2));
t.insert(0); t=t-1; return t;
},
1,n+1).get(n)<<"\n";
}跑了 sum 298ms/max 98ms，在写作本文时排在ranklist第一页。
此外，模板中还实现了快速线性递推、快速多点求值插值、幂和、简单函数复合逆等算法。
2021年了，牛顿法等朴素迭代方法已经不足以满足我们。接下来我们来考虑在线卷积算法。
常见(wo'jian'guo'de)的半在线卷积算法实现方法为，传入 $i$，更新到 $f[i]$ 位置时调用 $relax(i)$，但这种方法实现扩展性较差。
于是我们可以考虑把序列真的作为一个流来处理，主要定义如下：
struct ocpoly {
function<mi(int)> get_handle;
vector<int> vis; vector<mi> val;
mi get(int x) {
if((int)vis.size()>x&&vis[x]) return val[x];
if((int)vis.size()<=x)
vis.resize(x+1),val.resize(x+1);
val[x]=get_handle(x); vis[x]=1; return val[x];
}
poly await(int n) {
poly s(-1);
for(int i=0;i<n;++i)
s[i]=get(i);
return s;
}
void copy(ocpoly*b) {
get_handle=[=](int c) {
return b->get(c);
};
}
ocpoly() {}
ocpoly(ocpoly const&)=delete;
ocpoly& operator = (ocpoly const&)=delete;
}即我们对外的接口为 get 函数，该函数实现了对lambda get_handle 返回值的记忆化（我们希望 $\text{get_handle}(i)$ 返回 $x^i$ 位置上的系数）。这种写法的好处在于扩展性较强，我们只需要改变lambda就可以派生出各种流。例如我们可以定义在一个流上进行积分：
struct ocint: public ocpoly {
ocint(ocpoly*p,mi c=0) {
get_handle=[=](int u) {
if(u==0) return c;
return p->get(u-1)*rfac[u]*fac[u-1];
};
}
}我们可以定义更多的组合子，例如如果我们定义 $\text{ocde}$ 为流上的求导，$\text{ocquo}(A,B)$ 为 $A(x)B(x)^{-1}$ 形成的形式幂级数，我们可以组合成流上的 $\ln$：
struct ocln: public ocpoly {
ocln(ocpoly*a) {
copy(new ocint(new ocquo(new ocde(a),a)));
}
};（在内存管理的角度上这种写法不是很优美，但是懒得用智能指针）
当然，实现最困难的部分在于全在线多项式卷积 $\text{ocmul}$。首先全在线转半在线只需要倍增最大长度，即我们对于当前考虑的位置 $i$，我们保证所有 $i=a+b$ 有 $\min(a,b)\le u$，即要求 $2(u+1)>i$，并在不满足要求时修改 $u$。这样我们就可以将在线卷积转换为 $A[0..u],B[u+1..]$ 和 $B[0..u],A[u+1..]$ 的半在线卷积。
为了实现非递归的 $4$-叉 半在线卷积，我们进行形如二项式分组的过程（也可以理解为记录递归栈），对于每一组我们记录 DFT 后的点值，每次维护分组并计算贡献。在小范围上我们进行循环展开的暴力。
这里DFT的总长是 $O(n\log n)$ 级别的，因此需要进行内存回收。这里的内存管理需要格外小心。
利用 ocmul 全在线地写完 $\exp$, 根号, 求逆, 快速幂... 大功告成！
举个例子，实现快速幂 $F^k$：注意到 $(F^k)'F=kF^kF'$，在线地计算 $\int kF^kF'F^{-1}$ 即可（$F^k$ 即本身）。
如果你和我一样认为形如 copy(new ocint(new ocquo(new ocde( 的一大串不好看，我们可以使用一个包裹类包起来：
struct pipeline {
ocpoly*p;
pipeline() {p=new ocpoly();}
pipeline(ocpoly *q) {assert(q);p=q;}
pipeline(poly s) {p=new ocfixed(s);}
mi get(int n) {return p->get(n);}
poly await(int n) {return p->await(n);}
void set(pipeline q) {p->copy(q.p);}
};
pipeline operator + (pipeline a,pipeline b)
{return pipeline(new ocadd(a.p,b.p));}这样就可以把这个包裹类 pipeline 当做对象愉快地进行操作了！我们甚至可以保留与多项式部分相同的接口。
loj150 挑战多项式
没错，我们可以全在线地实现本题！代码也长得差不多。
int n,m,f[123456];
int main()
{
scanf("%d%d",&n,&m); ++n;
for(int i=0;i<n;++i) scanf("%d",f+i);
pipeline p(vector<int>(f,f+n));
p=p-gexp(gint(ginv(gsqrt(p,mod_sqrt(f[0],MOD)))));
p=gcorner(gln(gcorner(p,{1})),{1});
gde(gexp(gln(p)*m)).await(n).print_len(n-1,'\n');
}跑了 sum 8958ms/max 478ms，也就慢了一倍左右。
uoj50 链式法则
$F(x) \equiv \int\left(\frac{1}{2}A(x)F^2(x) + 1 \right)dx$，直接照抄式子！
int n; poly a(-1);
char str[288888];
int main()
{
scanf("%d%s",&n,str);
a.reserve(n+1);
for(int i=0;i<n;++i)
if(str[i]=='1') a[i]=rfac[i];
pipeline o;
o.set(gint(a*o*o/2+1_p)); //!
poly g=o.await(n+1);
for(int i=1;i<=n;++i) {
mi ans=g.get(i)*fac[i];
printf("%d\n",(int)ans);
}
}主要就一行代码，sum 1042ms/max 432ms，（在写作本文时）喜提ranklist第三。
loj6684 有根无标号「奇树」计数
$F(x) \equiv x\text{MSet}(\text{MSet}(F(x))-1)$，直接照抄。
int n;
int main() {
scanf("%d",&n);
pipeline p;
p.set(gshl(MSet(MSet(p)-1_p),1));
poly o=p.await(n+1);
for(int i=1;i<=n;++i)
printf("%d\n",(int)o.get(i));
}同样是一行代码，跑了 max 200ms，在写作本文时喜提ranklist第一（忽略一位打表的同学）。
loj6538 烷基计数 加强版 加强版
也是照抄一行式子。
int n;
int main() {
scanf("%d",&n);
pipeline T;
T.set(gcorner(gshl((gamp(T,3)*2+T*(gamp(T,2)*3+T*T))/6,1),{1}));
poly p=T.await(n+1);
printf("%d\n",p.get(n));
}跑了 sum 582ms/max 167ms，在写作本文时（可以）排在ranklist第六页（虽然这次有点惨但好歹能过）。
我们也可以方便地实现更为复杂的全在线过程，例如 $F\equiv GH(1+x)+3x^2$，$G\equiv FH(1+x^2)+5x$，$H\equiv FG(1-x^3)+3x^4$。
int main() {
pipeline f,g,h;
f.set(gcorner(g*h*"1+x"_p+"3x^2"_p,{0}));
g.set(gcorner(f*h*"1+x^2"_p+"5x"_p,{0}));
h.set(gcorner(f*g*"1-x^3"_p+"3x^4"_p,{0}));
poly F=f.await(100000);
poly G=g.await(100000);
poly H=h.await(100000);
F.dump('\n');G.dump('\n');H.dump('\n');
}可以看到全在线方法写起来比较优美，适用性广泛，效率也比较快，是我们熟悉的迭代方法的有力补充。
最后我们给出以上模板的实现，如果有更好的实现 / 更好的函数类型名 / 发现bug（这个比较重要）欢迎在评论区讨论。由于代码较长，建议自行截取需要的部分进行使用。
当然，发这份代码的本意并不是希望大家做题的时候上来就贴这份板子，主要还是希望给大家提供写板子的思路，以及普及一下在线卷积的作用？
代码更新：2021.08.07 (paste, gist) 修复了一处内存泄漏；修改了一些代码风格；修改了幂和的实现；换了个快点的ntt、细节上的常数优化（减少bitrev的调用、优化ocmul的小范围暴力）、加入了半在线卷积；加入了多项式欧几里得算法和有理分式重建
鄂公网安备 42010202000505 号