精华内容
下载资源
问答
  • 切比雪夫多项式证明
    千次阅读
    2021-03-15 16:32:08

    切比雪夫多项式.

    • 切比雪夫,俄文原名 П а ф н у ˊ т и й Л ь в о ˊ в и ч Ч е б ы ш ё в Пафну́тий Льво́вич Чебышёв ПафнуˊтийЛьвоˊвичЧебышёв ,俄罗斯数学家、力学家。初次接触是在概率论中,他提出了切比雪夫不等式。

    设随机变量 X X X 具有数学期望 E [ X ] = μ E[X]=\mu E[X]=μ 与方差 D ( X ) = σ 2 D(X)=\sigma^2 D(X)=σ2,则对任意正数 ϵ > 0 \epsilon>0 ϵ>0,有不等式 P { ∣ X − μ ∣ < ϵ } ≥ 1 − ( σ ϵ ) 2 . P\{|X-\mu|<\epsilon\}≥1-(\frac{\sigma}{\epsilon})^2. P{Xμ<ϵ}1(ϵσ)2.


    • 定义】多项式序列 T n ( x ) = c o s ( n ⋅ a r c c o s x ) , x ∈ [ − 1 , 1 ] T_n(x)=cos(n·arccosx),x\in[-1,1] Tn(x)=cos(narccosx),x[1,1] 称为切比雪夫多项式。

    • { T n ( x ) } \{T_n(x)\} {Tn(x)} 在区间 [ − 1 , 1 ] [-1,1] [1,1] 上带权函数 ρ ( x ) = ( 1 − x 2 ) − 1 \rho(x)=(\sqrt{1-x^2})^{-1} ρ(x)=(1x2 )1 正交。
    • ( T n , T m ) = ∫ − 1 1 1 1 − x 2 c o s ( n ⋅ a r c c o s x ) c o s ( m ⋅ a r c c o s x ) d x = { 0 , n ≠ m π 2 , n = m > 0 π , n = m = 0 ; n , m = 0 , 1 , 2 , . . . (T_n,T_m)=\int_{-1}^1\frac{1}{\sqrt{1-x^2}}cos(n·arccosx)cos(m·arccosx)dx=\left\{ \begin{aligned} &0,n≠m\\ &\frac{\pi}{2},n=m>0 \\ &\pi,n=m=0 \end{aligned} \right.;n,m=0,1,2,... (Tn,Tm)=111x2 1cos(narccosx)cos(marccosx)dx=0,n=m2π,n=m>0π,n=m=0;n,m=0,1,2,...
    • 证明】进行代换 x = c o s θ x=cos\theta x=cosθ,则 θ = a r c c o s x \theta=arccosx θ=arccosx,因此上式中的积分可以写为 ∫ − 1 1 1 s i n θ ⋅ c o s n θ ⋅ c o s m θ ⋅ d ( c o s θ ) = ∫ 0 π c o s n θ ⋅ c o s m θ ⋅ d θ . \int_{-1}^1\frac{1}{sin\theta}·cosn\theta·cosm\theta·d(cos\theta)=\int_0^\pi cosn\theta·cosm\theta·d\theta. 11sinθ1cosnθcosmθd(cosθ)=0πcosnθcosmθdθ.

    • 和勒让德多项式一样,当 n n n 为偶数时, T n ( x ) T_n(x) Tn(x) 是偶函数;当 n n n 为奇数时, T n ( x ) T_n(x) Tn(x) 是奇函数,即 T n ( − x ) = ( − 1 ) n T n ( x ) . T_n(-x)=(-1)^nT_n(x). Tn(x)=(1)nTn(x).
    • 证明 T n ( − x ) = c o s [ n ⋅ a r c c o s ( − x ) ] = c o s [ n ⋅ ( π − a r c c o s x ) ] = c o s ( n π ) c o s ( n ⋅ a r c c o s x ) + s i n ( n π ) s i n ( n ⋅ a r c c o s x ) = c o s ( n π ) c o s ( n ⋅ a r c c o s x ) = ( − 1 ) n c o s ( n ⋅ a r c c o s x ) . T_n(-x)=cos[n·arccos(-x)]=cos[n·(\pi-arccosx)]=cos(n\pi) cos(n·arccosx)+sin(n\pi)sin(n·arccosx)=cos(n\pi) cos(n·arccosx)=(-1)^ncos(n·arccosx). Tn(x)=cos[narccos(x)]=cos[n(πarccosx)]=cos(nπ)cos(narccosx)+sin(nπ)sin(narccosx)=cos(nπ)cos(narccosx)=(1)ncos(narccosx).

    • 切比雪夫多项式可以由如下递推式定义: { T 0 ( x ) = 1 T 1 ( x ) = x T n + 1 ( x ) = 2 x T n ( x ) − T n − 1 ( x ) , n = 1 , 2 , . . . \left\{ \begin{aligned} &T_0(x)=1\\ &T_1(x)=x\\ &T_{n+1}(x)=2xT_n(x)-T_{n-1}(x),n=1,2,... \end{aligned} \right. T0(x)=1T1(x)=xTn+1(x)=2xTn(x)Tn1(x),n=1,2,...
    • 证明】依旧使用代换 x = c o s θ x=cos\theta x=cosθ,那么 T n ( x ) = c o s ( n θ ) T_n(x)=cos(n\theta) Tn(x)=cos(nθ),由于 c o s [ ( n + 1 ) θ ] = c o s ( n θ ) c o s θ − s i n ( n θ ) s i n θ ; c o s [ ( n − 1 ) θ ] = c o s ( n θ ) c o s θ + s i n ( n θ ) s i n θ cos[(n+1)\theta]=cos(n\theta)cos\theta-sin(n\theta)sin\theta;cos[(n-1)\theta]=cos(n\theta)cos\theta+sin(n\theta)sin\theta cos[(n+1)θ]=cos(nθ)cosθsin(nθ)sinθ;cos[(n1)θ]=cos(nθ)cosθ+sin(nθ)sinθ,两式相加得到 c o s [ ( n + 1 ) θ ] + c o s [ ( n − 1 ) θ ] = 2 c o s ( n θ ) c o s θ . cos[(n+1)\theta]+cos[(n-1)\theta]=2cos(n\theta) cos\theta. cos[(n+1)θ]+cos[(n1)θ]=2cos(nθ)cosθ. T n + 1 ( x ) = 2 x T n ( x ) − T n − 1 ( x ) . T_{n+1}(x)=2xT_n(x)-T_{n-1}(x). Tn+1(x)=2xTn(x)Tn1(x).

    带权内积.

    • 在区间 [ − 1 , 1 ] [-1,1] [1,1] 定义带权函数 ρ ( x ) = 1 1 − x 2 \rho(x)=\frac{1}{\sqrt{1-x^2}} ρ(x)=1x2 1 的内积: ( f , g ) = ∫ − 1 1 f ( x ) ⋅ g ( x ) 1 − x 2 d x . (f,g)=\int_{-1}^1\frac{f(x)·g(x)}{\sqrt{1-x^2}}dx. (f,g)=111x2 f(x)g(x)dx.相应地,诱导出范数 ∣ ∣ f ∣ ∣ 2 = ∫ − 1 1 f 2 ( x ) 1 − x 2 d x . ||f||^2=\int_{-1}^1\frac{f^2(x)}{\sqrt{1-x^2}}dx. f2=111x2 f2(x)dx.
    • 例如求解如下问题:尝试确定参数 a , b , c a,b,c a,b,c 使得 I ( x ; a , b , c ) = ∫ − 1 1 [ 1 − x 2 − a x 2 − b x − c ] 2 ⋅ 1 1 − x 2 d x I(x;a,b,c)=\int_{-1}^1[\sqrt{1-x^2}-ax^2-bx-c]^2·\frac{1}{\sqrt{1-x^2}}dx I(x;a,b,c)=11[1x2 ax2bxc]21x2 1dx取得最小值。
    • 上述问题的本质就是在 [ − 1.1 ] [-1.1] [1.1] 上求 f ( x ) = 1 − x 2 f(x)=\sqrt{1-x^2} f(x)=1x2 关于权函数 1 1 − x 2 \frac{1}{\sqrt{1-x^2}} 1x2 1 的二次最佳平方多项式。
    更多相关内容
  • 切比雪夫多项式

    万次阅读 2019-05-20 17:36:16
    定理1:对于任意正整数n,存在多项式与,且满足等式 ...并且与都是整系数多项式,首项系数分别为与,与成为切比雪夫多项式。 定理2: 满足递推关系式 满足递推关系式 佩尔方程的定义:...

    定理1:对于任意正整数n,存在多项式T_{n}(x)U_{n}(x),且满足等式

                                      \left\{\begin{matrix} T_{n}(cos\theta )=cosn\theta \\ U_{n}(cos\theta )=\frac{sin(n+1)\theta }{sin\theta } \end{matrix}\right.

    并且T_{n}(x)U_{n}(x)都是整系数多项式,首项系数分别为2^{n-1}2^{n}T_{n}(x)U_{n}(x)成为切比雪夫多项式。

    定理2:

    T_{n}(x)满足递推关系式

                                     T_{n+1}(x)=2xT_{n}(x)-T_{n-1}(x)

    U_{n}(x)满足递推关系式

                                      U_{n}(x)=xU_{n-1}(x)+T_{n}(x)

    佩尔方程的定义:

     若一个不定方程具有这样的形式:x^{2}-ny^{2}=1,则称此二元二次方程为佩尔方程。

    切比雪夫多项式可以转换成佩尔方程的形式,令x=cos\theta,

                     则T_{n}(x)=cosn\theta ,U_{n-1}(x)\cdot sin\theta =sinnx

                                  则T_{n}^{2}(x)-(1-x^{2})U_{n-1}^{2}(x)=1

    因此多项式的解,可以通过解佩尔方程来求解。

    更多文章请关注公众号<<音频核>>

     

    展开全文
  • 为了避免宽带匹配中的不精确设计,提出了宽带匹配设计公式的择优性以及切比雪夫多项式匹配极限情况与二项式匹配的等价性。通过理论推导和案例设计证明了择优性和等价性的正确性,最后结果表明宽带匹配的这两个性质对...
  • 切比雪夫多项式也叫切比雪夫混沌映射,起源于多倍角的余弦函数和正弦函数的展开式,是计算数学中一类特殊的函数。扩展切比雪夫多项式(Extended Chebyshev Polynomials, ECP),也有叫作扩展切比雪夫混沌映射...

            切比雪夫多项式也叫切比雪夫混沌映射,起源于多倍角的余弦函数和正弦函数的展开式,是计算数学中一类特殊的函数。 扩展切比雪夫多项式(Extended Chebyshev Polynomials, ECP),也有叫作扩展切比雪夫混沌映射(Extended Chebyshev chaotic map),是切比雪夫多项式(混沌映射)参数x在\left ( -\infty ,+\infty \right )上的扩展。

            切比雪夫多项式定义:设n,x为变量且满足n \in Z^{*}, \forall x \in[-1,1],n阶切比雪夫多项式T_{n}(x):[-1,1] \rightarrow[-1,1]的余弦式定义为:T_{n}(x)=\cos (n \cdot \arccos (x))。当n\geq 2时,等价的递归迭代定义为:T_{n}(x)=2 x T_{n-1}(x)-T_{n-2}(x),其中T_{0}(x)=1, T_{1}(x)=x

             切比雪夫多项式的半群性质:\forall m, n \in Z^{*}, T_{m}\left(T_{n}(x)\right)=T_{n}\left(T_{m}(x)\right)=T_{m n}(x)

            2008年,Zhang证明了切比雪夫多项T_{n}(x)中变量x的取值范围扩展到区间(-\infty, \infty)后,T_{n}(x)仍然具有半群性质并且可以有效抵抗Bergamo攻击。

            扩展切比雪夫多项式定义:设n,x为变量且满足n \in Z^{*}, \forall x \in(-\infty, \infty),n阶扩展切比雪夫多项式的余弦式定义为:T_{n}(x)=\cos (n \cdot \arccos (x))(\bmod p)。当n\geq 2时,等价的递归迭代定义为:T_{n}(x)=\left(2 x T_{n-1}(x)-T_{n-2}(x)\right) \bmod p。其中T_{0}(x)=1, T_{1}(x)=x,p是一个大素数。

            扩展切比雪夫多项式的半群性质:若已知T_{n}(x), x的值,求解阶数n的问题称为切比雪夫离散对数问题。CDLP属于计算难问题,在常规多项式线性时间内是无法计算出阶数n。

             切比雪夫离散对数问题(Chebyshev Discrete Logarithm Problem,CDLP):若已知T_{n}(x), x的值,求解阶数n的问题称为切比雪夫离散对数问题。CDLP属于计算难问题,在常规多项式线性时间内是无法计算出阶数n。

            切比雪夫迪菲-赫尔曼问题(Chebyshev Diffie-Hellman Problem,CDHP):若已知T_{n}(x), T_{m}(x), x的值,求解T_{m \cdot n}(x)的值的问题称为切比雪夫迪菲-赫尔曼问题。CDHP属于计算难问题,不能在常规的多项式线性时间内得到有效解决。

            研究现状:

            2015年,Lee等人针对智能卡的安全问题提出了一种基于ECP的口令认证密钥协商协议,但该协议不能有效抵御模仿攻击。同年,为保障远程医疗信息系统的安全,Lu等人结合生物特征识别技术提出了一种基于ECP的口令认证密钥协商协议,但Masdari等人在其调研中证明了Lu等人的方案不能抵抗模仿攻击。2016年,Kumari等人在无线传感网领域提出了一种基于ECP的用户友好认证密钥协商协议,该协议具有双向认证性和完美前向安全性,并提供登录时错误标识符检测机制,但在Ferrag等人和El-hajj等人的调查研究中均指出Kumari等人的协议不具备消息完整性,也无法抵抗已知会话特定临时信息攻击和抗模仿攻击。2017年,针对安全读取远程智能电表数据问题,Sha等人设计实现了一种基于ECP的两阶段认证密钥协商协议,第一阶段智能电表读取器和云端电力服务器通过数字签名进行认证,验证通过后获得一次性的对称密钥,该密钥用于第二阶段智能电表读取器和远程电力设备间的认证和密钥协商。2018年,Abbasinezhad-Mood等人在其研究中证明了Sha等人的协议缺乏完美前向安全性,然后提出了一种能高效安全地获取远程电力设备数据的匿名认证密钥协商协议,但该协议无法抵抗内部特权攻击也不具备匿名性。2019年,Pak等人在研究中首先指出Kumari等人的协议无法抵抗已知会话特定临时信息攻击和抗模仿攻击,然后又详细论证了Lu等人所提协议不能满足匿名性以及口令更新阶段的安全性,最后结合用户的生物特征和口令提出了一种基于ECP的智能卡认证密钥协商协议,保障了数据的完整性,但无法保障匿名性,也不能抵抗重放攻击和已知会话特定临时信息攻击。同年,Jabbari等人提出了一种基于ECP的无口令的认证密钥协商协议,但该协议不具备匿名性,也不能抵抗重放攻击和已知会话特定临时信息攻击。

            参考文献:

    1. Lee T F. Enhancing the security of password authenticated key agreement protocols based on chaotic maps[J]. Information Sciences, 2015, 290: 63-71.
    2. Lu Y, Li L, Peng H, et al. Robust and efficient biometrics based password authentication scheme for telecare medicine information systems using extended chaotic maps[J]. Journal of medical systems, 2015, 39(6): 1-10.
    3. Masdari M, Ahmadzadeh S. A survey and taxonomy of the authentication schemes in Telecare Medicine Information Systems[J]. Journal of Network and Computer Applications, 2017, 87: 1-19.
    4. Kumari S, Li X, Wu F, et al. A user friendly mutual authentication and key agreement scheme for wireless sensor networks using chaotic maps[J]. Future Generation Computer Systems, 2016, 63: 56-75.
    5. Ferrag M A, Maglaras L A, Janicke H, et al. Authentication protocols for internet of things: a comprehensive survey[J]. Security and Communication Networks, 2017, 2017.
    6. El-hajj M, Fadlallah A, Chamoun M, et al. A survey of internet of things (IoT) Authentication schemes[J]. Sensors, 2019, 19(5): 1141.
    7. Sha K, Alatrash N, Wang Z. A secure and efficient framework to read isolated smart grid devices[J]. IEEE Transactions on Smart Grid, 2016, 8(6): 2519-2531.
    8. Abbasinezhad-Mood D, Nikooghadam M. Efficient anonymous password-authenticated key exchange protocol to read isolated smart meters by utilization of extended Chebyshev chaotic maps[J]. IEEE Transactions on Industrial Informatics, 2018, 14(11): 4815-4828.
    9. Pak K, Pak S, Ho C, et al. Anonymity preserving and round effective three-party authentication key exchange protocol based on chaotic maps[J]. PloS one, 2019, 14(3): e0213976.
    10. Jabbari A, Mohasefi J B. Improvement in new three-party-authenticated key agreement scheme based on chaotic maps without password table[J]. Nonlinear Dynamics, 2019, 95(4): 3177-3191.
    11. Zhang L . Cryptanalysis of the public key encryption based on multiple chaotic systems[J]. Chaos Solitons & Fractals, 2008, 37(3):669-674.
    12. Chatterjee S, Roy S, Das A K, et al. Secure biometric-based authentication scheme using Chebyshev chaotic map for multi-server environment[J]. IEEE Transactions on Dependable and Secure Computing, 2016, 15(5): 824-839.
    13. Lee T F. Provably secure anonymous single-sign-on authentication mechanisms using extended Chebyshev chaotic maps for distributed computer networks[J]. IEEE Systems Journal, 2015, 12(2): 1499-1505.
    14. Burrows M, Abadi M, Needham R M. A logic of authentication[J]. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 1989, 426(1871): 233-271.
    15. Blanchet B. An efficient cryptographic protocol verifier based on prolog rules[C]//csfw. 2001, 1: 82-96.
    16. Lee C C, Li C T, Chiu S T, et al. A new three-party-authenticated key agreement scheme based on chaotic maps without password table[J]. Nonlinear Dynamics, 2015, 79(4): 2485-2495.
    17. Cui J, Wang Y, Zhang J, et al. Full Session Key Agreement Scheme Based on Chaotic Map in Vehicular Ad Hoc Networks[J]. IEEE Transactions on Vehicular Technology, 2020, 69(8): 8914-8924.
    18. Abbasinezhad-Mood D, Ostad-Sharif A, Nikooghadam M, et al. Novel certificateless Chebyshev chaotic map-based key agreement protocol for advanced metering infrastructure[J]. The Journal of Supercomputing, 1-29.
    19. Kumar A, Om H. An enhanced and provably secure authentication protocol using Chebyshev chaotic maps for multi-server environment[J]. Multimedia Tools and Applications, 2021: 1-27.
    20. Zhang L, Zhu S, Tang S. Privacy protection for telecare medicine information systems using a chaotic map-based three-factor authenticated key agreement scheme[J]. IEEE journal of biomedical and health informatics, 2016, 21(2): 465-475.

            

    展开全文
  • 切比雪夫多项式   概述: 切比雪夫多项式是与棣美弗定理有关,以递归方式定义的一系列正交多项式序列。 通常,第一类切比雪夫多项式以符号Tn表示, 第二类切比雪夫多项式用Un表示。切比雪夫多项式 Tn 或 Un 代表...

    切比雪夫多项式

     

    概述:

    切比雪夫多项式是与棣美弗定理有关,以递归方式定义的一系列正交多项式序列。 通常,第一类切比雪夫多项式以符号Tn表示, 第二类切比雪夫多项式用Un表示。切比雪夫多项式 Tn 或 Un 代表 n 阶多项式。

    切比雪夫多项式在逼近理论中有重要的应用。这是因为第一类切比雪夫多项式的根(被称为切比雪夫节点)可以用于多项式插值。相应的插值多项式能最大限度地降低龙格现象,并且提供多项式在连续函数的最佳一致逼近。

     

    基本性质:

    对每个非负整数n, Tn(x) 和 Un(x) 都为 n次多项式。 并且当n为偶(奇)数时,它们是关于x 的偶(奇)函数, 在写成关于x的多项式时只有偶(奇)次项。

     

    按切比雪夫多项式的展开式:

    一个N 次多项式按切比雪夫多项式的展开式为如下,多项式按切比雪夫多项式的展开可以用 Clenshaw 递推公式计算。第一类切比雪夫多项式由以下递推关系确定。

     

    也可以用母函数表示。

     

    第二类切比雪夫多项式 由以下递推关系给出。

     

    此时母函数为

     

    Clenshaw递推公式

    在数值分析中,Clenshaw递推公式 (由Charles William Clenshaw发现)是一个求切比雪夫多项式的值的递归方法。

     

    切比雪夫多项式

    N次切比雪夫多项式,是下面形式的多项式p(x)

     

     

    其中Tnn阶切比雪夫多项式

     

    Clenshaw递推公式

    Clenshaw递推公式可以用来计算切比雪夫多项式的值。给定

     

     

    我们定义

     

    于是

     

     

    (注)上面的公式在 N=0,1的情况下无意义。此时我们可以用下面的公式:

     

    (downward, omit if N=0)

     

    这里

    或者

     

    其中是第二类切比雪夫多项式

    棣莫弗(de Moivre)原理

      设两个复数(用三角形式表示)Z1=r1(cosθ1+isinθ1),Z2=r2(cosθ2+isinθ2),则:

      Z1Z2=r1r2[cos(θ1+θ2)+isin(θ1+θ2)].

    解析

      证:先讲一下复数的三角形式的概念。在复平面C上,用向量Z(a,b)来表示Z=a+bi.于是,该向量可以分成两个在实轴,虚轴上的分向量.如果向量Z与实轴的夹角为θ,这两个分向量的模分别等于rcosθ,risinθ(r=√a^2+b^2).所以,复数Z可以表示为Z=r(cosθ+isinθ).这里θ称为复数Z的辐角.

      因为Z1=r1(cosθ1+isinθ1),Z2=r2(cosθ2+isinθ2),所以

      Z1Z2=r1r2(cosθ1+isinθ1)(cosθ2+isinθ2)

      =r1r2(cosθ1cosθ2+icosθ1sinθ2+isinθ1cosθ2-sinθ1sinθ2)

      =r1r2[(cosθ1cosθ2-sinθ1sinθ2)+i(cosθ1sinθ2+sinθ1cosθ2)]

      =r1r2[cos(θ1+θ2)+isin(θ1+θ2)].

      其实该定理可以推广为一般形式:

    推广

      设n个复数Z1=r1(cosθ1+isinθ1),Z2=r2(cosθ2+isinθ2),……,Zn=rn(cosθn+isinθn),则:

      Z1Z2……Zn=r1r2……rn[cos(θ1+θ2+……+θn)+isin(θ1+θ2+……+θn)].

    解析

      证:用数学归纳法即可,归纳基础就是两个复数相乘的棣莫弗定理。

      如果把棣莫弗定理和欧拉(Euler)公式“e^iθ=cosθ+isinθ”(参见《泰勒公式》,严格的证明需要复分析)放在一起看,则可以用来理解欧拉公式的意义。

      利用棣莫弗定理有:

      Z1Z2……Zn=r1r2……rn [cos(θ1+θ2+……+θn)+isin(θ1+θ2+……+θn)]

      如果可以把所有的复数改写成指数的形式,即:Z1=r1e^iθ1,Z2=r2e^iθ2,……,Zn=rne^iθn,

      Z1Z2……Zn=r1r2……rn e^i(θ1+θ2+……+θn)

      这和指数的可加性一致.

      在一般形式中如果令Z1=Z2=……=Zn=Z,则能导出复数开方的公式.有兴趣可自己推推看.

    下面这题可作为切比雪夫多项式的模版:

    Trig Function

    TimeLimit: 2000/1000 MS (Java/Others)    Memory Limit:32768/32768 K (Java/Others)
    Total Submission(s): 714    Accepted Submission(s): 206

    Problem Description

     

    f(cos(x))=cos(n∗x) holds for all x.

    Given two integersn and m , you need to calculate the coefficient of x^m​​ in f(x), modulo 998244353

     

      

    Input

     

    Multiple testcases (no more than 100).

    Each test casecontains one line consisting of two integers n and m.

    1≤n≤109,0≤m≤104

     

      

    Output

    Output the answerin a single line for each test case.

      

    Sample Input

    2 0

    2 1

    2 2

     

    Sample Output

    998244352

    0

    2


    【题意】

    给出一个函数,代入n,m后求出xm的系数,并取模输出。


    【思路】


    我们先尝试把cos(nx)化为cos(x)的形式,然后把cos(x)用x代换,就可以得到f(x)=...的形式,然后就能得到所求的系数了。


    那么我们如何把cos(nx)化为cos(x)的形式呢。


    其实可以尝试着暴力写出前几项的形式。如下图:

     

    由写出的式子,我们可以发现以下几点:

    1. 当m大于n时,答案显然为0。
    2. 当n为奇数且m为偶数或n为偶数且m为奇数时答案显然为0。
    3. 当n为奇数,且m为1时,答案的绝对值为n。
    4. 当n为偶数,且m为0时,答案的绝对值为1。
    5. 其余情况答案的绝对值均为【 n * (n-m+2) * (n-m+4) * ... * (n+m-4) * (n+m-2) 】/(m!)。(注意逆元的运用)
    6. 上面出现绝对值的情况,3和4 当(n/2)%2 == 0 时符号为正,否则为负;5 当((n-m)/2)%2 == 0时,符号为正,否则符号为负。

    依照这个规律分类讨论一下即可。

    于是我们可以得到以下一般解析式

    注意"!!"不是阶乘的阶乘,而是不超过n且与n具有相同奇偶性的所有正整数连乘积。

    n分类讨论下,当n为偶数时m=2*k, n为奇数时m=2*k-1

    还有注意下"!!"的约分,可能下面的比上面的大

    于是我们就得到了以下代码:

     1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 const int maxn=1e5+5;
     5 const int mod=998244353;
     6 ll fac[maxn]={1};
     7 ll n,m;
     8 void init()
     9 {
    10     for(int i=1;i<maxn;i++)
    11         fac[i]=fac[i-1]*i%mod;
    12 }
    13 ll qmod(ll x,int q)
    14 {
    15     ll res=1;
    16     while(q)
    17     {
    18         if(q%2)
    19             res=res*x%mod;
    20         x=x*x%mod;
    21         q/=2;
    22     }
    23     return res;
    24 }
    25 int main(void)
    26 {
    27     init();
    28     while(~scanf("%lld%lld",&n,&m))
    29     {
    30         if(m>n)
    31             puts("0");
    32         else if(n%2&&m%2==0)
    33             puts("0");
    34         else if(n%2==0&&m%2)
    35             puts("0");
    36         else
    37         {
    38             ll fz=n%mod;
    39             if(m>=1)
    40             {
    41                 for(int i=n-m+1;i<=n+m-1;i++)
    42                 {
    43                     if(i%2==(n+m-2)%2)
    44                     {
    45                         fz=fz*i%mod;
    46                     }
    47                 }
    48                 ll tmp=fz*qmod(fac[m],mod-2)%mod;
    49                 if((n-m)/2%2)
    50                     tmp=-tmp;
    51                 printf("%lld\n",(tmp+mod)%mod);
    52             }
    53             else
    54             {
    55                 ll t=1;
    56                 for(int i=n+m-1;i<=n-m;i++)
    57                 {
    58                     if(i%2==(n+m-2)%2)
    59                         t=t*i%mod;
    60                 }
    61                 ll tmp=fz*qmod(fac[m],mod-2)%mod*qmod(t, mod-2)%mod;
    62                 if((n-m)/2%2)
    63                     tmp=-tmp;
    64                 printf("%lld\n",(tmp+mod)%mod);
    65             }
    66         }
    67     }
    68 }

     

    展开全文
  • 切比雪夫插值

    千次阅读 2019-12-23 21:46:24
    事实证明,基点间距选取的方式对于插值误差有很大的影响,切比雪夫插值是一种特定最优的点间距选取方式。 理论分析 切比雪夫理论 切比雪夫插值的动机是在插值区间上,提高对如下插值误差(如:牛顿差商公...
  • 切比雪夫定理的证明

    千次阅读 2019-09-26 23:56:01
    证明过程,其中包含了对初等函数的定义、对阿贝尔积分的一些初步探讨、刘维尔的一个初等可积判断定理和最终切比雪夫关于二项微分式积分 初等可积性 的定理。 切比雪夫定理 :设 \[\int x^m(a+bx^n)^p\mathrm{d...
  • 切比雪夫不等式证明及应用

    千次阅读 2021-11-26 19:17:12
    切比雪夫不等式
  • (题图为第一类切比雪夫多项式的图像)大家好!今天给大家带来一个难度相对较大的内容:切比雪夫最佳逼近直线。这个内容在浙江省和江苏省考得比较多,其它考区不太清楚,听说全国卷不等式都是放在“不等式选讲”里面...
  • 基于切比雪夫正交多项式,有人提出了第一类与第二类切比雪夫核函数,文章用反例证明了所提出的第二类切比雪夫核函数不是核函数,并重新建立了第二类切比雪夫核函数。并在双螺旋集和标准UCI数据集上与第一类切比雪夫核及...
  • 鉴于此,对一元切比雪夫神经网络进行扩展,提出了多元切比雪夫神经网络模型,并在切比雪夫多项式正交性的基础上给出了快速权值确定算法。仿真实验证明,相对于传统多层感知器神经网络,该方法在计算精度和计算速度等...
  • 《数值分析》-- 正交多项式

    千次阅读 2021-12-04 14:37:08
    正交多项式,勒让德多项式,切比雪夫多项式
  • 多项式拟合

    2020-12-31 12:39:44
    另一种方法是利用切比雪夫节点求出函数值后再使用正交多项式。这两种方法都使正规方程 组的系数矩阵为对角矩阵,从而避免了正规方程组的病态。我们只介绍第一种,见第三节。 例如 m=19,=328,h=1, =+ih,i=0,1,…,...
  • 我们进一步证明,与一阶朴素模型(等式6)或使用切比雪夫多项式的高阶图卷积模型(等式5)相比,所提出的重标准化化传播模型(等式8)在许多数据集上提供了更高的效率(更少的参数和操作,如乘法或加法)和更好的...
  • 切比雪夫阻抗变换器设计与仿真

    千次阅读 2021-04-05 09:51:12
    一、切比雪夫阻抗变换器简介   阻抗变换器是一种常用的双端口元件,通过插入阻抗变换器可以消除因负载和传输线特性阻抗不 匹配而产生的反射.理论上说,一段 1/4 波长的均匀传输线就可以实现阻抗变换的功能,但...
  • 最佳平方逼近多项式

    万次阅读 2008-10-09 09:55:00
    一 内积与正交多项式定义1 设 , 是[a,b]上的权函数,记 (1)称为函数 上带权 的内积。内积具有以下性质:① 对称性 ;② 齐次性 ;③ 可加性 ;④ 非负性 ,且 当且仅当 , x∈[a,b]。定义2...
  • 针对此方案,分析了其存在的缺陷,包括易遭受用户模仿攻击、离线字典攻击、无法提供用户匿名性,以及注册阶段及口令修改阶段存在设计缺陷,由此提出了一个改进的基于混沌映射(切比雪夫多项式)的移动端认证协议来...
  • 简要介绍切比雪夫近似值的概念,并给出常见编程语言计算正弦和余弦函数使用切比雪夫近似值。
  • 数值分析(8)-最佳一致逼近多项式

    万次阅读 2019-06-07 14:01:03
    1. 误差 2. 多项式插值与样条插值 3. 函数逼近 4. 数值积分与数值微分 5. 线性方程组的直接解法 6. 线性方程组的迭代解法 7. 非线性方程求根 8. 特征值和特征向量的计算 9. 常微分方程初值问题的数值解
  • 常态和偏微分方程的时频解通常被认为是一种无效的方法。 与有限差分方法相比,时域的相关扩展被认为会导致许多数值运算... 对于MHD方程,证明了有利的子域缩放,这表明有效解决例如流体力学和MHD中高级初值问题的潜力。
  • 本文主要介绍插值与多项式逼近的数值计算方法,首先介绍几种常用的多项式逼近的方法与原理,包括泰勒多项式逼近、拉格朗日多项式逼近、切比雪夫多项式逼近和帕德多项式逼近,并分析他们各自逼近的优良程度。...
  • 为了使用户可以更加安全高效地访问服务,基于扩展切比雪夫混沌映射提出了一种新的单点登录认证协议,并证明了其安全性。方案中用户和云端应用服务器利用身份信息生成公、私钥对,并结合DH密钥交换思想进行双向认证。...
  • 为了能够更好地求解该类反问题,本文首先证明解的唯一性,然后给出其离散后的有限差分格式以及该格式下的数值解的稳定性条件,并通过切比雪夫多项式逼近未知函数,利用最小二乘法解出未知项的系数,最后给出数值试验。
  • 为了满足大规模数据集快速离群数据检测的需求,本文提出了一种新的无线传感器网络离群时间序列检测算法,通过引入切比雪夫多项式实现离群数据快速检测。通过NS2仿真实验,证明了该算法的可行性和有效性。
  • 最小二乘法的基本原理和多项式拟合 一 最小二乘法的基本原理 从整体上考虑近似函数 同所给数据点 (i=0,1,…,m)误差 (i=0,1,…,m)的大小,常用的方法有以下三种:一是误差 (i=0,1,…,m)绝对值的最大值 ,...
  • 与R(x)形式一致,deg(A,x) \leq deg(R,x)+1∫R(x)ep(x)dx=A[x]ep(x),并且A[x]与R(x)形式一致,deg(A,x)≤deg(R,x)+1 简单粗略的证明 ∫R(x)ep(x)dx=[a1(x)+b1(x)]ep(x) \int R(x)e^{p(x)} dx=[a_{1}(x)+b_{1}(x)]e^{p...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 566
精华内容 226
热门标签
关键字:

切比雪夫多项式证明