开始跳楼了
多项式部分简介
定义简介
一个以$x$为变量的定义在代数域$F$上,将函数$A(x)$表示为:
其中我们称$a_0,a_1,\dots,a_{n-1}$为系数,如果一个多项式的最高次的非零系数为$a_k$,那么称$A(x)$的次数为$k$,记为$degree(A)=k$,任何一个大于该多项式次数的整数都是这个多项式的次数界.
多项式的表示
系数表达 :
对一个次数界为$n$的多项式$A(x)=\sum_{j=0}^{n-1}a_jx^j$而言,其系数表达是一个由系数组成的向量$\text{a}=(a_0,a_1,\dots,a_{n-1})$.
在给定系数求值时,采用霍纳法则(秦九邵算法)可以实现在$O(n)$的复杂度内完成求值运算.扩充:霍纳法则:
1
2
3void Horner (){
for(int i=n-1;i>=1;i--)
ans*=x,ans+=a[i];点值表达
一个次数界为$n$的多项式$A(x)$的点值表达就是一个由$n$个点值对组成的集合使得对$k=0,1,\dots,n-1$,所有$x_k$各不相同
则$A(x)=\sum_{j=0}^{n-1}A(x_j)$
多项式的乘法
这是多项式最核心的操作
即给定两个多项式$f(x)$和$g(x)$
要计算多项式$Q(x)=f(x).g(x):$
常规系数表达的计算是$O(n^2)$的,可以通过快速傅里叶变换在$O(nlogn)$下计算
多项式的逆元
对于多项式$f(x)$,若存在$g(x)$满足:
则称$g(x)$为$f(x)$在模$x^n$下的逆元,记作$f^{-1}(x)$
多项式的余数和商
对于多项式$f(x),g(x)$ ,存在唯一的$Q(x)$满足:
则称$Q(x)$为$f(x)$除$g(x)$的商,$R(x)$为$f(x)$除$g(x)$的余数.亦可记作
多项式的对数函数与指数函数
对数
对于一个多项式 $f(x),$ 可以将其对数函数看作其与麦克劳林级数的复合:注意这里常数项必须为$1$,也就是说求对数的多项式必须满足 $A(x)=1+\sum_{i=1}^{\infty} a_{i} z^{i}$ 。
多项式exp
其指数函数同样可以这样定义：看到这种 $e^{A(x)}$ 的指数形式显然非常不好处理, 于是采用等式两边同时 $\ln$ 的方式。设 $F(x)=e^{f(x)},$ 则有 $\ln F(x)-f(x) \equiv 0 \quad\left(\bmod x^{n}\right)$ 。构造函数
$G(F(x))=\ln F(x)-f(x),$ 牛顿迭代即可。多项式的$k$次幂
注意这里的$k$可以是一个实数,对于$k$的整数部分显然可以直接用快速幂优化,而对于$k$的小数部分,我们可以运用$A^k(x)=e^{k ln A(x)}$进行求解.事实上当 $A(x)$的常数项不为$1$的时候我们是可以进行这样的运算的,可以直接把$C^{-1}$乘到前面去 $\left(C^{-1}\right.$ 为 $A(x)$ 的常数项的逆$)$，于是可以用 $A^{k}(x)=C^{k}\left(C^{-1} A\right)^{k}(x)=C^{k} e^{k \ln \left(C^{-1} A(x)\right)}$ 来进行求解。但是注意到如果仅仅是求In的
话是不能乘上逆元的, 因为把 $\ln \left(C^{-1} A(x)\right)$ 拆开来之后变成了 $\ln C^{-1}+\ln A(x),$ 而
$\ln C^{-1}$ 本身就是没有定义的。
多项式的对数一般求法
我们设$f(x)$是一个平静的多项式,我们要求$ln[f(x)]$
则我们设$g(x)=ln[f(x)]$,那么$g^{\prime}(x)=\frac{f^{\prime}(x)}{f(x)}$,$\ln g(x)=\int \frac{g^{\prime}(x)}{g(x)} \mathrm{d} x$
麦克劳林级数
- 基本介绍:
对于一个给定的函数 $f(x),$ 如果能找到一个幂级数 $\sum_{n=0}^{\infty} a_{n} x^{n},$ 使 成立，则称$f(x)$可展开成$x$的幂级数。 把$x=0$代入式$(1)$及上述各式，得于是把它们代回式$(1)$，得通常称式$(2)$为$f(x)$的麦克劳林展开式或$f(x)$在$x=0$处的幂级数展开式。式$(2)$中等号右端的级数称为$f(x)$的麦克劳林级数或$f(x)$展开成$x$的幂级数。
可见,当$a_n=\frac{1}{n!}f^{(n)}(0)$求得系数的幂级数在它的收敛域内的和函数就是$f(x)$ 麦克劳林级数展开的条件及方法
定理$1$:
设函数$f(x)$的麦克劳林级数的收敛半径$R>0$，当$n→∞$时，如果函数$f(x)$在任一固定点$x$处的$n$阶导数$f^{(n)}(x)$有界，则函数$f(x)$在收敛区间$(-R，R)$内能展开成麦克劳林级数.即把函数$f(x)$展开成幂级数，有直接展开法和间接展开法
直接展开法
利用麦克劳林级数公式将函数$f(x)$展开成$x$的幂级数的方法，称为直接展开法。步骤可归纳为：
- 求出 $f(x)$ 的各阶导数 $f^{\prime}(x), f^{\prime \prime}(x), \ldots, f^{(n)}(x), \ldots,$ 令 $x=0$ 得 $f(0), f^{\prime}(0), f^{\prime \prime}(0), \ldots, f^{(n)}(0), \ldots$
- 写出$f(x)$的麦克劳林级数并求出收敛半径$R$
间接展开法
利用麦克劳林级数展开函数，需要求高阶导数，比较麻烦，如果能利用已知函数的展开式，根据幂级数在收敛域内的性质，将所给的函数展开成幂级数，这种方法称为间接展开法
多项式的多点求值和插值
多项式的多点求值 $(Multi-point evaluation)$ 即给出一个多项式 $f(x)$ 和 $n$ 个点 $x_{1}, x_{2}, \ldots, x_{n}$ 求
多项式的插值 $(Interpolation)$ 即给出 $n+1$ 个点
求一个 $n$ 次多项式 $f(x)$ 使得这 $n+1$ 个点都在 $f(x)$ 上。
这两种操作的实质就是将多项式在 系数表示 和 点值表示间转化。
拉格朗日插值
题目大意
给出$n$个点$P(x_i,y_i)$,将过这$n$个点的最多$n-1$次多项式记为$f(x)$,求$f(k)$的值.
方法1:牛顿插值法
差商的定义：
函数$f(x)$在两个互异点$x_i,x_j$处的一阶差商定义为：二阶差商:
$k+1$阶差商:
差商的性质
(参考连接)
- $k$阶差商可以表示为函数值$f(x_0),f(x_1),\dots,f(x_k)$的线性组合,即 差商具有对称性,即差商与节点的排列顺序无关.
若函数$f(x)$在包含节点区间$[a,b]$上存在$k$ 阶导数,则$k$阶差商与导数的关系为
即$k$次多项式的$k$阶差商为常数,低于$k$次多项式的差商为$0$(推了一会柿子之后发现对于多项式$A(x)=a_0+a_1x^1+\dots+a_kx^k$,他的$k$阶差商就是$a_k$)
牛顿插值多项式
- 牛顿插值多项式的推导 然后我们由$a,b,c,d$柿子可以得到 我们从上到下把柿子分别标为$(1),(2),\dots,(n)$柿,然后我们发现 然后我们把这个大柿子的上边的部分称为牛顿插值公式$N_n(x)$,下边的部分称为插值余项$R_n(x)$(懒得写latex了直接扔图了)
- 求值
说了这么多,我们来考虑怎么使用这个玩意求多项式的插值.我们发现,对于给定的$n$个点,我们可以在$O(n^2)$的复杂度内递推出他们的差商.而对于求值来说,我们发现也可以在$O(n^2)$的时间复杂度内求出.即首先要递推出$(x-x_0)\times(x-x_1)\times \dots \times (x-x_n)$然后再用我们之前预处理的差商相乘再求和即可. - 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
using namespace std;
int count , num;
int dataX[2005];
int lovivd[2005][2005];
int ksm ( int x , int y ) {
long long tmp = 1;
while ( y ) {
if ( y & 1 )
tmp = 1ll * tmp * x % HA;
x = 1ll * x * x % HA;
y >>= 1;
}
return tmp % HA;
}
void init(){
double x , y;
cin >> count >> num;
for ( int i = 0 ; i < count ; i++ ) {
cin >> x >> y;
dataX[i] = x;
lovivd[i][0] = y;
}
return;
}
void pre () {
int dis = 1;
for ( int i = 0 ; i < count ; i++ ) {
for ( int j = i ; j < count ; j++ ) {
int tmp = ( ( lovivd[j + 1][i] - lovivd[j][i] ) * ksm ( dataX[j+1] - dataX[j + 1 - dis] , HA - 2 ) )%HA;
lovivd[j + 1][i + 1] = tmp;
}
dis += 1;
}
return;
}
int work() {
long long calcValue = 0,temp = 1;
for ( int i = 0 ; i < count ; i++ ) {
temp = 1;
for ( int j = 0 ; j < i ; j++ )
//计算(X-X0)*(X-X1).....*(X-Xn-1)
temp = 1ll * temp * ( num - dataX[j] + HA ) % HA;
//计算f(X0,X1,....,Xn)*(X-X0)*(X-X1).....*(X-Xn-1)
temp = 1ll * temp % HA * lovivd[i][i] % HA;
//计算f(X0,X1,....,Xn)*(X-X0)*(X-X1).....*(X-Xn-1)的和
calcValue = ( calcValue + temp + HA ) % HA;
}
return calcValue;
}
signed main(){
init();
pre();
cout << work () <<endl;
return 0;
}
- 牛顿插值多项式的推导 然后我们由$a,b,c,d$柿子可以得到 我们从上到下把柿子分别标为$(1),(2),\dots,(n)$柿,然后我们发现 然后我们把这个大柿子的上边的部分称为牛顿插值公式$N_n(x)$,下边的部分称为插值余项$R_n(x)$(懒得写latex了直接扔图了)
方法2:待定系数法
设$f(x)=\sum_{i=0}^{n-1}a_ix_i$将每个$x_i$带入$f(x)$,有$f(x_i)=y_i$,然后就可以使用高斯消元解方程组了.
(高消会补的啊真的会补的啊别催了QAQ)
方法3:拉格朗日插值
基本求值
拉格朗日插值有一个好就是代码比牛顿插值好写(
我们把原来的点集$P$中的每一个点在$x$轴上的映射$(x_i,0)$记为$H_i$.对于每一个$i$,我们都选择$n$个点组成的点集{$P_i$} $\cup$ {$H_j |1\leq i \leq n,j\not= i$},然后做一条过这个$n$个点的至多$n-1$次的曲线$g_i(x)$.如图所示,$g_i$用彩色线,而原来的$f(x)$用黑色线表示(从$OI-wiki$上偷的图)
这样我们不难发现,对于某个$g_i(x)$,他们都过点$(x_i,y_i)$,并且其余点的函数值均为$0$,所以我们对于每个$g_i$可以构造出他们的表达式
又因为对于每一个$i$,都只有一条$g_i$经过点$P_i$,其余的点都经过$H_i$,所以这些$g_i$相加之后发现可以恰好等于$f(x)$,所以$f(x)$的表达式即为:
如果我们要求$f(k)$的值的话,那我们只需要直接将$k$带入进$x$即可,即
代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const int maxn = 2010;
using ll = long long;
ll mod = 998244353;
ll n, k, x[maxn], y[maxn], ans, s1, s2;
ll powmod(ll a, ll x) {
ll ret = 1ll, nww = a;
while (x) {
if (x & 1)
ret = ret * nww % mod;
nww = nww * nww % mod;
x >>= 1;
}
return ret;
}
ll inv(ll x) {
return powmod(x, mod - 2);
}
int main() {
scanf("%lld%lld", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%lld%lld", x + i, y + i);
for (int i = 1; i <= n; i++) {
s1 = y[i] % mod;
s2 = 1ll;
for (int j = 1; j <= n; j++)
if (i != j)
s1 = s1 * (k - x[j]) % mod, s2 = s2 * ((x[i] - x[j] % mod) % mod) % mod;
ans += s1 * inv(s2) % mod;
ans = (ans + mod) % mod;
}
printf("%lld\n", ans);
return 0;
}
求系数
不会生成函数,先咕咕咕了(
快速傅里叶变换(FFT)
概述
离散傅里叶变换（Discrete Fourier Transform，缩写为 DFT），是傅里叶变换在时域和频域上都呈离散的形式，将信号的时域采样变换为其 DTFT 的频域采样。
FFT 是一种高效实现 DFT 的算法，称为快速傅立叶变换（Fast Fourier Transform，FFT）。它对傅里叶变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。快速数论变换 (NTT) 是快速傅里叶变换（FFT）在数论基础上的实现。
在 1965 年，Cooley 和 Tukey 发表了快速傅里叶变换算法。事实上 FFT 早在这之前就被发现过了，但是在当时现代计算机并未问世，人们没有意识到 FFT 的重要性。一些调查者认为 FFT 是由 Runge 和 König 在 1924 年发现的。但事实上高斯早在 1805 年就发明了这个算法，但一直没有发表。
通俗地说，多项式由系数表示法转为点值表示法的过程，就是 DFT 的过程。相对地，把一个多项式的点值表示法转化为系数表示法的过程，就是 IDFT。而 FFT 就是通过取某些特殊的 的点值来加速 DFT 和 IDFT 的过程。
DFT(离散傅里叶变换)
(默认从这里开始所有的$n$都为$2$的整数次幂)
首先我们对于任意系数表达的多项式转化为点值表达的话,可以随便取$n$个$x$带入计算.但是我们会发现,如果我们这样操作的话,那么时间复杂度就是$O(n^2)$的.
但是DFT就是要让我们知道,我们可以带入一组非常神奇的$x$,这样就不用完成全部的次方的运算了.
考虑什么数能简化求幂的操作,我们首先想到的就是$\pm 1$或者$\pm i$,但是我们在实际操作时只有这四个数当作$x$是完全不够用的.
但是我们在复数平面上考虑一个单位圆
发现圆上所有的点都可以经过若干次方的操作变成$1$
然后我们如果把这个圆给$k$等分了的话,我们从$(1,0)$点开始,把这个点标成$0$号点,一直标号到$k-1$号,然后我们记编号为$i$的点代表的复数值为$\omega_{n}^{i}$,然后由复数的运算法则可知
我们把$\omega_{n}^{1}$称为$n$次单位根,而且每一个单位根都可以求出,即
那么$\omega_n^1,\omega_n^2,\dots,\omega_n^{n-1}$就为我们要带入的$x_0,x_1,\dots,x_{n-1}$
单位根的一些性质
1.
2.
3.
FFT（快速傅里叶变换）
我们发现我们在搞了一系列花里胡哨的东西之后,把我们选取的$x$带入原来的柿子里计算求值还是$O(n^2)$的,所以我们考虑优化,这就有了$FFT$.
我们首先设一个多项式$A(x)$
那么我们按照下标的奇偶性分成两半,就有
然后我们再把右边的柿子里的$x$提出来,发现就得到了
然后我们吃惊的发现左右两个柿子除了系数不同之外,长的是差不多的,所以我们设
那么我们显然可以发现:
然后我们设$k<\frac{n}{2}$,把$\omega_{n}^{k}$作为$x$带入$A(x)$中,就能得到
那么对于$A(\omega_n^{k+\frac{n}{2}})$的话我们带入,则有:
我们发现,只要知道了$A_1(\omega_{\frac{n}{2}}^k)$和$A_2(\omega_{\frac{n}{2}}^{k})$的值,那么我们就能快速的求出$A(\omega_n^k)$和$A(\omega_n^{k+\frac{n}{2}})$的值了.
所以对于某一段序列$\{A(\omega_n^1),A(\omega_n^2),\dots,A(\omega_n^n)\}$,我们只要扫描它的前半部分,那么我们就能求出整个序列的值.这样的话我们就可以分治来求了. 时间复杂度为$T(n)=2T(\frac{n}{2})+O(n)=O
(nlog_2n)$
IDFT离散傅里叶反变换
使用快速傅里叶变换将多项式的点值表达转化为系数表达,这个过程叫做离散傅里叶反变换.
我们先设$(d_0,d_1,\dots,d_{n-1})$为$(a_0,a_1,\dots,a_{n-1})$进行$DFT$后的结果.
这时候我们构造一个多项式$F(x)=d_0+d_1x+\dots+d_{n-1}x^{n-1}$.然后我们再设向量$(c_0,c_1,\dots,c_{n-1})$为原多项式进行$DFT$后的点值表示.其中$c_k$表示$F(x)$在$x=\omega_n^{-k}$的点值表示.
即$c_k=\sum_{i=0}^{n-1}d_i(\omega_n^{-k})^i$
然后我们考虑把$d_i$分解,用$a_i$表示,我们得到了
然后我们把$a_j$扔到外面,就得到了
然后我们把$(\omega_n^{-k})^i$转换为$(\omega_n^i)^{-k}$并把最后两项合并之后有
然后我们把$\sum_{i=0}^{n-1}(\omega_n^i)^{j-k}$单独拿出来,并且设$\xi=j-k$,然后我们发现这个柿子就等于
我们观察一下这个柿子,发现我们可以用等比数列求和公式来直接求出这个柿子的值,而且这个柿子恰好等于$0$.
那么原来的柿子就可以这样乱搞:
即
对于多项式 $A(x)$ 由插值节点 $\left(\omega_{n}^{0}, \omega_{n}^{1}, \omega_{n}^{2}, \ldots, \omega_{n}^{n-1}\right)$ 做离散傅里叶变换得到的点值向量
$\left(d_{0}, d_{1}, \ldots, d_{n-1}\right)$ 。我们将 $\left(\omega_{n}^{0}, \omega_{n}^{-1}, \omega_{n}^{-2}, \ldots, \omega_{n}^{-(n-1)}\right)$ 作为插值节点,
$\left(d_{0}, d_{1}, \ldots, d_{n-1}\right)$ 作为系数向量, 做一次离散傅里叶变换得到的向量每一项都除以 $n$ 之后得 到的 $\left(\frac{c_{0}}{n}, \frac{c_{1}}{n}, \ldots, \frac{c_{n-1}}{n}\right)$ 就是多项式的系数向量 $\left(a_{0}, a_{1}, \ldots, a_{n-1}\right)$ 。
注意到 $\omega_{n}^{-k}$ 是 $\omega_{n}^{k}$ 的共轭复数。
FFT朴素版代码
1 |
|
迭代实现
先盗一下图(
我们观察一下原序列和后序列,然后我们发现了一个显然的的结论:
我们需要求的序列实际是原序列下标的二进制反转！
因此我们对序列按照下标的奇偶性分类的过程其实是没有必要的,所以这样我们可以$O(n)$的利用某种操作得到我们要求的序列，然后不断向上合并就好了
FFT代码(迭代实现)
1 |
|
快速数论变换(NTT)
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想