new-blog

发表于 2021-03-07 | 分类于 Others |

这个博客以后就不更了~

欢迎来新的博客玩~

HNOI2019 白兔之舞

发表于 2019-07-09 | 分类于题解 |

题目大意

考虑现在有$n \times (L+1)$个点，每个点用一个坐标$(x,y)$表示。（$x \in [0,L],y \in [1,n]$）

一开始我们在$(0,x)$处，接下来每次可以跳若干步，从$(a,x)$跳到$(b,y)$（$a < b$）的方案数为$w[a][b]$，求在跳了$x$次后到达$(L,y)$的方案数，$x$满足$x \bmod d=k$，对于$k\in[0,t-1]$都输出一个答案。

给定$n,w[][],L,x,y,d,t$，答案对质数$P$取模，保证有在模$P$意义下的$d$次单位根。

题解

考虑若对$x$的限制是$x=L$，那么这个问题可以直接使用矩阵快速幂解决。

加上题目里都明示要用单位根反演了，那我们考虑用单位根反演来解决这个问题。

我们可以比较容易地想到这个多项式：

$f(x)=\left( \begin{bmatrix} 1 \ 0 \ 0 \\ 0 \ 1 \ 0 \\ 0 \ 0 \ 1 \end {bmatrix} + Wx \right)^L$

其中，$W$是一个矩阵，数值就是给定的w数组。

那么我们要求的东西就是这个：

$Ans_k=\sum_{i=0}^L [x \bmod k=t] [x^i]f(x) \qquad (for \ k \in[0,t-1])$

然后就可以用矩阵乘法求答案了！

我们考虑使用单位根反演。注意：为了处理不是$d$的整次幂的情况，我们可以直接乘上一个$x^{d-k}$。

$\begin{aligned} Ans_k &= \frac{1}{d} \sum_{i=0} ^{d-1} f(\omega_{d}^{i})(\omega_d^{i})^{d-k} \\ Ans_k &= \frac{1}{d} \sum_{i=0} ^{d-1} \omega_d^{-i\times k} \times f(\omega_{d}^{i}) \end{aligned}$

注意到：$i \times k= {i +k \choose 2} - {i \choose 2} - {k \choose 2}$。

代入可得

$\begin{aligned} Ans_k = \frac{1}{d} \sum_{i=0} ^{d-1} \omega_d^{ {k \choose 2} + {i \choose 2} - {i+k \choose 2} } \times f(\omega_{d}^{i}) \\ Ans_k = \frac{\omega_d^{ {k \choose 2} } }{d} \sum_{i=0} ^{d-1} \omega_d^{-{i+k \choose 2} } \times ( f(\omega_{d}^{i}) \times \omega_d^{ {i \choose 2} } ) \end{aligned}$

后面的用矩阵快速幂预处理。

差一定的卷积，请。

（要写任意模数卷积。）

代码请移步Github仓库。

[WC2019] 数树

发表于 2019-04-09 | 分类于题解 |

题目大意

题目的模型是有两棵$n$个点树，求$y^{|T 1 \cap T 2 |}$。（$T 1,T 2$分别是两棵树的边集。）

有三个部分，分别是：

给定两棵树求答案。
给定一棵树，然后求另一棵树是$n^{n-2}$种情况时的答案和。
只给一个$n$，求出两棵树在所有情况下的答案和（共$(n^{n-2})^2$种情况）

题解

我们一次考虑每个部分的做法。

给定两棵树

这部分只有普及组难度，随便用个$set$记一下就行了。

给定一棵树

我们不妨钦定一些$T 1$中的边为必选边，那么考虑$T 2$的方案数是多少（记为$F$）。

我们发现，加入一些必选边后，$T _ 2$被连成了若干连通块，我们假设形成了$m$个连通块（说明钦定了$n-m$条边）。

有一个很直观的想法就是这$m$个连通块的生成树个树（即$m^{m-2}$），但是显然算少了很多，因为两个连通块间的边的个数不是$1$，而是两个连通块大小的乘积。

