多项式除法例子_方程除法怎么算

多项式除法例子_方程除法怎么算问题描述给定一个$n$次多项式$F(x)$和一个$m$次多项式$G(x)$,请求出多项式$Q(x)$,$R(x)$,满足以下条件:$Q(x)$次数为$n-m$,$R(x)$次数

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

问题描述

给定一个 $n$次多项式 $F(x)$ 和一个 $m$ 次多项式 $G(x)$,请求出多项式 $Q(x)$,$R(x)$,满足以下条件:

  • $Q(x)$ 次数为 $n-m$,$R(x)$ 次数小于 $m$
  • $F(x) = Q(x) * G(x) + R(x)$

所有运算在模998244353意义下进行

详见洛谷 P4512

分析

具体来说,设多项式$A$为$n$次多项式,考虑一种操作$R$,使得

$\displaystyle A_R(x)=x^n A(\frac{1}{x})$

稍微想象一下,可以发现$A_R[i]=A[n-i]$($[i]$表示多项式的第$i$次系数)。

这个操作可以$O(n)$完成。

然后开始化式子。

$$F(x)=Q(x) * G(x)+R(x)$$

$$\displaystyle F(\frac{1}{x})=Q(\frac{1}{x}) * G(\frac{1}{x})+R(\frac{1}{x})$$

$$\displaystyle x^n F(\frac{1}{x})=x^{n-m} Q(\frac{1}{x}) * x^m G(\frac{1}{x})+x^{n-m+1} * x^{m-1} R(\frac{1}{x})$$

$$\displaystyle F_R(x)=Q_R(x)*G_R(x)+x^{n-m+1} * R_R(x)$$

$$\displaystyle F_R(x) \equiv Q_R(x)*G_R(x)\pmod {x^{n-m+1}}$$

$$\displaystyle Q_R(x) \equiv F_R(x)*G_R^{-1}(x)\pmod {x^{n-m+1}}$$

求一遍$G_R$的逆,然后就可以利用多项式乘法求出$Q$。然后

$$R(x)=F(x)-G(x)*Q(x)$$

直接计算即可。系数翻转可以用自带的 $reverse$ 函数,逆元最好迭代求解

总的时间复杂度$O(nlogn)$。

代码:

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1<<20;

int read()
{
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = (x<<1) + (x<<3) + c - '0', c = getchar();
    return x * f;
}
namespace Polynomial
{
    const ll P = 998244353, g = 3, gi = 332748118;
    static int rev[N];
    int lim, bit;
    ll add(ll a, ll b)
    {
        return (a += b) >= P ? a - P : a;
    }
    ll qpow(ll a, ll b)
    {
        ll prod = 1;
        while(b)
        {
            if(b & 1) prod = prod * a % P;
            a = a * a % P;
            b >>= 1;
        }
        return (prod + P) % P;
    }
    void calrev() {
        for(int i = 1; i < lim; i++)
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
    }
    void NTT(ll *A, int inv)
    {
        for(int i = 0; i < lim; i++)
            if(i < rev[i]) swap(A[i], A[rev[i]]);
        for(int mid = 1; mid < lim; mid <<= 1)
        {
            ll tmp = qpow(inv == 1 ? g : gi, (P - 1) / (mid << 1));
            for(int j = 0; j < lim; j += (mid << 1))
            {
                ll omega = 1;
                for(int k = 0; k < mid; k++, omega = (omega * tmp) % P) {
                    int x = A[j + k], y = omega * A[j + k + mid] % P;
                    A[j + k] = (x + y) % P;
                    A[j + k + mid] = (x - y + P) % P;
                }
            }
        }
        if(inv == 1) return;
        int invn = qpow(lim, P - 2);
        for(int i = 0; i < lim; i++)
            A[i] = A[i] * invn % P;
    }
    static ll x[N], y[N];
    void mul(ll *a, ll *b)
    {
        memset(x, 0, sizeof x);
        memset(y, 0, sizeof y);
        for(int i = 0; i < (lim >> 1); i++)
            x[i] = a[i], y[i] = b[i];
        NTT(x, 1), NTT(y, 1);
        for(int i = 0; i < lim; i++)
            x[i] = x[i] * y[i] % P;
        NTT(x, -1);
        for(int i = 0; i < lim; i++)
            a[i] = x[i];
    }
    static ll c[2][N];
    void Inv(ll *a, int n)
    {
        int p = 0;
        memset(c, 0, sizeof c);
        c[0][0] = qpow(a[0], P - 2);
        lim = 2, bit = 1;
        while(lim <= (n << 1))
        {
            lim <<= 1, bit++;
            calrev();
            p ^= 1;
            memset(c[p], 0, sizeof c[p]);
            for(int i = 0; i <= lim; i++)
                c[p][i] = add(c[p^1][i], c[p^1][i]);
            mul(c[p^1], c[p^1]);
            mul(c[p^1], a);
            for(int i = 0; i <= lim; i++)
                c[p][i] = add(c[p][i], P - c[p^1][i]);
        }
        for(int i = 0; i < lim; i++)
            a[i] = c[p][i];
    }
}
using namespace Polynomial;
int n,  m;
ll F[N], G[N], Q[N], R[N], Gr[N];
int main()
{
    n = read(), m = read();
    for(int i = 0; i <= n; i++)
        F[i] = read(), Q[n - i] = F[i];
    for(int i = 0; i <= m; i++)
        G[i] = read(), Gr[m - i] = G[i];
    for(int i = n - m + 2; i <= m; i++)
        Gr[i] = 0;
    Inv(Gr, n - m + 1);    //Gr=Gr的逆
    mul(Q, Gr);            //Q=Q*Gr
    reverse(Q, Q + n - m + 1);   //Q=reverse(Q)
    for(int i = n - m + 1; i <= n; i++)
        Q[i] = 0;
    for(int i = 0; i <= n - m; i++)
        printf("%lld ", Q[i]);
    printf("\n");
    lim = 1, bit = 0;
    while(lim <= (n << 2))
        lim <<= 1, bit++;
    calrev();
    mul(Q, G);
    for(int i = 0; i < m; i++)
        printf("%lld ", add(F[i], P - Q[i]));   //R=F - Q*G
    return 0;
}

 

