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

多项式除法例子_方程除法怎么算问题描述给定一个$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)


相关推荐

  • makefile菜鸟入门「建议收藏」

    makefile菜鸟入门「建议收藏」转自:http://my.oschina.net/u/1413984/blog/199029 Makefile有三个非常有用的变量。分别是$@,$^,$发表于2年前(2014-02-1215:43)  阅读(9199) | 评论(0)2人收藏此文章,我要收藏赞0

  • 手机抓包工具 charles使用[通俗易懂]

    手机抓包工具 charles使用[通俗易懂]转自:https://blog.csdn.net/weixin_42338923/article/details/80500323(我又添加了几句我的使用经验)1、下载charles包、安装https://www.charlesproxy.com/download/2、关闭电脑防火墙【但我的经验是:可以选择先不关闭防火墙试一试,因为我后边再次使用时没关闭防火墙也是可以抓包的)】打开…

  • arp内网攻击_外网和内网怎么设置

    arp内网攻击_外网和内网怎么设置arpspoof是一款进行arp欺骗的工具,攻击者通过毒化受害者arp缓存,将网关mac替换为攻击者mac,然后攻击者可截获受害者发送和收到的数据包,可获取受害者账户、密码等相关敏感信息。本次测试是在局域网内进行,利用kali截获centos相关数据攻击者ip:192.168.157.129受害者ip:192.168.157.2501、在kali中开启端口转发功能:echo…

  • 数据库索引的实现原理

    数据库索引的实现原理

  • 关于串口数据的发送和接收(调试必备)

    关于串口数据的发送和接收(调试必备)前言对于串口的数据发送和接收,大多是都是利用串口中断来进行的,但是这样对于编程方面有一定要求,并且程序也不太好写,比如说,如果让你随意接收一段数据,然后利用串口将它发送出来,第一个需要考虑的问题就是接收数据的长度,怎么才知道一段数据是否结束?或者说如果串口助手上面没有可以在数据末尾加上结束标志的时候,你如何知道数据的结束?,这必然牵涉到一定的编程技巧。但是,之前在接触C语言的时候,我们就利用过…

  • xshell下载安装教程_xshell命令连接ip

    xshell下载安装教程_xshell命令连接ipxshell下载链接:  http://www.netsarang.com/download/free_license.html         现今软件市场上有很多终端工具,比如:secureCRT、Putty、telnet、xshell\等等。secureCRT是一款很强大的终端工具,但是,它毕竟是收费软件,在公司里不允许使用。而且在自己的电脑里一旦输入大写,整个界面就乱了(原因未知,未…

发表回复

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

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