那么我们不妨从$m^{m-2}$的本质来考虑这件事，众所周知，$m^{m-2}$的来源是$prufer$序列，那我们从$prufer$序列来审视这个问题。

我们发现，假设一个连通块的出现次数在$prufer$的出现次数为$d i$，它的大小为$siz i$，显然，它的度数为$d i+1$，它对答案有一个$siz i^{d _ i+1}$的乘法贡献。

我们现在不妨枚举每个连通块在$prufer$序列的出现次数并且枚举$prufer$序列，注意要处理多重集合的排列。

那么方案数很容易写出：

$F= m! \sum _ {\sum _ {i=1}^{m} d _ i=m-2} \prod _ {i=1}^{m} \frac{siz _ i^{d _ i+1}}{d _ i!}$

我们随手化简一下，可以得到

$F= \prod _ {i=1}^{m} siz _ i \times m! \sum _ {\sum _ {i=1}^{m} d _ i=m-2} \prod _ {i=1}^{m} \frac{siz _ i^{d _ i}}{d _ i!}$

我们接下来来考虑后面这一坨东西的组合意义，相当于我们先给每个连通块分配了一些位置，然后每个位置可以填$siz i$种数字。那么我们可以直接考虑每个位置能填的数字，显然种类数就是$\sum {i} siz _ i =n$，那么可以进一步化简得到最终形式。

$F = \prod _ {i=1} ^{m} siz _ i \times n^{m-2}$

也就是说，我们现在可以暴力枚举边集，然后计算答案

$Ans = \sum _ {E \subset T _ 1} y^{n-|E|} n^{n-|E|-2} \prod _ {i=1} ^{n-|E|-2} siz _ i\\ Ans = y^n n^{n-2} \sum _ {E \subset T _ 1} y^{-|E|} n^{-|E|} \prod _ {i=1} ^{n-|E|-2} siz _ i$

接下来，为方便起见，我们令$y=y^{-1}$，最后统一乘$y^n$。

写个暴力，然后发现这玩意并不对，我们冷静分析一下，发现我们钦定出来的边集只是两个边集的交的一个子集，而不是最终的交。

那么接下来有两种处理方法，容斥和组合恒等式，这里只介绍组合恒等式的处理方法。

我们发现，我们设最终的交集为$|S|$，若我们钦定的集合的大小为$k$，那么这种大小的连通块对$S$的贡献就是.${|S| \choose k} \times val$。

我们知道有组合恒等式$y^{k} = \sum \limits _ {i=0} ^{k} {k \choose i} (y-1) ^ i$。

那么如果我们将权值$val$设置为$y-1$，再进行刚才的做法，发现每个集合的贡献恰好是$y^k$。

于是我们得到了一个指数级的做法，枚举边集。我们接下来考虑将复杂度降到$poly(n)$。

一个很自然的想法就是用树形$dp$来优化上述过程，我们发现，一个点状态只和这个点所在的连通块大小有关。那么可以设$f _ {x,s}$为考虑完以$x$为根的子树后，$x$所在的连通块的大小为$s$。这样，我们在合并儿子时考虑下$x$到儿子的这条边选不选，并且乘上相应的系数（$1$或$y^{-1}n^{-1}$）进行转移即可，使用$siz$优化，复杂度为$\mathcal{O}(n^2)$。

这个做法的复杂度我们显然无法接受，考虑继续优化。

我们发现，$\prod{siz _ i}$的组合意义是从每个连通块分别选出一个点的方案数。那么我们可以这个组合意义设置新的$dp$状态。

我们设$f _ {x,0/1}$为考虑完$x$为根的子树，$x$所在连通块是否已经选点了的方案数，转移讨论一下就行了，注意每个点必须要选出一个点。复杂度$\mathcal{O}(n)$。

给定零棵树

这里我们继续沿用给定一棵树时的做法。