代码转载自:https://www.luogu.org/blog/AKIOIorz/p4512-mu-ban-duo-xiang-shi-chu-fa

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/167859.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • jsonstring_jsonstring转对象

    jsonstring_jsonstring转对象fastjson包下的JSONJSONStringauthTbAccountsByBd=instance.getAuthTbAccountsByBd(“”);JSONObjectparse=(JSONObject)JSON.parse(authTbAccountsByBd.getValue());

  • 《大话数据结构》pdf

    《大话数据结构》pdf下载地址:网盘下载编辑推荐编辑超级畅销书《大话设计模式》作者的新作!用户群更为广泛,写作风格一如既往,技术沉淀更加深厚,势必掀起全民数据结构的热潮!内容简介编辑本书为超级畅销书《大话设计模式》作者程杰潜心三年推出的扛鼎之作!以一个计算机教师教学为场景,讲解数据结构和相关算法的知识。通篇以一种趣味方式来叙述,大量引用了各种各样的生…

  • 基于麦克风阵列的现有声源定位技术有_阵列原理

    基于麦克风阵列的现有声源定位技术有_阵列原理《基于麦克风阵列声源定位系统.doc》由会员分享,可免费在线阅读全文,更多与《基于麦克风阵列声源定位系统》相关文档资源请在帮帮文库(www.woc88.com)数亿文档库存里搜索。1、()cosiiiiettH,则有:cos()ex()()cosjiijijjiijretjkrretr()由于()()cos()cosex()jjijjijjjjiettHtHjkrr…

  • 二叉树的5个重要性质「建议收藏」

    二叉树的5个重要性质「建议收藏」1.在二叉树的第i层上最多有2 i-1 个节点。(i>=1) 用归纳法证明:归纳基:i=1层时,只有一个根结点,          2i-1=20=1;归纳假设:假设i=k时,命题成立;归纳证明:二叉树上每个结点至多有两棵子树,则第k+1层的结点数最多为2k-12=2k+1-1。

  • html.dropdownlistfor_see的用法

    html.dropdownlistfor_see的用法常用方法后台代码:publicActionResultIndex(){ViewData[“deptOu”]=”SOHO”;using(ISessionsession=newNHibernateHelper(DataBase.ADDB).OpenSession()){IList<t_data_DeptOU>dep…

    2022年10月10日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号