精华内容
下载资源
问答
  • 留数法拆开重根多项式
    千次阅读
    2021-12-07 14:48:35

    部分分式展开以及系数的留数法求解

    有理真分式分解为部分分式

    当有一个次数小于n的多项式 P ( x ) P(x) P(x)

    则其一定可以写为如下的形式
    P ( x ) = A 1 ( x − a ) n − 1 + A 2 ( x − a ) n − 2 + ⋯ + A n − 1 ( x − a ) + A n P(x)=A_1(x-a)^{n-1}+A_2(x-a)^{n-2}+\dots+A_{n-1}(x-a)+A_n P(x)=A1(xa)n1+A2(xa)n2++An1(xa)+An
    因此两边同时除以 ( x − a ) n (x-a)^n (xa)n次后就可以得到
    P ( x ) ( x − a ) n = A 1 x − a + A 2 ( x − a ) 2 + ⋯ + A n ( x − a ) n \frac{P(x)}{(x-a)^{n}}=\frac{A_1}{x-a}+\frac{A_2}{(x-a)^2}+\dots+\frac{A_n}{(x-a)^n} (xa)nP(x)=xaA1+(xa)2A2++(xa)nAn
    因此可以得出结论,如果存在一个有理真分式 P ( x ) ( x − a ) n \frac{P(x)}{(x-a)^{n}} (xa)nP(x),(因为是真分式所以 P ( x ) P(x) P(x)的次数小于n),则该真分式一定可以化为上式右侧的部分分式的形式

    现在有一个有理真分式 P ( x ) Q ( x ) \frac{P(x)}{Q(x)} Q(x)P(x) Q ( x ) Q(x) Q(x)为n次多项式

    对分母 Q ( x ) Q(x) Q(x)进行因式分解,

    (1)假如 Q ( x ) Q(x) Q(x)有且只有k个不同的实根,没有虚根,则可因式分解为
    Q ( x ) = ∏ i = 1 k ( x − a i ) p i Q(x)=\prod\limits_{i=1}^k(x-a_i)^{p_i} Q(x)=i=1k(xai)pi
    其中 a i a_i ai Q ( x ) Q(x) Q(x) p i p_i pi重根, ∑ p i = n \sum{p_i}=n pi=n

    这种情况下,可以将有理真分式 P ( x ) Q ( x ) \frac{P(x)}{Q(x)} Q(x)P(x),按照如下公式化为部分分式的和
    P ( x ) Q ( x ) = ∑ i = 1 k ∑ j = 1 p i A i j ( x − a i ) j \frac{P(x)}{Q(x)}=\sum_{i=1}^k{\sum\limits_{j=1}^{p_i}{\frac{A_{ij}}{(x-a_i)^j}}} Q(x)P(x)=i=1kj=1pi(xai)jAij
    (2)假如n次多项式 Q ( x ) Q(x) Q(x)不只有实根,还有复根,那么其依然满足因式分解定理,即在实数域上可以分解为如下形式
    Q ( x ) = a 0 ⋅ ∏ i = 1 k ( x − a i ) p i ∏ i = 1 l ( x 2 + b i x + c i ) q i Q(x)=a_0\cdot\prod\limits_{i=1}^k{(x-a_i)^{p_i}}\prod\limits_{i=1}^{l}{(x^2+b_ix+c_i)^{q_i}} Q(x)=a0i=1k(xai)pii=1l(x2+bix+ci)qi

    ∑ p i + 2 ∑ q i = n \sum{p_i}+2\sum{q_i}=n pi+2qi=n

    这种情况下,可以将有理真分式 P ( x ) Q ( x ) \frac{P(x)}{Q(x)} Q(x)P(x),按照如下公式化为部分分式的和
    P ( x ) Q ( x ) = ∑ i = 1 k ∑ j = 1 p i A i j ( x − a i ) j + ∑ i = 1 l ∑ j = 1 q i B i j x + C i j ( x 2 + b i x + c i ) j \frac{P(x)}{Q(x)}=\sum_{i=1}^k{\sum\limits_{j=1}^{p_i}{\frac{A_{ij}}{(x-a_i)^j}}}+\sum_{i=1}^l{\sum\limits_{j=1}^{q_i}{\frac{B_{ij}x+C_{ij}}{(x^2+b_ix+c_i)^j}}} Q(x)P(x)=i=1kj=1pi(xai)jAij+i=1lj=1qi(x2+bix+ci)jBijx+Cij

    利用留数和留数定理求部分分式的系数

    P ( x ) Q ( x ) = ∑ i = 1 k ∑ j = 1 p i A i j ( x − a i ) j + ∑ i = 1 l ∑ j = 1 q i B i j x + C i j ( x 2 + b i x + c i ) j \frac{P(x)}{Q(x)}=\sum_{i=1}^k{\sum\limits_{j=1}^{p_i}{\frac{A_{ij}}{(x-a_i)^j}}}+\sum_{i=1}^l{\sum\limits_{j=1}^{q_i}{\frac{B_{ij}x+C_{ij}}{(x^2+b_ix+c_i)^j}}} Q(x)P(x)=i=1kj=1pi(xai)jAij+i=1lj=1qi(x2+bix+ci)jBijx+Cij

    假定零极点可以是复数,则依旧可以化为如下形式:
    P ( x ) Q ( x ) = ∑ i = 1 k ∑ j = 1 p i A i j ( x − a i ) j \frac{P(x)}{Q(x)}=\sum_{i=1}^k{\sum\limits_{j=1}^{p_i}{\frac{A_{ij}}{(x-a_i)^j}}} Q(x)P(x)=i=1kj=1pi(xai)jAij
    则系数 A i j A_{ij} Aij,根据留数定理可以用如下公式求出
    A i j = 1 ( p i − j ) ! lim ⁡ x → a i [ ( x − a i ) p i P ( x ) Q ( x ) ] ( p i − j ) A_{ij}=\frac{1}{(p_i-j)!}\lim\limits_{x\to a_i}{[(x-a_i)^{p_i}\frac{P(x)}{Q(x)}]}^{(p_i-j)} Aij=(pij)!1xailim[(xai)piQ(x)P(x)](pij)
    右上角的(j-1)表示求j-1阶导数

    例如:
    x 2 + 5 x − 2 x 3 + 3 x 2 + 3 x + 1 \frac{x^2+5x-2}{x^3+3x^2+3x+1} x3+3x2+3x+1x2+5x2
    其中 Q ( x ) = x 3 + 3 x 2 + 3 x + 1 = ( x + 1 ) 3 Q(x)=x^3+3x^2+3x+1=(x+1)^3 Q(x)=x3+3x2+3x+1=(x+1)3

    因此
    x 2 + 5 x − 2 x 3 + 3 x 2 + 3 x + 1 = K 1 x + 1 + K 2 ( x + 1 ) 2 + K 3 ( x + 1 ) 3 \frac{x^2+5x-2}{x^3+3x^2+3x+1}=\frac{K_1}{x+1}+\frac{K_2}{(x+1)^2}+\frac{K_3}{(x+1)^3} x3+3x2+3x+1x2+5x2=x+1K1+(x+1)2K2+(x+1)3K3

    K 3 = lim ⁡ x → − 1 [ ( x + 1 ) 3 ⋅ x 2 + 5 x − 2 x 3 + 3 x 2 + 3 x + 1 ] ( 3 − 3 ) = lim ⁡ x → − 1 [ x 2 + 5 x − 2 ] = − 6 K_3=\lim\limits_{x\to -1}{[(x+1)^3\cdot\frac{x^2+5x-2}{x^3+3x^2+3x+1}]}^{(3-3)}=\lim\limits_{x\to -1}{[x^2+5x-2]}=-6 K3=x1lim[(x+1)3x3+3x2+3x+1x2+5x2](33)=x1lim[x2+5x2]=6

    K 2 = lim ⁡ x → − 1 [ ( x + 1 ) 3 ⋅ x 2 + 5 x − 2 x 3 + 3 x 2 + 3 x + 1 ] ( 3 − 2 ) = lim ⁡ x → − 1 [ 2 x + 5 ] = 3 K_2=\lim\limits_{x\to -1}{[(x+1)^3\cdot\frac{x^2+5x-2}{x^3+3x^2+3x+1}]}^{(3-2)}=\lim\limits_{x\to -1}{[2x+5]}=3 K2=x1lim[(x+1)3x3+3x2+3x+1x2+5x2](32)=x1lim[2x+5]=3

    K 1 = 1 2 ! ⋅ lim ⁡ x → − 1 [ ( x + 1 ) 3 ⋅ x 2 + 5 x − 2 x 3 + 3 x 2 + 3 x + 1 ] ( 3 − 1 ) = 1 2 ⋅ lim ⁡ x → − 1 [ 2 ] = 1 K_1=\frac{1}{2!}\cdot\lim\limits_{x\to -1}{[(x+1)^3\cdot\frac{x^2+5x-2}{x^3+3x^2+3x+1}]}^{(3-1)}=\frac{1}{2}\cdot\lim\limits_{x\to -1}{[2]}=1 K1=2!1x1lim[(x+1)3x3+3x2+3x+1x2+5x2](31)=21x1lim[2]=1

    因此
    x 2 + 5 x − 2 x 3 + 3 x 2 + 3 x + 1 = 1 x + 1 + 3 ( x + 1 ) 2 − 6 ( x + 1 ) 3 \frac{x^2+5x-2}{x^3+3x^2+3x+1}=\frac{1}{x+1}+\frac{3}{(x+1)^2}-\frac{6}{(x+1)^3} x3+3x2+3x+1x2+5x2=x+11+(x+1)23(x+1)36

    更多相关内容
  • 由于利用留数定理分解分式多项式的计算麻烦,所以决定用python做一个利用留数定理分解分式多项式程序,实现只要输入多项式就可以得到各种中间参数和最终拆分结果的目的。从本程序可以得到:分解后每项多项式分子值、...

    编写之初

    由于利用留数定理分解分式多项式的计算麻烦,所以决定用python做一个利用留数定理分解分式多项式程序,实现只要输入多项式就可以得到各种中间参数和最终拆分结果的目的。从本程序可以得到:分解后每项多项式分子值、计算分解后每项多项式分子值的过程展示、最终分解结果展示。

    算数实现

    利用留数定理分解分式多项式计算过程以下图为例所示
    留数定理分解多项式举例
    对于算数运算形象的理解:以该式为例,分解后各项分母为原多项式分母中的各项(s、(s+2)、(s+3)²)加上这些项中高次幂项去掉次幂为分母的项((s+3));分解后各项分子为原多项式分母依次去掉各项后求极限所得值(-4、1/3、3)以及n(n>1)次幂项去掉该项后的n阶微分式求极限所得值(-10/3)。也依据这个思路编写程序。

    依赖的包

    1.sympy模块
    sympy模块,可以进行符号计算,可以定义符号变量,进行代数运算,以及微分运算、积分运算等。

    pip install sympy
    

    2.re正则化模块
    re模块是python独有的匹配字符串的模块,该模块中提供的很多功能是基于正则表达式实现的。

    pip install re
    

    完整代码及注释

    import sympy as sp
    import re
    
    s = sp.symbols('s')     # 创建符号变量
    
    print('以 6*(s+1)/(s*(s+2)*(s+3)**2) 形式为例')
    Y = input('请输入待分解多项式:')   # 复制 例 6*(s+1)/(s*(s+2)*(s+3)**2)
    
    # denominator = y.split('/')[0]   # 分子项
    molecule = Y.split('/')[1]      # 分母项
    
    moleculelist = molecule.strip('()').split('*')  # 分母每项
    # print(moleculelist)
    
    reg = re.compile(r"(?<=\*)\d+")     # 获取分式中的幂数
    match=reg.search(Y)
    pow = match.group(0)
    
    molecule_number = 0     # 初始化分母项索引
    # 计算拆分后各项值
    while molecule_number < len(moleculelist):
        try:
            if moleculelist[molecule_number] != '':
                if moleculelist[molecule_number + 1] != '':
                    y = Y.replace(moleculelist[molecule_number]+'*', '')    # 得到用来计算 该项分子值 的多项式
                    if moleculelist[molecule_number] == 's':
                        value = sp.limit(y, s, 0)               # 求极限计算 该项分子值
                        print('\n计算分母为' + str(moleculelist[molecule_number]) +'项的分子:limit——>0 ', y)
                        print('计算得;', value)
                    else:
                        limit_value = -int(re.findall('(\d+)', moleculelist[molecule_number])[0])   # 获取求极限时的 极限参数
                        value = sp.limit(y, s, limit_value)         # 求极限计算 该项分子值
                        print('计算分母为' + str(moleculelist[molecule_number]) +'项的分子:limit——>' + str(limit_value), y)
                        print('计算得:', value)
                else:
                    y = Y.replace('*' + moleculelist[molecule_number] + '**' + pow, '')     # 得到用来计算 该项分子值 的多项式
                    limit_value = -int(re.findall('(\d+)', moleculelist[molecule_number])[0])       # 获取求极限时的 极限参数
                    value = sp.limit(y, s, limit_value)         # 求极限计算 该项分子值
                    print('计算分母为' + str(moleculelist[molecule_number]) + '**' + pow + '项的分子:limit——>' + str(limit_value), y)
                    print('计算得:', value)
    
                    y_diff = sp.together(sp.diff(y, s, int(pow)-1))      # 求解 除n次幂项外分式 n阶导数
                    limit_value = -int(re.findall('(\d+)', moleculelist[molecule_number])[0])       # 获取求极限时的 极限参数
                    value = sp.limit(y_diff, s, limit_value)        # 求极限计算 该项分子值
                    print('计算分母为' + str(moleculelist[molecule_number]) + '项的'+ str(int(pow)-1) + '阶导数的分子:limit——>' + str(limit_value), y_diff)
                    print('计算得:', value)
    
        except: pass
        molecule_number += 1
    
    # print(molecule+'\n'+molecule)
    print('分解结果为:',sp.apart(Y, s))      # 拆分结果
    
    

    运行结果

    运行代码,首先以例示形式输入待分解多项式,得到分解过程及结果
    程序运行结果

    感悟与不足

    本来打算纯手写一个留数定理分解分式多项式的程序,但是由于其中涉及到极限与微分的计算,而这两个模块编写起来又要一定时间,于是借助了sympy模块辅助编程,但是我意外地发现,sympy模块居然自带多项式分解函数 sympy.apart()因此我也在呈现分解结果时用到了这个函数,免去了字符串处理当中的一系列麻烦。因此如果大家对多项式分解的过程不在意,只想得到分解结果,只需执行sympy.apart()函数即可,至于它其中的运算原理我也不得而知。

    展开全文
  • 文章目录关于多项式多项式乘法DescriptionSample复数的表示、基本定义与一些性质FFT预备知识FFTDFTIDFTFFT之再优化AttentionCode 关于多项式 一个形如f(x)=∑i=0naixi(an≠0)f(x)=\sum_{i=0}^n a_i x^i(a_n \neq 0)f...

    关于多项式

    一个形如 f ( x ) = ∑ i = 0 n a i x i ( a n ≠ 0 ) f(x)=\sum_{i=0}^n a_i x^i(a_n \neq 0) f(x)=i=0naixi(an=0)的式子被称为一个 n n n次多项式。例如, 3 x 3 + 5 x 2 + x + 2021 3x^3+5x^2+x+2021 3x3+5x2+x+2021是一个 3 3 3次多项式。

    一个多项式有多种表示方法,其中最经典的是系数表示法。形式化地说, ∑ i = 0 n a i n i \sum_{i=0}^n a_i n^i i=0naini被表示为 ( a 0 , a 1 , a 2 ⋯ a n ) (a_0,a_1,a_2 \cdots a_n) (a0,a1,a2an)。一些多项式的题目中往往会直接或间接地给出这些系数。下面的题目中,“给定一个多项式”默认为“给出此多项式的各项系数”

    多项式还有点值表示法。假设这个多项式为 f f f,那么在 f f f的图像上任意取出 n + 1 n+1 n+1个点即可确定这个多项式的各项系数。例如, 3 x + 2 3x+2 3x+2的一种点值表示为 ( 0 , 2 ) ( 1 , 5 ) (0,2)(1,5) (0,2)(1,5)。点值表示法在多项式乘法中与多项式求逆中有很大的用处。


    在多项式的学习中,可能会遇到各种各样的数学大坑,这一部分也是学习中的重难点,这也导致了笔者曾经几次三番放弃学习多项式。考虑到我的较差体验,笔者将会耐心地为大家去补充这些知识,相信你能够迅速理解这些妙妙的东西。

    鸣谢: gh巨佬(他教会了我这个东西,还为本文贡献了许多图片)

    多项式乘法

    Description

    给定一个 n n n次多项式 A A A m m m次多项式 B B B,请求出 A A A B B B的卷积(即 A × B A×B A×B的各项系数)。

    n , m ≤ 1 0 6 n,m \le 10^6 n,m106

    Sample

    Input
    1 1
    1 1
    1 1

    Output
    1 2 1

    Explanation
    ( x + 1 ) ( x + 1 ) = x 2 + 2 x + 1 (x+1)(x+1)=x^2+2x+1 (x+1)(x+1)=x2+2x+1

    复数的表示、基本定义与一些性质

    在初中阶段,我们已经学过了实数,它的特点是能在一条数轴上表示出来,比如 3 , 2021 , 998244353 1 0 9 + 7 \sqrt 3, 2021, \frac {998244353} {10^9+7} 3 ,2021,109+7998244353

    复数是形如 a + b i a+bi a+bi的数,其中 i = − 1 i=\sqrt {-1} i=1 ,它也被称为虚数单位。不难发现,当 b = 0 b=0 b=0时该数为实数,否则为虚数。

    显然,虚数是不能使用一条数轴表示出来的。

    那我们采用两条数轴呢?考虑一个“平面直角坐标系”: 横轴表示实部(即 a + b i a+bi a+bi中的 a a a),纵轴表示虚部(即 a + b i a+bi a+bi中的 b i bi bi),我们可以将 a + b i a+bi a+bi表示在 ( a , b ) (a,b) (a,b)处!如下图:

    在这里插入图片描述
    我们成功地将复数表示在了“平面直角坐标系”上。现在,我们再赋予复数几个定义:

    ①幅角 φ \varphi φ(虽然这是欧拉函数, 但是请您将就着看吧/kk): ( a , b ) (a,b) (a,b)与原点连线和 x x x轴所形成的角的大小(注意区分夹角与角度)。
    ②模长 d d d: ( a , b ) (a,b) (a,b)到原点的距离。

    如下图:

    在这里插入图片描述
    好了,我们的定义到此为止。剩下的工作交给欧拉。

    Euler: “ e i φ = cos ⁡ ( φ ) + i sin ⁡ ( φ ) e^{i \varphi}=\cos(\varphi)+i \sin(\varphi) eiφ=cos(φ)+isin(φ)

    式子中的 e e e是自然对数(即 lim ⁡ x → ∞ ( x + 1 x ) x \lim_{x→∞} (x+\frac 1 x)^x limx(x+x1)x), i i i是虚数单位。

    这是十分有用的一个公式。由于笔者太菜不会证明所以证明省略 结合我们上面对复数的定义与在坐标系上的表示,不难发现 e i φ e^{i \varphi} eiφ对应的就是一个模长为 1 1 1,幅角为 φ \varphi φ的点!

    为什么呢?考虑 cos ⁡ ( φ ) + i sin ⁡ ( φ ) \cos(\varphi)+i \sin(\varphi) cos(φ)+isin(φ)的坐标为 ( cos ⁡ ( φ ) , sin ⁡ ( φ ) ) (\cos(\varphi),\sin(\varphi)) (cos(φ),sin(φ))。根据勾股定理,此时的模长为 c o s 2 ( φ ) + s i n 2 ( φ ) = 1 \sqrt {cos^2(\varphi)+sin^2(\varphi)}=1 cos2(φ)+sin2(φ) =1。根据 s i n sin sin的定义,不难得到幅角为 φ \varphi φ

    更一般性地,一个模长为 a a a,幅角为 φ \varphi φ的复数总可以用 a × e i φ a \times e^{i \varphi} a×eiφ来表达。为了方便叙述,我们将这个复数简记为 ( a , φ ) (a,\varphi) (a,φ)

    考虑两个复数相乘: ( a , φ 1 ) × ( b , φ 2 ) (a,\varphi_1) \times (b,\varphi_2) (a,φ1)×(b,φ2),根据欧拉定理,这个式子等价于

    ( a × e i φ 1 ) ( b × e i φ 2 ) (a \times e^{i \varphi_1})(b×e^{i \varphi_2}) (a×eiφ1)(b×eiφ2)

    = ( a b ) × ( e i ( φ 1 + φ 2 ) ) =(ab) \times (e^{i(\varphi_1+\varphi_2)}) =(ab)×(ei(φ1+φ2))

    综上所述,复数相乘,模长相乘且幅角相加

    FFT预备知识

    接下来的时间交给傅里叶。

    他让我们画了一个以原点为圆心且半径为 1 1 1的圆(是不是很可爱呢 )。然后我们把它 n ( n = 2 k , k ∈ N ) n(n=2^k, k \in N) n(n=2k,kN)等分了:

    在这里插入图片描述

    于是我们在圆上得到了 8 8 8个表示复数的点。从幅角为 0 ° 0 \degree 0°的点开始逆时针标号,分别标号为 0 , 1 , 2 ⋯   , n − 1 , n , n + 1 ⋯ 0,1,2 \cdots,n-1,n,n+1\cdots 0,1,2,n1,n,n+1其中,标号为 k k k的点简记为 w n k w_n^k wnk w n k w_n^k wnk被称为一个单位根。

    单位根是有许多性质的。下面列出了部分重要性质:

    n n n个单位根两两不同
    w n k = w 2 n 2 k w_n^k=w_{2n}^{2k} wnk=w2n2k
    ( w n k ) n = 1 (w_n^k)^n=1 (wnk)n=1
    w n k = − w n k − n 2 w_n^k=-w_n^{k-\frac n 2} wnk=wnk2n
    w n a × w n b = w n a + b w_n^a \times w_n^b=w_n^{a+b} wna×wnb=wna+b

    证明十分简单,只需要瞅一瞅那个被 n n n等分的圆即可。如果觉得不够严谨,也可以结合复数相乘“模长相乘,幅角相加”的性质来详细证明。说白了就是我懒不想证了

    这些性质有什么用呢?马上你就知道了。

    FFT

    假设我们想要求出两个多项式 f , g f,g f,g的乘积。

    首先,一种方法是枚举 f , g f,g f,g中的两项并向答案对应的项做贡献。这样子的时间复杂度是 O ( n m ) O(nm) O(nm)的。

    傅里叶又开始吊打我们了……祂提出了FFT的详细流程:

    ①带入 n n n个单位根作为 x x x,分别求出对应的 y = f ( x ) y=f(x) y=f(x)(即转换为了点值表示法);
    ②带入 n n n个单位根作为 x x x,分别求出对应的 y = g ( x ) y=g(x) y=g(x)
    ③将对应的点值相乘,即将 ( x 1 , y 1 ) ( x 1 , y 2 ) (x_1,y_1)(x_1,y_2) (x1,y1)(x1,y2)转换为 ( x 1 , y 1 y 2 ) (x_1,y_1y_2) (x1,y1y2)
    ④将点值表示法还原为系数表示法,得到答案。

    其中,①被称为DFT,④被称为IDFT,整个流程被称为FFT,即“傅里叶快速变换”。

    考虑①②是基本相同的,③直接 O ( n ) O(n) O(n)相乘,④是①、②的逆变换。现在,关键在于求出①与④的做法。

    DFT

    现在我们想要快速求出 ∑ i = 0 n − 1 a i   w n i \sum_{i=0}^{n-1} a_i\ w_n^i i=0n1ai wni。考虑将它按照 i i i的奇偶性拆开:

    ∑ i = 0 n − 1 a i   w n i \sum_{i=0}^{n-1} a_i\ w_n^i i=0n1ai wni
    = ∑ i = 0 ⌊ n 2 ⌋ − 1 a 2 i   w n 2 i k + ∑ i = 0 ⌊ n 2 ⌋ − 1 a 2 i + 1 w n ( 2 i + 1 ) k =\sum_{i=0}^{\lfloor \frac n 2 \rfloor-1} a_{2i}\ w_n^{2ik}+\sum_{i=0}^{\lfloor \frac n 2 \rfloor-1} a_{2i+1} w_n^{(2i+1)k} =i=02n1a2i wn2ik+i=02n1a2i+1wn(2i+1)k
    = ∑ i = 0 ⌊ n 2 ⌋ − 1 a 2 i   w n 2 i k + w n k ∑ i = 0 ⌊ n 2 ⌋ − 1 a 2 i + 1 w n 2 i k =\sum_{i=0}^{\lfloor \frac n 2 \rfloor-1} a_{2i}\ w_n^{2ik}+w_n^k\sum_{i=0}^{\lfloor \frac n 2 \rfloor-1} a_{2i+1} w_n^{2ik} =i=02n1a2i wn2ik+wnki=02n1a2i+1wn2ik

    根据单位根的性质② w n k = w 2 n 2 k w_n^k=w_{2n}^{2k} wnk=w2n2k,不难得到

    = ∑ i = 0 ⌊ n 2 ⌋ − 1 a 2 i   w n 2 i k + w n k ∑ i = 0 ⌊ n 2 ⌋ − 1 a 2 i + 1 w n 2 i k =\sum_{i=0}^{\lfloor \frac n 2 \rfloor-1} a_{2i}\ w_n^{2ik}+w_n^k\sum_{i=0}^{\lfloor \frac n 2 \rfloor-1} a_{2i+1} w_n^{2ik} =i=02n1a2i wn2ik+wnki=02n1a2i+1wn2ik
    = ∑ i = 0 ⌊ n 2 ⌋ − 1 a 2 i   w n 2 i k + w n k ∑ i = 0 ⌊ n 2 ⌋ − 1 a 2 i + 1 w n 2 i k =\sum_{i=0}^{\lfloor \frac n 2 \rfloor-1} a_{2i}\ w_{\frac n 2}^{ik}+w_n^k\sum_{i=0}^{\lfloor \frac n 2 \rfloor-1} a_{2i+1} w_{\frac n 2}^{ik} =i=02n1a2i w2nik+wnki=02n1a2i+1w2nik

    然后分治下去就做完了?

    并不是。考虑直接分治的话,每次都要带入 w n 0 , w n 1 … … w n n − 1 w_n^0,w_n^1……w_n^{n-1} wn0,wn1wnn1 n n n个单位根。虽然系数每次减半,但是带入的值并没有减半,这导致我们的时间复杂度依然不对。

    考虑对于 k ≤ n 2 k \le \frac n 2 k2n的时候按照上述方式去分治。当 n 2 + 1 ≤ k \frac n 2+1 \le k 2n+1k时,我们令 K = k − n 2 K=k-\frac n 2 K=k2n,将其带入得

    ∑ i = 0 n − 1 a i w n ( K + n 2 ) i \sum_{i=0}^{n-1} a_i w_n^{(K+\frac n 2)i} i=0n1aiwn(K+2n)i
    = ∑ i = 0 n 2 − 1 a 2 i w n ( K + n 2 ) 2 i + ∑ i = 0 n 2 − 1 a 2 i + 1 w n ( K + n 2 ) ( 2 i + 1 ) =\sum_{i=0}^{\frac n 2-1}a_{2i}w_n^{(K+\frac n 2)2i}+\sum_{i=0}^{\frac n 2-1} a_{2i+1} w_n^{(K+\frac n 2)(2i+1)} =i=02n1a2iwn(K+2n)2i+i=02n1a2i+1wn(K+2n)(2i+1)

    考虑有
    (1) w n ( K + n 2 ) 2 i w_n^{(K+\frac n 2)2i} wn(K+2n)2i
    = w n 2 i K × w n n i = w n 2 i K =w_n^{2iK}×w_n^{ni}=w_{\frac n 2}^{iK} =wn2iK×wnni=w2niK

    (2) w n ( K + n 2 ) ( 2 i + 1 ) w_n^{(K+\frac n 2)(2i+1)} wn(K+2n)(2i+1)
    = w n ( 2 i K + K + n i + n 2 ) =w_n^{(2iK+K+ni+\frac n 2)} =wn(2iK+K+ni+2n)
    = w n 2 i K × w n K × w n n i × w n n 2 =w_n^{2iK}×w_n^K×w_n^{ni}×w_n^{\frac n 2} =wn2iK×wnK×wnni×wn2n
    = − w n 2 i K × w n K =-w_{\frac n 2}^{iK}×w_{n}^K =w2niK×wnK

    往回带入得

    ∑ i = 0 n 2 − 1 a 2 i w n 2 K i − w n K ∑ i = 0 n 2 − 1 a 2 i + 1 w n 2 K i \sum_{i=0}^{\frac n 2-1} a_{2i} w_{\frac n 2}^{Ki}-w_n^K\sum_{i=0}^{\frac n 2 -1} a_{2i+1} w_{\frac n 2}^{Ki} i=02n1a2iw2nKiwnKi=02n1a2i+1w2nKi

    至此,FFT的推导到此结束。我们总结一波。

    A A A表示一个用系数表示的多项式, A 1 A_1 A1表示 A A A的偶数项的系数形成的多项式, A 2 A_2 A2表示 A A A的奇数项的系数形成的多项式。则

    A ( w n k ) = A 1 ( w n 2 k ) + w n k A 2 ( w n 2 k ) A(w_n^k)=A_1(w_{\frac n 2}^k)+w_n^k A_2(w_{\frac n 2}^k) A(wnk)=A1(w2nk)+wnkA2(w2nk)
    A ( w n k + n 2 ) = A 1 ( w n 2 k ) − w n k A 2 ( w n 2 k ) A(w_n^{k+\frac n 2})=A_1(w_{\frac n 2}^k)-w_n^k A_2(w_{\frac n 2}^k) A(wnk+2n)=A1(w2nk)wnkA2(w2nk)

    此时我们分治下去的时间复杂度是什么呢?

    假设对于一个项数为 n n n的多项式,做一遍DFT的时间复杂度为 T ( n ) T(n) T(n)。每次拆开奇偶位并进行分治,这一部分的时间复杂度是 2 T ( n 2 ) 2T(\frac n 2) 2T(2n);然后还要对于 w n 0 , w n 1 … … w n n − 1 w_n^0,w_n^1……w_n^{n-1} wn0,wn1wnn1分别求出它们带进去当前多项式后得到的值,由于每次调用都是 O ( 1 ) O(1) O(1)的,所以这一部分的时间复杂度是 O ( n ) O(n) O(n)的。

    T ( n ) = 2 T ( n 2 ) + O ( n ) T(n)=2T(\frac n 2)+O(n) T(n)=2T(2n)+O(n)。通过主定理不难得到 T ( n ) = O ( n log ⁡ n ) T(n)=O(n \log n) T(n)=O(nlogn)

    IDFT

    学会了DFT你是不是很开心?可是如果不会IDFT,一切都是白搭/kk

    不难发现,这一部分是一个解方程组的问题。

    盗个图:

    在这里插入图片描述
    我们想要求出的就是 a 0 , a 1 ⋯ a n − 1 a_0,a_1 \cdots a_{n-1} a0,a1an1

    写成矩阵的形式:

    在这里插入图片描述
    令上图中从左到右的三个矩阵分别是 A , X , B A,X,B A,X,B

    考虑另一个矩阵 T T T,其中 T i j = w n − i j T_{ij}=w_n^{-ij} Tij=wnij

    在这里插入图片描述
    F = A × T F=A×T F=A×T。考虑 F F F长啥样,我们分类讨论如下:

    i = j i=j i=j,此时 F i , j = ∑ k = 1 n w n i k w n − j k = ∑ k = 1 n w n 0 = n F_{i,j}=\sum_{k=1}^n w_n^{ik} w_n^{-jk}=\sum_{k=1}^n w_n^0=n Fi,j=k=1nwnikwnjk=k=1nwn0=n

    i ≠ j i≠j i=j

    ∑ k = 0 n − 1 w n − i k w n k j \sum_{k=0}^{n-1} w_n^{-ik} w_n^{kj} k=0n1wnikwnkj

    ∑ k = 0 n − 1 w n k ( j − i ) \sum_{k=0}^{n-1} w_n^{k(j-i)} k=0n1wnk(ji)

    这不就是一个等比数列求和的形式吗?

    ∑ k = 0 n − 1 w n k ( j − i ) \sum_{k=0}^{n-1} w_n^{k(j-i)} k=0n1wnk(ji)

    = 1 − w n n ( j − i ) 1 − w n j − i =\frac {1-w_n^{n(j-i)}} {1-w_n^{j-i}} =1wnji1wnn(ji)

    由于 w n n ( j − i ) = 1 w_n^{n(j-i)}=1 wnn(ji)=1,所以上面这个式子为 0 0 0


    于是 F F F是一个单位矩阵的 n n n倍!

    于是 A A A的逆矩阵就是 T T T除以 n n n

    更形式化地说,

    在这里插入图片描述
    综上所述,我们只需要将 w n − 0 , w n − 1 ⋯ w n − ( n − 1 ) w_n^{-0},w_n^{-1} \cdots w_n^{-(n-1)} wn0,wn1wn(n1)逐一带入,用类似 D F T DFT DFT的方法与各项系数为 A ( w n 0 ) , A ( w n 1 ) ⋯ A ( w n n − 1 ) A(w_n^0),A(w_n^1) \cdots A(w_n^{n-1}) A(wn0),A(wn1)A(wnn1)的多项式相乘,最终再将各项系数除以 n n n即可得到最终的答案

    显然这一部分的时间复杂度仍然是 O ( n log ⁡ n ) O(n \log n) O(nlogn)的。

    FFT之再优化

    到这一步,我们似乎已经得到了 O ( n log ⁡ n ) O(n \log n) O(nlogn)的解法。但是很可惜,这种做法的常数非常之大。gh尝曰: “此法尚不如暴力也。”

    所以我们需要对这种做法的常数进行一定的优化。

    我们观察一下做FFT的过程:

    在这里插入图片描述
    操作的位置的原序列与后序列如下:
    在这里插入图片描述
    发现了什么?将原序列的下标做二进制反转后就是后序列!

    所以我们可以采用数位 d p dp dp处理出每一个在 [ 0 , n − 1 ] [0,n-1] [0,n1]范围内的数反转后的值。每次在做DFT/IDFT前进行反转即可。

    Attention

    ①要多次做复数相加,相减和相乘的运算,可以将一个复数拆成实部与虚部并放在一个结构体里面,然后重载运算符(比如 + , − , × +, -, \times +,,×);

    ②单位根 w n k = c o s ( 2 π n k ) + i   s i n ( 2 π n k ) w_n^k=cos(\frac {2 \pi} n k)+i\ sin(\frac {2 \pi} n k) wnk=cos(n2πk)+i sin(n2πk)——请注意C++里面的三角函数采用了弧度制;

    ③FFT有精度误差,最后输出的时候要精确到整数部分输出;

    n , m n,m n,m较大请使用快读;

    ⑤答案的最高项的次数可能会达到 n + m n+m n+m,所以我们必须让 A , B A,B A,B与答案的项数为一个大于 n + m n+m n+m 2 2 2的次方数。

    其他详见有注释的代码。

    Code: FFT

    #include <bits/stdc++.h>
    #define int long long
    #define double long double
    using namespace std;
    const int maxl=5000005;
    const double PI=acos(-1.00);
    
    int read(){//快读
    	int s=0,w=1;char ch=getchar();
    	while (ch<'0'||ch>'9'){if (ch=='-')  w=-w;ch=getchar();}
    	while (ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^'0');ch=getchar();}
    	return s*w;
    }
    int n,m,len=1,cnt=0;
    int r[maxl];
    
    struct Complex{
    	double x,y;
    	Complex(double a=0,double b=0){x=a,y=b;}
    	Complex operator + (const Complex a){return Complex(a.x+x,a.y+y);}
    	Complex operator - (const Complex a){return Complex(x-a.x,y-a.y);}
    	Complex operator * (const Complex a){return Complex(x*a.x-y*a.y,x*a.y+y*a.x);}
    	//重载运算符
    }a[maxl],b[maxl];
    
    void FFT(Complex *a,int len,int flag){//flag=1表示在做DFT,否则在做IDFT
    	for (int i=0;i<len;i++){
    		if (i<r[i])  swap(a[i],a[r[i]]);
    		//如果不写i<r[i]那么会被交换两次,即交换回来
    	}
    	for (int i=2;i<=len;i*=2){
    		Complex wn(cos(flag*2*PI/i),sin(flag*2*PI/i));//求出w_i^1
    		for (int j=0;j<len;j+=i){
    			Complex w(1,0);
    			for (int k=j;k<j+(i/2);k++){
    				Complex u=a[k],v=w*a[k+(i/2)];//千万别忘记乘上w
    				a[k]=u+v,a[k+(i/2)]=u-v;//套公式
    				w=w*wn;//实时维护w_i^(k-j)
    			}
    		}
    	}
    	if (flag==-1){
    		for (int i=0;i<len;i++)  a[i].x/=len;//如果是在进行IDFT,每个复数均除以长度
    	}
    }
    
    signed main(){
    	n=read(),m=read();
    	for (int i=0;i<=n;i++)  a[i].x=read();
    	for (int i=0;i<=m;i++)  b[i].x=read();
    	
    	while (len<=n+m)  len*=2,cnt++;//n必须是2的整数次方,否则单位根就没有上面的性质了
    	for (int i=0;i<len;i++)  r[i]=(r[i>>1]>>1)+((i&1)<<(cnt-1));//数位dp
    	
    	FFT(a,len,1),FFT(b,len,1);//进行两次DFT
    	for (int i=0;i<=len;i++)  a[i]=a[i]*b[i];//点值相乘
    	FFT(a,len,-1);//IDFT
    	
    	for (int i=0;i<=n+m;i++)  cout<<(int)(a[i].x+0.5)<<' ';//保留整数输出
    	return 0;
    }//by ducati
    

    Summary

    可以发现,FFT在优秀的 O ( n log ⁡ n ) O(n \log n) O(nlogn)的复杂度内完成了多项式乘法。同时,它也能应对许多实际问题,这些东西留到多项式学习笔记[三]来详细讲解。

    但是不难发现,FFT中用到了三角函数与double运算,会存在不小的精度误差。同时,对于一些需要取模且在不取模的情况下系数很大的题目,FFT将非常难运行出正确的结果。所以我们需要一个精度更高,能应对取模的多项式乘法算法。

    前置芝士: 原根

    何为原根?

    定义如下: 正整数 g g g是正整数 n n n的原根,当且仅当 1 ≤ g ≤ n − 1 1 \leq g \leq n-1 1gn1 ,且 g g g n n n的阶为 φ ( n ) \varphi(n) φ(n)

    更简单地说,原根 g g g [ 1 , n ) [1,n) [1,n)范围内,且使得 g t g^t gt n n n 1 1 1的自然数 t t t只有 φ ( n ) \varphi(n) φ(n)

    原根有许多优美的性质,这里简要地列出几条:
    (1) g 1 , g 2 ⋯ g φ ( n ) g^1,g^2 \cdots g^{\varphi(n)} g1,g2gφ(n)两两 不同,所以 g g g可以作为在模 n n n意义下 log ⁡ \log log的底数;
    (2)原根的大小在 n 0.25 n^{0.25} n0.25级别。
    (3)令 n n n的最小原根为 p p p,那么所有其他的原根均为 p r ( gcd ⁡ ( r , φ ( n ) ) = 1 ) p^{r}(\gcd(r,\varphi(n))=1) pr(gcd(r,φ(n))=1)在模 n n n意义下的值。

    所以,我们可以采用如下方法计算出一个自然数的所有原根:

    1. 枚举 i ( 1 ≤ i ≤ n − 1 ) i(1 \le i \le n-1) i(1in1)
      (1)对于所有满足 d ∣ φ ( n ) d|\varphi(n) dφ(n)的自然数 d d d,通过快速幂求出 i d i^d id n n n的值 v a l val val
      ①如果 v a l = 1 val=1 val=1 d ≠ φ ( n ) d≠\varphi(n) d=φ(n),那么这个数不是原根;
      ②如果 v a l ≠ 1 val≠1 val=1 d = φ ( n ) d=\varphi(n) d=φ(n),那么这个数不是原根;
      (2)如果这个数是原根,那么令 p = i p=i p=i并退出循环。

    2. 枚举 r r r使得 1 ≤ r ≤ φ ( n ) − 1 1 \le r \le \varphi(n)-1 1rφ(n)1 gcd ⁡ ( φ ( n ) , r ) = 1 \gcd(\varphi(n),r)=1 gcd(φ(n),r)=1,求出 p r p^r pr n n n的值从而得到所有原根。

    一些经典的数的原根如下:
    998244353 998244353 998244353的原根为 3 3 3
    1 0 9 + 7 10^9+7 109+7的原根为 5 5 5

    现在我们已经搞懂了原根已经求法并记得了一些重要的数的原根。但是这东西对多项式乘法有什么用呢?

    NTT

    回顾一下FFT我们是如何定义 w n k w_n^k wnk的。现在,我们将 w n k w_n^k wnk的定义魔改一番 w n k = ( x p − 1 n ) k w_n^k=(x^{\frac {p-1} n})^k wnk=(xnp1)k

    这里的 p p p表示多项式乘法的模数, x x x表示 p p p的一个原根

    这么定义之后,不难发现单位根拥有的所有性质都仍然满足。下面给出证明:

    Lemma 1: n n n个“单位根”两两不同
    Certification 1: 根据原根的定义显然。

    Lemma 2: w n k = w 2 n 2 k w_n^k=w_{2n}^{2k} wnk=w2n2k
    Certification 2: ( x p − 1 2 n ) 2 k = ( x p − 1 n ) k (x^{\frac {p-1} {2n}})^{2k}=(x^{\frac {p-1} n})^k (x2np1)2k=(xnp1)k

    Lemma 3: ( w n k ) n = 1 (w_n^k)^n=1 (wnk)n=1
    Certification 3: ( x p − 1 n ) k n = ( x p − 1 ) k = 1 (x^{\frac {p-1} n})^{kn}=(x^{p-1})^k=1 (xnp1)kn=(xp1)k=1

    Lemma 4.1: w n n 2 = − 1 w_n^{\frac n 2}=-1 wn2n=1
    Certification 4.1:
    ( ( x p − 1 n ) n 2 ) 2 = 1 ((x^{\frac {p-1} n})^{\frac n 2})^2=1 ((xnp1)2n)2=1
    又∵ w n n 2 ≠ w n n w_n^{\frac n 2}≠w_n^n wn2n=wnn
    w n n 2 = − 1 w_n^{\frac n 2}=-1 wn2n=1

    Lemma 4.2: w n k = − w n k − n 2 w_n^k=-w_n^{k-\frac n 2} wnk=wnk2n
    Certification 4.2:

    ( x p − 1 n ) k − n 2 = ( x p − 1 n ) k ( x p − 1 n ) n 2 = w n k − 1 = − w n k (x^{\frac {p-1} n})^{k-\frac n 2}=\frac {(x^{\frac {p-1} n})^k}{(x^{\frac {p-1} n})^{\frac n 2}}=\frac {w_n^k} {-1}=-w_n^k (xnp1)k2n=(xnp1)2n(xnp1)k=1wnk=wnk

    Lemma 5: w n a × w n b = w n a + b w_n^a \times w_n^b=w_n^{a+b} wna×wnb=wna+b
    Certification 5:
    ( x p − 1 n ) a × ( x p − 1 n ) b = ( x p − 1 n ) a + b = w n a + b (x^{\frac {p-1} n})^a \times (x^{\frac {p-1} n})^b=(x^{\frac {p-1} n})^{a+b}=w_n^{a+b} (xnp1)a×(xnp1)b=(xnp1)a+b=wna+b

    综上所述,我们只需要把FFT中所有的 w n k w_n^k wnk的定义改一改,其他的就基本相同了。

    Code: NTT

    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    const int maxl=5000005,mod=998244353;
    const int inv3=(mod+1)/3;//998244353的一个原根是3, 而3在模998244353意义下的值为inv3
    
    int read(){
    	int s=0,w=1;char ch=getchar();
    	while (ch<'0'||ch>'9'){if (ch=='-')  w=-w;ch=getchar();}
    	while (ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^'0');ch=getchar();}
    	return s*w;
    }
    
    int n,m,len=1,cnt;
    int r[maxl],a[maxl],b[maxl];
    
    int quick_power(int x,int y){
    	int res=1;
    	for (;y;y=y>>1,x=(x*x)%mod){
    		if (y&1)  res=(res*x)%mod;
    	}
    	return res;
    }
    
    void NTT(int *a,int len,int flag){
    	for (int i=0;i<=len;i++){
    		if (i<r[i])  swap(a[i],a[r[i]]);
    	}
    	for (int i=2;i<=len;i*=2){
    		int wn=1;
    		if (flag==1)  wn=quick_power(3,(mod-1)/i);
    		else wn=quick_power(inv3,(mod-1)/i);
    		
    		for (int j=0;j<len;j+=i){
    			int w=1;
    			for (int k=j;k<j+(i/2);k++){
    				int u=a[k],v=(w*a[k+(i/2)])%mod;
    				a[k]=(u+v)%mod,a[k+(i/2)]=(u+mod-v)%mod;//注意减法的取模
    				w=(w*wn)%mod;
    			}
    		}
    	}
    	if (flag==-1){
    		int p=quick_power(len,mod-2);//除以一个数相当于乘它的逆元
    		for (int i=0;i<=len;i++)  a[i]=(a[i]*p)%mod;
    	}
    }
    
    signed main(){
    	n=read(),m=read();
    	for (int i=0;i<=n;i++)  a[i]=read();
    	for (int i=0;i<=m;i++)  b[i]=read();
    	
    	while (len<=n+m)  len*=2,cnt++;
    	for (int i=0;i<=len;i++)  r[i]=(r[i>>1]>>1)|((i&1)<<(cnt-1));
    	
    	NTT(a,len,1),NTT(b,len,1);
    	for (int i=0;i<=len;i++)  a[i]=(a[i]*b[i])%mod;
    	
    	NTT(a,len,-1);
    	for (int i=0;i<=n+m;i++)  printf("%lld ",a[i]);
    	return 0;
    }
    

    Summary

    NTT可以应对自如许多取模的多项式乘法题,并且没有精度误差

    但是,我们回顾一下在NTT中 w n k = w_n^k= wnk=的定义 w n k = ( x p − 1 n ) k w_n^k=(x^{\frac {p-1} n})^k wnk=(xnp1)k

    只有当 n ∣ ( p − 1 ) n|(p-1) n(p1)的时候NTT才能正确运行!

    由于 n n n总是 2 2 2的整数次方,所以 p − 1 p-1 p1必须可以写成一个 2 r × d + R 2^r×d+R 2r×d+R的形式,其中 ⌈ log ⁡ 2 n ⌉ + 1 ≤ r \lceil \log_2 n \rceil+1 \le r log2n+1r。对于这一类的模数 p p p我们称之为NTT模数,如:

    167772161 167772161 167772161
    469762049 469762049 469762049
    998244353 998244353 998244353
    1004535809 1004535809 1004535809

    ⋯ ⋯ \cdots \cdots

    很可惜,有的时候模数并不是NTT模数,这导致FFT与NTT都都较难运行出正确的答案。我们需要一个更牛逼的做法来解决这种毒瘤的问题。

    它,有一个好听的名字,叫做任意模数NTT。

    多项式学习笔记[二](全网最详细!有图有代码有解释有例题有总结!)

    展开全文
  • 【数学】有理分式的拆解技巧

    万次阅读 多人点赞 2021-05-12 23:00:48
    通常对于二次或以上的因式最好用 例如: 下面是练习,你们可以试试: 如果分子的次数 ≥ 分母的次数,这是假分式,设法自然会有些改变 这个可依旧运用待定系数: 或者多项式: 图5留数法第二道题解答有点错误...

    【数学】有理分式的拆解技巧

    仅做个人学习总结使用
    参考的文章:
    https://www.jianshu.com/p/1f6025995502
    https://zhuanlan.zhihu.com/p/69471608

    相信大家都不会陌生,经常遇见含有这些分式的积分类型
    现在说说有哪些技巧可以简单应付

    一个真分式,分子的次数 < 分母的次数
    我们把一个真分式拆解为几个小分式,通常第一步会先把分母进行因式分解,然后按照那个因式分裂为小分式

    在这里插入图片描述

    对于小分式,分子的次数 总会 比分母的次数少1次方deg(分子) = deg(分母) - 1
    例如分母是二阶 a x 2 + b x + c ax^2+bx+c ax2+bx+c,则分子为 A x + B Ax+B Ax+B
    若分母是一阶 a x + b ax+b ax+b,则分子为常数A

    不过,对于高阶极点来说,小分式的个数 = 分母的因式个数
    例如 ( x + 5 ) 3 (x + 5)^3 (x+5)3,因式为 ( x + 5 ) 3 (x + 5)^3 (x+5)3 ( x + 5 ) 2 (x + 5)^2 (x+5)2 ( x + 5 ) (x + 5) (x+5),共三个因式
    $(x^2+4 )4,因式为(x2+4)4,(x2+4)3,(x2+4)2,(x^2+4),共四个因式

    在这里插入图片描述

    常用的方法无非都是那几种:
    添项减项法:这个方法对

    1 ( x + a ) ( x + b ) \frac{1}{(x+a)(x+b)} (x+a)(x+b)1

    1 / [ ( x + a ) ( x + b ) ] 1/[(x+a)(x+b)] 1/[(x+a)(x+b)]

    型有效
    待定系数法:即小分式通分后,把分子与原式的分子恒等,从而解出对应系数
    留数法:即通过消去零因式来解出系数,分母要求为线性(ax+b)型因式,可以是高阶极点
    这个方法其实跟z变换类似

    添项减项法 和 待定系数法:

    在这里插入图片描述

    在这里插入图片描述
    留数法:

    在这里插入图片描述

    在这里插入图片描述

    留数法对于一次因式,一阶极点的因式时最好用的
    例如:

    在这里插入图片描述

    而待定系数法,则需要对联立多元方程有很好的运算技巧
    通常对于二次或以上的因式最好用
    例如:

    在这里插入图片描述
    下面是练习,你们可以试试:

    在这里插入图片描述
    如果分子的次数 ≥ 分母的次数,这是假分式,设法自然会有些改变

    在这里插入图片描述
    这个可依旧运用待定系数法:

    在这里插入图片描述
    或者多项式除法:

    在这里插入图片描述

    图5留数法第二道题解答有点错误,应该对A那个式子求导。希望作者更正下。☺☺☺

    https://zhuanlan.zhihu.com/p/69471608

    分解步骤总览:

    1. 判别真假分式.

    2. 真分式分解出待定式.

    3. 待定系数求解方法: 实根法(一次式), 复根法(二次式), 求导法(一次n重), 极限法(一、二次的二重)

    4. 判别真假分式

    形如 P ( x ) Q ( x ) \frac{P(x)}{Q(x)} Q(x)P(x)
    的分式, 若分子指数等于或高于分母, 则要化为真分式.[1]

    化简方法: 做多项式除法[2]

    例如:

    在这里插入图片描述
    2. 真分式分解

    [公式] 重一次因式
    

    形如: P ( x ) ( A x + b ) k \frac{P(x)}{(Ax+b)^k} (Ax+b)kP(x)

    k = 1 k = 1 k=1

    在这里插入图片描述
    其中 A i A_i Ai为待定系数.

    k > 1 k > 1 k>1

    在这里插入图片描述
    例如:

    在这里插入图片描述
    A i , B i , C i A_i, B_i, C_i Ai,Bi,Ci 为待定系数.

    k k k 二次因式

    形如

    P ( x ) ( a x 2 + b x + c ) k \frac{P(x)}{(ax^2+bx+c)^k} (ax2+bx+c)kP(x)

    k = 1 k=1 k=1时,

    在这里插入图片描述
    k > 1 k>1 k>1时,

    在这里插入图片描述
    例如:

    在这里插入图片描述

    1. 待定系数求解[3]

      无特征——反解方程法

    将各项通分合并, 将分子与原式的分子做系数比对, 写出关于待定系数的方程, 进行求解

    多个不同的一次式, 且无重因式——实根代入法

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    展开全文
  • 机器学习-常用回归算法归纳(全网之最)

    千次阅读 多人点赞 2021-10-28 17:31:55
    文章目录前言一元线性回归多元线性回归局部加权线性回归多项式回归Lasso回归 & Ridge回归Lasso回归Ridge回归岭回归和lasso回归的区别L1正则 & L2正则弹性网络回归贝叶斯岭回归Huber回归KNNSVMSVM最大间隔...
  • 【算法】复变函数

    万次阅读 多人点赞 2020-02-18 17:15:40
    复变函数复数与复变函数复数复变函数导数积分级数留数保形映射解析函数对平面向量场的应用 复数与复变函数 复数 复数的代数运算: 复数四则运算的几何意义: ①两个复数乘积的模等于它们模的乘 积;两个复数乘积...
  • 网络通信原理(1)

    2022-04-05 21:21:43
    VLAN ID): 12bit,指明VLAN的ID,共4096个(这里的VLAN和MAC表种的VLAN字段同义) CRC:Cyclic Redundancy Check 循环冗余校验 CRC验证原理 无数日夜小明同学冥思苦想,最终还剩最后三头发之际他学会除,...
  • 计算机考研复试题(近十万字)

    千次阅读 2022-04-03 10:23:16
    什么是地址定位?什么是碎片? 6. 什么是覆盖技术?什么是交换?什么是换入和换出? 7.覆盖技术与虚拟存储技术有何本质不同 ?交换技术与虚存中使用的调入 / 调出技术有何相同 8.什么是虚拟存储器?虚拟存储器基本...
  • 江湖救急笔记——计算机网络

    千次阅读 2022-01-01 14:11:34
    光纤的缺点: (曾经)技术陌生,易损坏 双向传输时需要两光纤,或一光纤上划分两个频段 成本高 三、公共交换电话网络PSTN 1.调制解调器Modem的调制方式 Modem,调制解调器,俗称“猫”。 Modem是用于将数字信号...
  • 常见对称加密、解密、破解

    千次阅读 2021-02-28 10:50:25
    于是我们想到,其实i和s反了,这应该是life和lifes,虽然lifes并不是单词,但是可以拆开,s变成so,这里是一个词组so that 生成新的字母表T2=rltwacmqezvxnhfkjsgidybupo 重新翻译: thereareccents in life when ...
  • ACM 算法模板

    2020-02-07 05:33:37
    ACM 算法模板 Dinic算法求网络流 #include #include <string.h> #include using namespace std; int const inf = 0x3f3f3f3f;...int const MAX = 205;...//dep[MAX]代表当前层 int bfs(in...
  • 两种方法分别在点度数小和深度小的情况下表现优异,考虑合并: 链剖分后每个点只维护轻儿子信息,那么每次修改就只有 l o g log log个点要更新信息 按dfn序建树状数组/线段树,用于维护儿子的贡献,查询时可在 l...
  • 不定积分计算法则总结

    千次阅读 2020-12-23 13:37:13
    本篇幅是关于大部分...TianX:有理函数不定积分计算法则——留数拆分​zhuanlan.zhihu.com结束语 写到最后。以上内容是本人在复习的时候对付不定积分常用的方法,仅供参考。 In The End. Thanks for your reading!
  • 下面解释一下特殊情况的 M > H: 实际上,除了输入数据的通道比较少之外,中间层的feature map很多,这样中间层算卷积会累死计算机(鱼塘太深,每层鱼都打,需要的鱼网太了)。所以很多深度卷积网络把全部...
  • FFT 快速傅里叶变换 初探

    千次阅读 2015-07-14 16:55:34
    一直认为很高深的东西其实也并不很难。以下内容部分来自qy大神的ppt,同时结合了自己的理解。但理解还不是很深,需要继续研究。开头首先什么是傅里叶变换:傅立叶变换...多项式的表示点值表示给出N+1个不同的x代入A
  • 恳求似的 sit [sɪt] (雅思) v,考试,坐下 resit [ˈriːsɪt] (雅思,超级无敌高频) n,v,考、补考 nature [ˈneɪtʃə] (雅思,PTE,超级无敌高频) n,本质,自然,性质,特性 The time spent on an ...
  • 机器学习面试

    千次阅读 2020-06-19 22:55:07
    下面解释一下特殊情况的 M > H: 实际上,除了输入数据的通道比较少之外,中间层的feature map很多,这样中间层算卷积会累死计算机(鱼塘太深,每层鱼都打,需要的鱼网太了)。所以很多深度卷积网络把全部...
  • 2020 HDU多校联合训练

    2020-08-28 11:59:05
    坑之后写一写 1006 Finding a MEX 02:59:09(-4) 直接暴力的话查询最坏是 O(n)O(n)O(n),但是修改是 O(1)O(1)O(1)的。 考虑平衡复杂度,设阀值为 BBB。 注意到查询复杂度只与度数有关,而度数大于 BBB的点最多有 ...
  • 2019年一月刷题列表

    2019-01-05 23:40:00
    我们可以直接暴力求出\(m\)的原,然后把所有都用原转化到指数的位置,这样相乘就对应着指数的相加了。最后注意下标也是在模\(m\)意义下的,要时刻注意复制走。 sol Luogu P4238 【模板】多项式求逆 多项式全家...
  • 深度学习基础知识整理

    千次阅读 2018-10-20 09:09:50
    本文是在七月的BAT机器学习面试1000题系列进行修改。&amp;nbsp; 前言 ... 之前本博客整理过千道微软等公司的面试题,侧重数据结构、算法、海量数据处理,详见:微软面试100题系列,今17年,近...
  • 数论大杂烩

    2018-04-15 20:21:21
    ,可以发现,每一个这样的二元组表示,都能与一个 \sum_{i|p^{k_1}} \sum_{j|p^{k_2}} \sum_{i|p^{k_1}} \sum_{j|p^{k_2}} 相对应,因此对于一个质数的情况成立 考虑合数的情况,其实就是将很多质数相乘。对于...
  • 斯特林是把p次多项式线性空间的两组基:A=(1,x,x 2 ,…,x p ) , B=(1,[x] 1 ,…,[x] p )相互变换的系数。 其中,第一类斯特林的是:A到B,即下降(上升)幂,到x p ,第二类斯特林是B到A,即x p 到降(上升...
  • 一场CF的台前幕后(上)

    千次阅读 2019-05-24 19:38:14
    ……然后各种毒瘤属性爆发:“谁来造个E吧-_-||……出抽代怎么样-_-||……多项式多项式素性检测!”   第二天pyx造了个题: 两个人玩游戏,每回合每个人可以选择:攻击,防御,蓄力。蓄力能增加1...
  • 2019寒假小记

    2019-01-27 22:27:00
    多项式 啊,但是我连板子都不会。 然后发现还要模数 \(10^9+7\) 的情况,岂不是要 任意模数NTT ,弃了弃了。 手速码了个暴力开始找规律,看到 \(a_0=a_1=1\) 的那个 \(1,1,2,5,14\) 的东西就知道是个 卡特兰...
  • 2018十二月刷题列表

    2018-12-01 22:08:00
    ,然后从开始求异或前缀和最后看有相同的的对数即可。 Luogu P3723 [AH2017/HNOI2017]礼物 考虑只对第一个手环加 \(m\) (这样 \(m\) 可以为负,相当于在第二个手环加),最后就是最小化 \(\sum_{i=1}^n (x_i...

空空如也

空空如也

1 2 3 4
收藏数 62
精华内容 24
热门标签
关键字:

留数法拆开重根多项式

友情链接: xueshengxinxi-xitong.zip