我们设$f(E)=\prod {i=1} ^{m} siz i \times n^{m-2}$，其中，$E$是一个边集，$m$表示将$E$中的边连接后形成的连通块个数，${siz}$是每个连通块的大小。

那么我们枚举一个边集$E$，且这个边集必须是某棵树的边集的子集，那么这个边集对答案的贡献是$f(E)^2 y^{|E|}$。

所以答案就是$\sum \limits _ {E} y^{|E|} f(E)^2 $。

我们不妨枚举$|E|$，我们设$g i=\sum \limits {|E|=i} f(E)$，答案可以进一步化简为$\sum \limits {i=0}^{n-1} y^i g i$。

那么我们接下来就要处理${g}$数组了。

由$f(E)$的计算式，我们不妨考虑枚举将$E$中的边连起来后每个连通块的大小${a}$，然后可以得到以下式子：

$g _ s = \sum _ {\sum _ {i=1}^{n-s}a _ i=n}\frac{n!}{(n-s)!} \prod _ {i=1}^{n-s} { \frac{a _ i^{a _ i-2}}{a _ i!}} ( \prod _ {i=1} ^{n-s} a _ i \times n^{n-s-2} )^2$

解释下这个式子是怎么来的：

首先，我们需要让这些连通块内部都是连通的，就是$\prod \limits {i=1}^{n-s} a i^{a i-2}$，然后，我们将$n$个点划分到这些集合中，就是多重集合的排列，体现在式子中就是$n! \prod \limits {i=1}^{n-s} \frac{1}{a _ 1!}$，最后，这些连通块其实是无序的，但是我们在枚举大小的时候是作为有序的做的，所以我们要除掉$(n-s)!$，最后那个平方项就是$f(E)^2$。

然后我们将这个式子带到答案的式子中，并进行一番化简：

$\begin{aligned} Ans &= \sum _ {s=0}^{n-1} \sum _ {\sum _ {i=1}^{n-s}a _ i=n}\frac{n!}{(n-s)!} \prod _ {i=1}^{n-s} { \frac{a _ i^{a _ i-2}}{a _ i!}} ( \prod _ {i=1} ^{n-s} a _ i \times n^{n-s-2} )^2 \\ Ans &= \sum _ {s=0}^{n-1} n!\frac{n^{2 * (n-2-s)}}{(n-s)!} \sum _ {\sum _ {i=1}^{n-s} a _ i = n} \prod _ {i=1}^{n-s} {\frac{a _ i^{a _ i}}{a _ i!}}\\ Ans &= n! \sum _ {s=0}^{n-1} y^s \frac{n^{2 * (n-2-s)}}{(n-s)!} \sum _ {\sum _ {i=1}^{n-s} a _ i = n} \prod _ {i=1} ^{n-s} { \frac{a _ i^{a _ i}}{a _ i!}} \\ Ans &= n! \sum _ {s=1}^{n} y^{(n-s)} \frac{n^{2 * (s-2)}}{s!} \sum _ {\sum _ {i=1}^{s} a _ i = n} \prod _ {i=1} ^{n-s} { \frac{a _ i^{a _ i}}{a _ i!}} \\ Ans &= \frac{n!y^n}{n^4} \sum _ {s=1}^{n} y^{-s} \frac{n^{2 * s}}{s!} \sum _ {\sum _ {i=1}^{s} a _ i = n} \prod _ {i=1} ^{n-s} { \frac{a _ i^{a _ i}}{a _ i!}} \end{aligned}$

注意，在第四个式子中，我用将$s$替换为了$n-s$。

然后我们发现第二个求和号的那个限制很难搞，但观察一下可以发现其实是个$\bf EGF$的形式，我们用$\bf EGF$来替换第二个求和号部分，并继续化简：

