一个服务器怎么做两个网站,网站建设胶州家园,淘宝采用了哪些网络营销方式,深圳比较好的设计网站公司多项式工业警告#xff01;#xff01;#xff01;
点击看题意
思路来自 这位大佬 。
为什么这么好的题解没人评论。
Part 1
前置知识#xff1a;拉格朗日反演#xff08;多项式复合#xff09;#xff0c;分式域#xff08;引入负整数次项#xff09;。
条件
点击看题意
思路来自 这位大佬 。
为什么这么好的题解没人评论。
Part 1
前置知识拉格朗日反演多项式复合分式域引入负整数次项。
条件有两个幂级数 F ( x ) , G ( x ) F(x),G(x) F(x),G(x)有 G ( F ( x ) ) x G(F(x))x G(F(x))x即 F , G F,G F,G互为复合逆。 F , G F,G F,G应常系数为 0 0 0且 [ x 1 ] [x^1] [x1]系数非 0 0 0。
首先引入分式域。对于无法求逆的整式 F ( x ) F(x) F(x)找出 G ( x ) F ( x ) / x k G(x)F(x)/x^k G(x)F(x)/xk则 1 F ( x ) x − k 1 G ( x ) \frac{1}{F(x)}x^{-k}\frac{1}{G(x)} F(x)1x−kG(x)1。这也说明了分式域下存在负指数这通常在对整式求逆时出现。注意此时乘法卷积仍然是良定义。
引理默认 F ( x ) F(x) F(x)满足上述条件 [ x − 1 ] F ′ ( x ) F ( x ) k [ k − 1 ] [x^{-1}]F(x)F(x)^k[k-1] [x−1]F′(x)F(x)k[k−1]
证明当 k ≠ − 1 k\ne -1 k−1时左式可以看作 ( 1 k 1 F ( x ) k 1 ) ′ (\frac{1}{k1}F(x)^{k1}) (k11F(x)k1)′而求导不可能产生 [ x − 1 ] [x^{-1}] [x−1]项 ln ( x ) \ln (x) ln(x)是例外但是在 x 0 x0 x0处无定义所以不合法当 k − 1 k-1 k−1时可以验证答案就是 1 1 1。
扩展拉格朗日反演 [ x n ] H ( G ( x ) ) 1 n [ x n − 1 ] H ′ ( x ) ( x F ( x ) ) n [x^n]H(G(x))\frac{1}{n}[x^{n-1}]H(x)\left(\frac{x}{F(x)}\right)^n [xn]H(G(x))n1[xn−1]H′(x)(F(x)x)n
另类扩展拉格朗日反演 [ x n ] H ( G ( x ) ) [ x n ] H ( x ) ( x F ( x ) ) n 1 F ′ ( x ) [x^n]H(G(x))[x^n]H(x)\left(\frac{x}{F(x)}\right)^{n1}F(x) [xn]H(G(x))[xn]H(x)(F(x)x)n1F′(x)
懒得抄了自己看command_block的博客吧
通常来讲 H ( x ) H(x) H(x)是自己构造的。求复合逆没有比较好的方法一般要根据题目特殊性质来。一般来讲根据 H ( x ) H(x) H(x)和 F ( x ) F(x) F(x)谁的导函数比较简单来选取公式并且显然我们也可以看出当 n 0 n0 n0时只能选后面那一种公式。
比较经典的应用是有标号有根树计数。
Part 2
咕了。自己看大佬写的题解吧。感觉肯定比我写得好。
代码
//我还真写了居然能过。
