精华内容
下载资源
问答
  • P4512 【模板】多项式除法 链接 分析   多项式除法 注意的地方: 75,76行开始时是这样写的: memcpy(TA,a,sizeof(int)*(n+1));memset(TA+n+1,0,sizeof(TA)); memcpy(TB,b,sizeof(int)*(m+1));memset...

    P4512 【模板】多项式除法

    链接

     

    分析  

      多项式除法

     

    注意的地方:

    75,76行开始时是这样写的:

    memcpy(TA,a,sizeof(int)*(n+1));memset(TA+n+1,0,sizeof(TA));
    memcpy(TB,b,sizeof(int)*(m+1));memset(TB+m+1,0,sizeof(TB));

    然后开O2的情况不过。最后发现时后面的memset不能这样写。然后在本地开O2测试,可以过样例。。。 ~ 惊!~ 吓!

     

     

    代码

      1 #include<cstdio>
      2 #include<algorithm>
      3 #include<cstring>
      4 #include<cmath>
      5 #include<iostream>
      6 #include<cctype>
      7 
      8 #define P 998244353
      9 #define G 3
     10 #define Gi 332748118 
     11 #define N 270000
     12 
     13 using namespace std;
     14 
     15 int A[N],B[N],D[N],TA[N],TB[N],DR[N],Binv[N],R[N];
     16 
     17 inline int read() {
     18     int x = 0,f = 1;char ch=getchar();
     19     for (; !isdigit(ch); ch=getchar()) if(ch=='-')f=-1;
     20     for (; isdigit(ch); ch=getchar()) x=x*10+ch-'0';
     21     return x*f;
     22 }
     23 
     24 int ksm(int a,int b) {
     25     int ans = 1;
     26     while (b) {
     27         if (b & 1) ans = (1ll * ans * a) % P;
     28         a = (1ll * a * a) % P;
     29         b >>= 1;
     30     }
     31     return ans;
     32 }
     33 void NTT(int *a,int n,int ty) {
     34     for (int i=0,j=0; i<n; ++i) {
     35         if (i < j) swap(a[i],a[j]);
     36         for (int k=(n>>1); (j^=k)<k; k>>=1);
     37     }
     38     for (int w1,m=2; m<=n; m<<=1) {
     39         if (ty == 1) w1 = ksm(G,(P-1)/m);
     40         else w1 = ksm(Gi,(P-1)/m);
     41         for (int i=0; i<n; i+=m) {
     42             int w = 1;
     43             for (int k=0; k<(m>>1); ++k) {
     44                 int u = a[i+k],t = 1ll * w * a[i+k+(m>>1)] % P;
     45                 a[i+k] = (u + t) % P;
     46                 a[i+k+(m>>1)] = (u - t + P) % P;
     47                 w = 1ll * w * w1 % P;
     48             }
     49         }
     50     }
     51     if (ty==-1) {
     52         int inv = ksm(n,P-2);
     53         for (int i=0; i<n; ++i) a[i] = 1ll * a[i] * inv % P;
     54     }
     55     
     56 }
     57 void Inv(int *A,int *B,int n) { 
     58     int len = 1;
     59     while (len <= n) len <<= 1; 
     60     B[0] = ksm(A[0],P-2);
     61     for (int m=2; m<=len; m<<=1) {
     62         for (int i=0; i<m; ++i) TA[i] = A[i],TB[i] = B[i];
     63         NTT(TA,m<<1,1);
     64         NTT(TB,m<<1,1);
     65         for (int i=0; i<(m<<1); ++i) TA[i] = 1ll*TA[i]*TB[i]%P*TB[i]%P;
     66         NTT(TA,m<<1,-1);
     67         for (int i=0; i<m; ++i) B[i] = (1ll*2*B[i]%P-TA[i]+P)%P;
     68     }
     69     memset(TA,0,sizeof(TA));
     70     memset(TB,0,sizeof(TB));
     71 }
     72 void Mul(int *a,int *b,int *C,int n,int m) {
     73     int len = 1;
     74     while (len <= n+m) len <<= 1;
     75     for (int i=0; i<=n; ++i) TA[i] = a[i];
     76     for (int i=0; i<=m; ++i) TB[i] = b[i];
     77     NTT(TA,len,1);
     78     NTT(TB,len,1);
     79     for (int i=0; i<len; ++i) C[i] = (1ll * TA[i] * TB[i]) % P,TA[i] = TB[i] = 0;
     80     NTT(C,len,-1);
     81 }
     82 int main() {
     83     int n = read() ,m = read() ;
     84     for (int i=0; i<=n; ++i) A[i] = read();
     85     for (int i=0; i<=m; ++i) B[i] = read();
     86     
     87     reverse(A,A+n+1);reverse(B,B+m+1); 
     88     
     89     Inv(B,Binv,n-m); // 求B转换后的逆元 
     90     Mul(A,Binv,D,n-m,n-m); // 求转换后的D 
     91     reverse(D,D+n-m+1);  
     92     for (int i=0; i<=n-m; ++i) printf("%d ",D[i]);puts("");
     93     
     94     reverse(A,A+n+1);reverse(B,B+m+1);
     95     Mul(D,B,R,n-m,m); // 求D*B 
     96     for (int i=0; i<m; ++i) R[i] = (A[i] - R[i] + P) % P; // 求R 
     97     for (int i=0; i<m; ++i) printf("%d ",R[i]);
     98     
     99     return 0;
    100 }

     

    转载于:https://www.cnblogs.com/mjtcn/p/9157378.html

    展开全文
  • 题目大意:给定一个$n$次多项式$F(x)$和一个$m$次多项式$G(x)$,请求出多项式$Q(x),R(x)$,满足: ...题解:多项式除法。$$F(x)\equiv Q(x)G(x)+R(x)(\bmod{x^n})\\F(\dfrac 1 x)\equiv Q(\dfr...

    题目大意:给定一个$n$次多项式$F(x)$和一个$m$次多项式$G(x)$,请求出多项式$Q(x),R(x)$,满足:

    1. $Q(x)$次数为$n-m$,$R(x)$次数小于$m$
    2. $F(x)=Q(x)\times G(x)+R(x)$

    题解:多项式除法。
    $$
    F(x)\equiv Q(x)G(x)+R(x)(\bmod{x^n})\\
    F(\dfrac 1 x)\equiv Q(\dfrac 1 x)G(\dfrac 1 x)+R(\dfrac 1 x)(\bmod{x^n})\\
    x^nF(\dfrac 1 x)\equiv x^{n-m}Q(\dfrac 1 x)\cdot x^mG(\dfrac 1 x)+x^nR(\dfrac 1 x)(\bmod{x^n})\\
    F_R(x)\equiv Q_R(x)G_R(x)+x^{n-m+1}R_R(x)(\bmod{x^n})\\
    F_R(x)\equiv Q_R(x)G_R(x)(\bmod{x^{n-m+1}})\\
    Q_R(x)\equiv F_R(x)G_R^{-1}(x)(\bmod{x^{n-m+1}})\\
    R_R(x)=F_R(x)-G_R(x)Q_R(x)
    $$
    卡点:

     

    C++ Code:

    #include <algorithm>
    #include <cstdio>
    #include <cctype>
    namespace __IO {
    	namespace R {
    		int x, ch;
    		inline int read() {
    			ch = getchar();
    			while (isspace(ch)) ch = getchar();
    			for (x = ch & 15, ch = getchar(); isdigit(ch); ch = getchar()) x = x * 10 + (ch & 15);
    			return x;
    		}
    	}
    }
    using __IO::R::read;
    
    const int mod = 998244353, G = 3;
    
    namespace Math {
    	int x, y;
    	inline int pw(int base, int p) {
    		int res = 1;
    		for (; p; p >>= 1, base = static_cast<long long> (base) * base % mod) if (p & 1) res = static_cast<long long> (res) * base % mod;
    		return res;
    	}
    	void exgcd(int a, int b, int &x, int &y) {
    		if (!b) x = 1, y = 0;
    		else exgcd(b, a % b, y, x), y -= a / b * x;
    	}
    	inline int inv(int a) {
    		exgcd(a, mod, x, y);
    		return x + (x >> 31 & mod);
    	}
    }
    
    #define N 262144
    inline void reduce(int &a) {a += a >> 31 & mod;}
    inline void clear(int *l, const int *r) {
    	if (l >= r) return ;
    	while (l != r) *l++ = 0;
    }
    
    namespace Poly {
    	int lim, ilim, rev[N], s;
    	int Wn[N + 1];
    	inline void init(int n) {
    		s = -1, lim = 1; while (lim < n) lim <<= 1, s++; ilim = Math::inv(lim);
    		for (register int i = 0; i < lim; i++) rev[i] = rev[i >> 1] >> 1 | (i & 1) << s;
    		const int t = Math::pw(G, (mod - 1) / lim);
    		*Wn = 1; for (register int i = 1; i <= lim; i++) Wn[i] = static_cast<long long> (Wn[i - 1]) * t % mod;
    	}
    	void NTT(int *A, int op = 1) {
    		for (register int i = 0; i < lim; i++) if (i < rev[i]) std::iter_swap(A + i, A + rev[i]);
    		for (register int mid = 1; mid < lim; mid <<= 1) {
    			const int t = lim / mid >> 1;
    			for (register int i = 0; i < lim; i += mid << 1) {
    				for (register int j = 0; j < mid; j++) {
    					const int W = op ? Wn[t * j] : Wn[lim - t * j];
    					const int X = A[i + j], Y = static_cast<long long> (A[i + j + mid]) * W % mod;
    					reduce(A[i + j] += Y - mod), reduce(A[i + j + mid] = X - Y);
    				}
    			}
    		}
    		if (!op) for (register int i = 0; i < lim; i++) A[i] = static_cast<long long> (A[i]) * ilim % mod;
    	}
    	int C[N];
    	void INV(int *A, int *B, int n) {
    		if (n == 1) {
    			*B = Math::inv(*A);
    			return ;
    		}
    		INV(A, B, n + 1 >> 1);
    		std::copy(A, A + n, C);
    		init(n << 1), clear(C + n, C + lim);
    		NTT(B), NTT(C);
    		for (int i = 0; i < lim; i++) B[i] = (2 + mod - static_cast<long long> (C[i]) * B[i] % mod) * B[i] % mod;
    		NTT(B, 0);
    		clear(B + n, B + lim);
    	}
    	int D[N], E[N], F[N];
    	void DIV(int *A, int *B, int *Q, int n, int m) {
    		std::reverse_copy(A, A + n, D), std::reverse_copy(B, B + m, E);
    		clear(D + n - m + 1, D + n);
    		clear(E + n - m + 1, E + m);
    		INV(E, F, n - m + 1), init(n - m + 1 << 1);
    		NTT(D), NTT(F);
    		for (int i = 0; i < lim; i++) Q[i] = static_cast<long long> (D[i]) * F[i] % mod;
    		NTT(Q, 0);
    		std::reverse(Q, Q + n - m + 1);
    		for (int i = n - m + 1; i < lim; i++) Q[i] = 0;
    	}
    	int G[N];
    	void DIV_MOD(int *A, int *B, int *Q, int *R, int n, int m) {
    		DIV(A, B, Q, n, m);
    		std::copy(Q, Q + n - m + 1, G);
    		init(n << 1);
    		NTT(A), NTT(B), NTT(G);
    		for (int i = 0; i < lim; i++) R[i] = (A[i] + mod - static_cast<long long> (B[i]) * G[i] % mod) % mod;
    		NTT(R, 0);
    	}
    }
    
    int A[N], B[N], Q[N], R[N];
    int n, m;
    int main() {
    	n = read() + 1, m = read() + 1;
    	for (int i = 0; i < n; i++) A[i] = read();
    	for (int i = 0; i < m; i++) B[i] = read();
    	Poly::DIV_MOD(A, B, Q, R, n, m);
    	for (int i = 0; i < n - m + 1; i++) printf("%d ", Q[i]); puts("");
    	for (int i = 0; i < m - 1; i++) printf("%d ", R[i]); puts("");
    	return 0;
    }
    

      

    转载于:https://www.cnblogs.com/Memory-of-winter/p/10084154.html

    展开全文
  • 模2除法

    2015-10-21 19:54:00
    在CRC(循环冗余校验码)的计算中用到了模2除法,与算数除法类似但每一位除的结构不影响其他位,即不向上借一位,所以实际上就是或。 2.被校验的数据 M(x)=1000,其选择生成多项式为 G(x)=x^3+x+1,该数据...
    1. 在CRC(循环冗余校验码)的计算中用到了模2除法,与算数除法类似但每一位除的结构不影响其他位,即不向上借一位,所以实际上就是或。

     

     

     

    2.被校验的数据  M(x)=1000,其选择生成多项式为 G(x)=x^3+x+1,该数据的循环冗余校验和应为多少?

        解:

    G(x)=x^3+x+1对应的二进制数为1011,且G(x)中含3个项式,生成多项式为4

    位二进制,由CRC规则应该取(4-1)=3位(校验和),所以可以预加上3位得到1000B*2^3=1000 000B; 1000 000B(被除数)对1011(除数)做模2除法,得到的余数便101B(即CRC校验和),

    所以该数据的循环冗余校验后的数据应为

    1000 000B+101B=1000101B

    转载于:https://www.cnblogs.com/miajun/p/4898904.html

    展开全文
  • 模2除法求冗余码模2除法课后例题 模2除法 模2除法是参考博文知悉的。 注意:求冗余码所用的二进制除法是模2除法模2除法需要用到模2减法,而模2减法跟模2加法类似,是不带进/借位的运算! 模2减法规则: 0-0=0; 1-1...

    模2除法求冗余码

    模2除法

    模2除法是参考博文知悉的。

    注意:求冗余码所用的二进制除法是模2除法,模2除法需要用到模2减法,而模2减法跟模2加法类似,是不带进/借位的运算!

    模2减法规则:

    0-0=0;
    1-1=0;
    0-1=1;//无需考虑借位
    1-0=1;//同上
    

    课后例题

    3-07 要发送的数据为1101011011。采用CRC的生成多项式是P(X)=X^4+X+1。试求应添加在数据后面的余数。数据在传输过程中最后一个1变成0,问接收端能否发现?

    解:由生成多项式可得除数为10011,除数位数为5,则余数位数为4。
    被除数为要发送的数据+4个0即11010110110000。根据除法规则得余数1110。
    数据传输出错后被除数变成了11010110100000,被除数除以除数10011得余数不为0,所以接收端能发现传输错误。
    在这里插入图片描述
    3-08 数据101110,多项式是P(X)=X^3+1。求余数?
    由多项式得除数为1001,则余数位数应为3,被除数为101110000。根据除法规则得余数011。
    在这里插入图片描述

    展开全文
  • 模2除法(计算CRC校验码)

    千次阅读 2020-03-31 17:51:29
    模2除法结果与异或相同,但是与算术除法不同,即每一位除的结果不影响其它位(不向上一位借位)。 以下,我将以一道题目为例。 采用CRC进行差错校验,生成多项式为G(x)=x4+x+1G(x)=x^{4} +x+1G(x)=x4+x+1信息码字为...
  • 一、CRC定义 CRC(Cyclic Redundancy Check),即循环冗余检验码,也可叫做循环码,具有检错和纠错能力。... 模2除法,就是在进行除法运算时不计进位的除法。 先看三点在模2除时要记住的准则 ...
  • 1、环境要求:Windows2000/XP/7;C;信息交换内容为文本文件;信息交换方式为共享文件 2、编码要求:生成多项式为CRC-32 3、功能要求:能在两台计算机机上运行程序,一台产生CRC码,另一台校验
  • 网上的除法很多都很官方,很难看得懂,因为实在太耗费时间搜索,索性自己写了一个较为简单的,方便以后复习。 以这道题为例,又多项式可以得出除数为10011。 在进行除法,要在被除数后面加上“除数位数-1”的0...
  • 多项式求逆 给定A(x)A(x)A(x)求B(x)=A−1(x)(modxn)B(x)=A^{-1}(x)(mod x^n)B(x)=A−1(x)(modxn) 使用倍增构造。 若n=1,则直接求0次项的乘法逆元。 若n&amp;amp;amp;amp;gt;1 设B(x)B(x)B(x)满足 A(x)B(x)≡1...
  •  这里多项式的系数只有1或0,因为题目要求:这里多项式的加减法是将系数相加/减后再模2,这样其实也就可以用异或运算来代替加减法。 思路:看代码吧,水题一个,主要在于把除法转化成减法,一次一次减就行。 ...
  • 文章目录一、前言二、数学基础1、GF(2⁸)有限域内的多项式2、不可约多项式3、多项式模运算3、乘法逆元三、算法步骤1、扩展欧几里得算法2、多项式除法3、多项式乘法四、代码实现1、多项式除法2、多项式乘法3、...
  • 多项式填坑。。?

    2019-02-27 23:04:00
    多项式带余除法 这东西啥啊。怎么还带翻转的。 别指望我写推导,丢个代码块就跑。 而且还是我美妙无比的多项式模板。(牛顿迭代自己\(yy\)循环写法的真的就我一个吗?) inline void Inv(int *A,int *B,int n){ B[0...
  • 模2运算百度百科

    2020-10-30 14:13:24
    与四则运算相同,模2运算也包括模2加法、模2减法、模2乘法、模2除法四种二进制运算。与四则运算不同的是模2运算不考虑进位和借位,模2算术是编码理论中多项式运算的基础。模2算术在其他数字领域中的应用也是很广泛的...
  • PAT-天梯赛习题集-L2-018-多项式A除以B

    千次阅读 2017-03-30 23:39:48
    ACM模版描述题解原本我以为这个是...而这道题,实际上不是代码难写,也不是思路复杂,而是我根本不知道什么是多项式除法,所以比赛时大眼瞪小眼瞪了半个多小时却没有看懂样例,一旦知道什么是多项式除法以及具体怎么
  • 通讯校验

    2020-11-30 23:40:25
    通讯校验: 在一个m位m二进制数据序列之后附加...每个二进制序列的校检码为该序列与所选择的多项式模2除法的余数。 常用的CRC码的生成多项式为: CRC8=X8+X5+X4+1 CRC-CCITT=X16+X12+X5+1 CRC16=X16+X15+X5+1 CRC12=X.
  • CRC查表运算原理

    2021-05-16 11:30:10
    CRC校验是依据多项式模2运算进行的,这里有两点: 1. 一个二进制串总可以表示为多项式,例如: 10101 表示为 ...除法:依据多项式模2减法算得 多项式模2运算满足分配律和结合律:已知多项式 则 ...
  • 模2运算的加减乘除运算

    千次阅读 2020-05-05 12:30:43
    模2运算 是一种二进制算法,CRC校验技术中的核心部分。与四则运算相同,模二运算也包括模二加法、模二减法、模二乘法、模二除法四种二进制运算。与四则运算不同的是模二运算不考虑进位和借位,模二算术是编码理论中...
  • 2.注意做除法之前需要先在原数据后面添加4个零才能作为被除数,4对于除数多项式的最高次幂4 3.关于除到什么时候停止:余数必须是比除数小一个位数,最后余数需要是4位也是与除数那个多项式的最高次幂相同 3-08 要...
  • CRC校验码之二算法

    2020-02-28 20:37:01
    与四则运算相同,模2运算也包括模2加法、模2减法、模2乘法、模2除法四种二进制运算。与四则运算不同的是模2运算不考虑进位和借位,模2算术是编码理论中多项式运算的基础。模2算术在其他数字领域中的应用也是很广泛的...
  • 他其实是利用了模2除法的计算方式 我用下面的例子简述一下使用方法。 原始报文为 “11001010101”,其生成多项式为:x4+x3+x+1.对其进行CRC编码后的结果为? 首先要先理解生成的多项式 x4+x3+x+1的含义,其中最高的...
  • 循环冗余校验是一种错误检测算法,它使用生成多项式 2 除法来查找要与数据一起发送的校验和;
  • CRC校验

    千次阅读 2013-07-07 13:48:53
    CRC检验原理实质是利用模2除法(除数由生成多项式决定)来求得余数,生成检验码,将其并入数据项末尾作为数据序列(比特序列)发送出去。 接收方拿到数据序列后,使用相同的生成多项式进行模2除法,若可除尽,则...
  • CRC校验理解

    千次阅读 2019-03-13 22:59:45
    3. 除法模2减法。 为了进行CRC运算,也就是这种特殊的除法运算,必须要指定个被除数,在CRC算法中,这个被除数有一个专有名称叫做“生成多项式”。最常用的几种生成多项式如下: CRC8=X8+X5+X...
  • 被处理的数据块可以看作是一个二进制多项式,例如,10110101可以看作是2^7+2^5+2^4+2^2+2^0,多项式除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2,加减时不进,错位,和逻辑异或运算一致...
  • 循环冗余检验算法CRC

    2016-12-08 08:27:00
    首先要了解多项式乘法...了解模2运算的含义,多项式除法后合并同类项时。。系数%2处理 大大简化了除法运算。。并且运算方式跟异或对应上了。。很好。。 转载于:https://www.cnblogs.com/linkzijun/p/6143520.html...
  • CRC校验详解(附代码示例)

    千次阅读 2019-11-08 10:15:21
    模2除法:也叫模2运算,就是结果除以2后取余数。模2除法每一位除的结果不影响其它位,即不向上一位借位,所以实际上就是异或。在CRC计算中有应用到模2除法多项式与二进制:二进制可表示成多项式的形式,比如二...
  • CRC校验算法原理

    千次阅读 2012-09-01 17:06:32
    被处理的数据块可以看作是一个二进制多项式,例如,10110101可以看作是2^7+2^5+2^4+2^2+2^0,多项式除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2,加减时不进,错位,和逻辑异或运算一致...
  • CRC 校验

    2012-03-04 12:00:51
    被处理的数据块可以看作是一个二进制多项式,例如,10110101可以看作是2^7+2^5+2^4+2^2+2^0,多项式除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2,加减时不进,错位,和逻辑异或运算一致...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 156
精华内容 62
关键字:

多项式模2除法