$\begin{aligned} Ans &= \frac{n!y^n}{n^4} \sum _ {s=1}^{n} y^{-s} \frac{n^{2*s}}{s!} [x^n] \left( {\sum _ {j \geqslant 1} \frac{j^{j}}{j!}} x^j \right) ^ s\\ Ans &= \frac{n!y^n}{n^4} [x^n] \sum _ {s=1}^{n} \frac{\left( {\frac{n^2}{y} \sum _ {j \geqslant 1} \frac{j^{j}}{j!}} x^j \right) ^ s}{s!}\\ Ans &= \frac{n!y^n}{n^4} [x^n] e^{\left( {\frac{n^2}{y} \sum _ {j \geqslant 1} \frac{j^{j}}{j!}} x^j \right)} \end{aligned}$

然后写个多项式$\bf Exp$就做完了。

复杂度：$\mathcal{O}(n \log n)$

代码

[CodeForces 98E] Help Shrek and Donkey

发表于 2019-02-21 | 分类于题解 |

题目大意

有两个人在玩一个游戏，规则如下：

每个人的手上有一些牌，桌子上有一张牌，每个人只能看到自己手上的牌。（桌子上的看不到）
每张牌都不一样。
两个人轮流进行如下两个操作之一：
- 猜桌子上的那张牌是什么，若猜对了，即获得胜利，否则算输掉比赛。
- 询问对方手中有没有一张牌，对方必须如实回答。

现在假设两个人都会执行最优策略，给定先后手的牌数$n,m$，询问两个人的胜率。

$n,m \leqslant 1000$

分析

不难发现，一个人若是进行询问操作，则有两种问法：

询问自己手上没有的牌。（我们记这种询问为诚实的询问）
询问自己手上有的牌。（我们记这种询问为欺骗的询问）

因为一个比较显然的思路是每次询问是问自己手上没有的牌（这样才能获得更多的信息）

然而我没也可以询问自己手上有的牌来误导对方自己手上没有这张牌，然后对方也没有这张牌的话就会认为桌子上是这张牌并猜是这张牌，然后他就输了。

然后对方也可以猜我这次的询问是不是诚实的询问（我们记为是否相信）。

题解

我们设$f(n,m)$为先手有$n$张牌，后手有$m$张牌时先手的胜率。

从刚才的分析中我们可以根据询问的诚实与否和是否相信来分为4种情况。

情况的具体分析

1. 先手进行诚实询问，后手相信这次询问。

那么会有以下两种情况：

$\frac{1}{m+1}$的概率猜到桌子上的牌，那么后手获胜（先手已经进行了操作，而后手已经知道了问的那张牌自己没有同时对方也没有，也就是桌子上的牌），对$f(n,m)$的贡献为$0$。
$\frac{m}{m+1}$的概率猜到后手手上的牌，那么先手知道了后手有问的那张牌（相当于后手失去了一张牌），后手知道了先手没有问的那张牌（没有得到新的信息），对$f(n,m)$的贡献是$\frac{m}{m+1} \times (1-f(m-1,n))$。（因为接下来先后手互换）

2.先手进行诚实询问，后手不相信这次询问。

会出现以下两种情况：

$\frac{1}{m+1}$的概率猜到桌子上的牌，那么后手会认为这张桌子上的牌会在先手的手中，也就是后手必败，对$f(n,m)$的贡献是$\frac{1}{m+1}$。
$\frac{m}{m+1}$的概率猜到后手手上的牌，那么后手肯定会相信这次询问，那么对答案的贡献就和上面一样了，即为$\frac{m}{m+1} \times (1-f(m-1,n))$。

3.先手进行欺骗询问，后手相信这次询问。

那么后手就中招了，自己手上没有那张牌，且认为先手手上也没有问的那张牌，那么就会认为那张牌就是桌子上的牌，这样先手就会必胜，对$f(n,m)$的贡献是$1$。

4.先手进行欺骗询问，后手不相信这次询问。

那么后手就会多知道先手手的一张牌（相当于先手失去了一张牌），对$f(n,m)$的贡献是$1-f(m,n-1)$。

做法

不难发现，这是一种混合策略的博弈游戏，就需要纳什均衡的那一套理论。

我们不妨假设先手进行诚实询问的概率为$p$，则进行欺骗询问的概率就是$1-p$。

那么后手选相信时对答案的贡献就是$p \times \frac{m}{m+1} \times (1-f(m-1,n)) + (1-p) \times 1$。

后手选不相信时对答案的贡献就是$p \times (\frac{1}{m+1}+\frac{m}{m+1} \times (1-f(m-1,n))) +(1-p) \times 1-f(m,n-1)$。

根据纳什均衡的理论，先手的最优决策点就是纳什均衡点，就是无论后手如何选择，答案均不会比当前情况更差的那个$p$，在这里就是令上下式子相等的那个$p$，解下方程就行了。

最后我们再记忆化一下就可以做到$\mathcal{O}(nm)$了。

代码

#include<bits/stdc++.h>

using namespace std;

const int MAXN=1010;

bool vis[MAXN][MAXN];
long double f[MAXN][MAXN];

long double F(int n,int m)
{
	if(vis[n][m]) return f[n][m];
	vis[n][m]=1;
	if(!n) return f[n][m]=1.0/(m+1);
	if(!m) return f[n][m]=1;
	long double k1=1.0*m/(m+1)*(1-F(m-1,n))-1,k2=1.0*m/(m+1)*(1-F(m-1,n))+1.0/(m+1)+F(m,n-1)-1;
	long double x=(-F(m,n-1))/(k1-k2);
	return f[n][m]=x*(1.0*m/(m+1)*(1-F(m-1,n)))+1-x;
}

int main()
{
	int n,m;
	cin>>n>>m;
	long double Ans=F(n,m);
	cout<<fixed<<setprecision(15)<<Ans<<" "<<1-Ans<<endl;
}

多项式全家桶

发表于 2018-12-20 | 分类于学习笔记 |

　引言

众所周知，多项式在OI中是一项很实用的技能，现在将多项式的有关知识总结一下。

前置技能

认识汉字以及常用的基本词汇，如果此项有问题，请移步这里
基本数学知识（四则运算，多项式的概念等），如果此项有问题，请移步这里
一些高中数学知识和高数知识（泰勒展开等），如果此项有问题，请自行学习
FFT、NTT等多项式基本算法

符号及约定

若不做特殊说明，$n$代指多项式的长度（次数+1）
$[x^i]f(x)$表示多项式$f(x)$的$i$次项系数。
若不做特殊说明，本文的运算均在$998244353$或其他费马素数的剩余系下的意义进行。

多项式加减法

直接$\mathcal{O}(n)$。

多项式乘法

暴力卷积 $\mathcal{O}(n^2)$。

使用NTT可加速至$\mathcal{O}(n \log n)$

多项式求逆

首先，求逆必须要在$\bmod x^k$的意义下进行。

现在假设我们已知$n$次多项式$f(x)$，现在要求$g(x)$使得$ f(x) \times g(x) \equiv1 \pmod {x^{n+1}} $。

我们使用倍增算法。

假设已知$g_0(x)$使得$f(x) \times g_0(x) \equiv 1 \pmod{x^{\frac{n}{2}}}$，

现在要求$g(x)$使得$f(x) \times g(x) \equiv 1 \pmod{x^n}$。

$\begin{aligned} \because f(x) \times g_0(x) & \equiv 1 & \pmod{x^{\frac{n}{2}}} \\ f(x) \times g(x) & \equiv 1 & \pmod{x^{\frac{n}{2}}} \\ \therefore g(x)-g_0(x) & \equiv 0 & \pmod{x^{\frac{n}{2}}}\\ \text{两边平方，得到} (g(x)-g_0(x))^2 & \equiv 0 & \pmod{x^{n}}\\ g^2(x)-2g(x)g_0(x)+g_0^2(x) & \equiv 0 & \pmod{x^{n}}\\ \text{两边同乘f(x)，得到} g(x)-2g_0(x)+g_0^2(x) \times f(x) & \equiv 0 & \pmod{x^{n}}\\ g(x) & \equiv 2g_0(x)-g_0^2(x) \times f(x) & \pmod{x^{n}} \end{aligned}$

于是我们得到了$g(x) \equiv 2g_0(x)-g_0^2(x) \pmod{x^{n}}$，就可以倍增了。

倍增起点是$g(x)=1 \pmod{x}$，倍增终点是$k>n$，$k=2^i$，就是我们在倍增时候的那个次数。

复杂度：$T(n)=T(\frac{n}{2})+O(n \log n)$得到最终复杂度为$O(n \log n)$

多项式除法

多项式除法同样是在$\bmod x^k$的意义下进行的。

假设我们现在已知$n$次多项式$f(x)$和$m$次多项式$g(x)$，现在请求出多项式$h(x)$和$r(x)$，满足下列两个条件

$f(x) \equiv g(x) \times h(x) +r(x) \pmod{x^{n+1}}$
$h(x)$的次数为$n-m$，$r(x)$的次数小于$m$

我们来考虑一个操作：

另$g(x)=x^nf(\frac{1}{x})$，则不难发现，其实$g(x)$的系数就是将$f(x)$的系数翻转过来了。

我们设$\hat f(x)=x^n f(\frac{1}{x})$

那么我们不妨这样处理：

$\begin{aligned} f(x) & \equiv g(x) \times h(x) +r(x) & \pmod{x^{n+1}} \\ f(\frac{1}{x}) & \equiv g(\frac{1}{x}) \times h(\frac{1}{x}) +r(\frac{1}{x}) & \pmod{x^{n+1}} \\ x^nf(\frac{1}{x}) & \equiv x^n g(\frac{1}{x}) \times h(\frac{1}{x}) + x^nr(\frac{1}{x}) & \pmod{x^{n+1}} \\ x^nf(\frac{1}{x}) & \equiv x^m g(\frac{1}{x}) \times x^{n-m} h(\frac{1}{x}) + x^nr(\frac{1}{x}) & \pmod{x^{n+1}} \\ \hat f(x) & \equiv \hat g(x) \times \hat h(x) +x^{n-m+1} \hat r(x) & \pmod{x^{n+1}} \\ \text{接下来在} & \bmod x^{n-m+1}\text{的意义下进行} \\ \hat f(x) & \equiv \hat g(x) \times \hat h(x) & \pmod{x^{n-m+1}} \\ \hat h(x) & \equiv \hat f(x) \times \hat g^{-1}(x) & \pmod{x^{n-m+1}} \\ \end{aligned}$

于是我们就求出来了$h(x)$，那么显然有$r(x) \equiv f(x) - g(x) \times h(x)$

复杂度显然与多项式求逆一致。

多项式求导

$[x^i]f'(x)=(i+1) \times [x^{i+1}]f(x)$

$\mathcal{O}(n)$

多项式积分

$[x^i]\int f(x) = \frac{1}{i}[x^{i-1}]f(x)$

$\mathcal{O}(n)$

多项式牛顿迭代

在这个问题中，我们已知函数$f(x)$，现在要求函数$g(x)$，使得$f(g(x)) \equiv 0 \pmod{x^{n+1}}$。

我们考虑倍增，假设我们已经求出了$g_0(x)$使得$f( g_0(x) ) \equiv 0 \pmod{x^{\frac{n}{2}}}$

我们要求$g(x)$使得$f( g(x) ) \equiv 0 \pmod{x^{n}}$

我们在$g_0(x)$出泰勒展开，我们可以得到

$\begin{aligned} f(g(x)) & = f(g_0(x)) \\ & + f'(g_0(x)) (g(x)-g_0(x)) \\ & + \frac{f''(g_0(x))(g(x)-g_0(x))^2 }{2!}\\ & + \cdots \end{aligned}$

由于我们在$\bmod x^{n}$的意义下进行，并且$g(x)-g_0(x)$的只有前$\frac{n}{2}$项不为$0$，

所以从第三项开始的东西都被消去了。

于是得到

$\begin{aligned} f(g(x)) & \equiv f(g_0(x)) + f'(g_0(x)) (g(x)-g_0(x)) \pmod {x^n}\\ 0 & \equiv f(g_0(x)) + f'(g_0(x)) (g(x)-g_0(x)) \pmod {x^n}\\ g(x) & \equiv g_0(x) - \frac{f(g_0(x))}{f'(g_0(x))} \pmod {x^n}\\ \end{aligned}$

就可以了

多项式ln

多项式ln可以看成将多项式带入了麦克劳林级数中。

具体定义是：

$\ln (1 - A(z)) = -\sum_{i \geq 1} \frac{A^i(z)}{i}$

也就是说，我们在计算$\ln f(x)$时，必须满足$[x^0]f(x)=1$。

接下来考虑怎么做。

$\begin{aligned} g(x) & \equiv \ln(f(x)) \pmod {x^{n+1}} \\ g'(x) & \equiv \frac{f'(x)}{f(x)} \pmod {x^{n+1}} \end{aligned}$

最后再将$g$积分回去即可。

只需要多项式求逆+多项式求导/积分。

复杂度$O(n \log n)$

多项式exp

多项式exp可以看成将多项式带入了麦克劳林级数中。

具体定义是：

$\exp(A(z)) = e^{A(z)} = \sum_{i \geq 0} \frac{A^i(z)}{i!}$

设$g(x)=e^{f(x)}$，两边取对数，得到$\ln g(x)=f(x)$，进一步可得到$ln(g(x))-f(x)=0$

也就是说，我们现在有函数$h(x)=ln(x)-f(z)$，现在要求$g(x)$使得$h(g(x))=0$。

显然有$h’(x)=\frac{1}{x}$，也就是说$h’(g(x))=\frac{1}{g(x)}$。

根据牛顿迭代的理论，这东西显然是要倍增的，并且能够得到递推式

$\begin{aligned} g(x) & \equiv g_0(x) - \frac{h(g_0(x))}{h'(g_0(x))} & \pmod {x^n} \\ g(x) & \equiv g_0(x) - h(g_0(x)) \times g_0(x) & \pmod {x^n} \\ g(x) & \equiv g_0(x) \times (1 - h(g_0(x))) & \pmod {x^n} \\ \text{带入}&h(x)\text{的定义，得到} \\ g(x) & \equiv g_0(x) \times (1 - \ln (g_0(x)) + f(x)) & \pmod {x^n} \\ \end{aligned}$

于是就可以递推了。

复杂度$O(n \log n)$

所有代码均可以在这里找到

多项式开根

算法一：$\sqrt{f(x)}=e^{\frac{1}{2} \ln f(x)}$

算法二：牛顿迭代

我们现在要求$g(x)$使得$g^2(x)=f(x)$。

构造函数$h$满足$h(g(x))=g^2(x)-f(x)$，问题转化为了求$g(x)$满足$h(g(x))=0$。

假设我们已经得到了$\pmod {x^\frac{n}{2}}$时的答案$g_0(x)$

直接套用牛顿迭代的式子，我们可以得到

$\begin{aligned} g(x) & \equiv g_0(x) - \frac{f(g_0(x))}{f'(g_0(x))} \pmod {x^n} \\ g(x) & \equiv g_0(x) - \frac{g_0^2(x)-f(x)}{2g_0(x)} \pmod {x^n} \\ g(x) & \equiv \frac{g_0^2(x)+f(x)}{2g_0(x)} \pmod {x^n} \end{aligned}$

倍增的起点是$n=1$，一般来说，$f(x)$ 的常数项为1或0，否则需要计算二次剩余。

Zhang_RQ

In solitude, where we are least alone.

27 日志

8 分类

32 标签