精华内容
下载资源
问答
  • 题目地址: PTA 题目内容 设计函数分别求两个一元多项式的乘积与和。 输入格式: 输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式...(系数全为零的多项式没有次数,这个多项式叫零多项式零多项式总可

    题目地址: PTA

    题目内容

    设计函数分别求两个一元多项式的乘积与和。

    输入格式:
    输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值 均为不超过1000的整数)。数字间以空格分隔。

    输出格式:
    输出分2行,分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔,但结尾不能有多余空格零多项式应输出0 0

    注意事项

    1.输入的时候不能输入 0 n 即项数是不输入0的。
    (系数全为零的多项式没有次数,这个多项式叫零多项式,零多项式总可计为0)
    2.括号里的绝对值在本题中起误导作用,本人一开始想到的指数范围是-1000 - 1000。 但ac后发现指数范围其实只是0 - 1000
    3.输出的时候即使是0 + 0 也只输出一个0即多个0只输出一次 0 0
    (此处本人理解是因为1中的零多项式总可计为0,即多个0相加始终是一个0)【还有指数递降的限制】。
    4.注意空格格式和输出0的问题(尤其是0的问题)

    解题思路

    将输入的多项式依次存到数组池中。
    再将多项式的指数作为数组下标,系数作为数组值存到乘法数组和加法数组中。
    存入一个多项式就进行一次运算。
    因为题目限制了指数大小,为了不浪费存储空间,数组大小进行了特殊赋值

    代码

    #include<iostream>
    using namespace std;
    struct Pool {
    	int ex;
    	int co;
    }pool[1001];	// 指数范围 0 - 1000 或 1 - 1000
    int product[2001];	// 1001项乘1001项 共2001项 即数组大小为2001
    int sum[1001];		// 加法项 0-1000 1001项 即数组大小为1001
    int main()
    {
    	int n1, n2;
    	cin >> n1;
    	for (int i = 0; i < n1; i++)
    	{
    		cin >> pool[i].co >> pool[i].ex;	//依次存入多项式到数组池中
    		sum[pool[i].ex] += pool[i].co;		// 将指数作为数组下标存入数组,系数作为数组值
    	}
    	cin >> n2;
    	int exponent, coefficient;	// 第二次输入得指数系数
    	for (int i = 0; i < n2; i++)
    	{
    		cin >> coefficient >> exponent;	// 存入一个多项式就拿此多项式进行运算
    		sum[exponent] += coefficient;	// 指数相同则系数相加
    		for (int j = 0; j < n1; j++) {	// 用存进去的多项式依次跟数组池中的数进行运算
    			product[exponent + pool[j].ex] += coefficient * pool[j].co;	// 指数相加,系数相乘
    		}
    	}
    	int isFirst = 1, flag = 1;	// 第一次输出及零多项式的标志
    	for (int i = 2000; i >= 0; i--)		// 指数递减
    	{
    		if (product[i] != 0)	// 不为零则输出
    		{
    			if (isFirst)	// 判断是否是第一次输出
    			{
    				cout << product[i] << " " << i;		// 空格格式
    				isFirst = 0;
    			}
    			else {
    				cout << " " << product[i] << " " << i;		// 无法确定最后一位输出故更改第一位输出
    
    			}
    			flag = 0;	// 进入if则不为0 重置flag
    		}
    	}
    	if (flag) {
    		cout << 0 << " " << 0;		// 全为0 输出 0 0
    	}
    	cout << endl;	// 输出换行
    	isFirst = 1, flag = 1;	// 更新数据
    	for (int i = 1000; i >= 0; i--)		// 同输出乘法
    	{
    		if (sum[i] != 0)
    		{
    			if (isFirst)
    			{
    				cout << sum[i] << " " << i;
    				isFirst = 0;
    			}
    			else {
    				cout << " " << sum[i] << " " << i;
    			}
    			flag = 0;
    		}
    	}
    	if (flag) {
    		cout << 0 << " " << 0;
    	}
    	return 0;
    }
    

    个人认为此题题意不是很明确,踩了很多坑。但也可能是我的理解能力出现了问题
    此代码参考了此文章 原文

    展开全文
  • 整系数多项式的基本运算 问题的引出 ... 通常需要借助费马小定理和多项式的欧几里得除法将上述一个复杂的问题转化一个次数更低的模素数同余式。 具体来说,由费马小定理可知,多项式xp−x(modp)x

    问题的引出

    在该博客中我将着手解决这样一个问题,在求解模素数pp的同余式:
    f(x)=anxn++a1x+a00(modp) f(x)=a_nx^n+\cdots+a_1x+a_0\equiv0\left(modp\right)
    时,其中ana_n恒不为零. 通常需要借助费马小定理和多项式的欧几里得除法将上述一个复杂的问题转化为一个次数更低的模素数同余式。

    具体来说,由费马小定理可知,多项式xpx(modp)x^p-x\left(modp\right)对任何整数取值为零.进一步,利用多项式欧几里得除法可知存在整系数多项式q(x)q(x),r(x)r(x)使得:
    f(x)=q(x)(xpx)+r(x),deg(r(x))<deg(g(x)). f(x)=q(x)(x^p-x)+r(x), deg(r(x))<deg (g(x)).
    从而容易将上述同余式:
    f(x)=anxn++a1x+a00(modp) f(x)=a_nx^n+\cdots+a_1x+a_0\equiv0\left(modp\right)
    降次为同余式:
    r(x)0(modp) r(x)\equiv0\left(modp\right)
    不难证明上述两个模pp同余式等价.这时我便将初始的问题转化为一个次数更低的模pp同余式,进而方便原复杂问题的进一步求解。在这个化简过程中,起到核心作用的便是多项式的欧几里得除法,所以为了最终成功编程实现模素数pp任意次同余式的求解,我需要首先编程实现整系数的多项式欧几里得除法.

    多项式欧几里得除法

    引理(多项式欧几里得除法):

    f(x)=anxn++a1x+a0 f(x)=a_nx^n+\cdots+a_1x+a_0
    nn次整系数多项式,
    g(x)=xn++b1x+b0 g(x)=x^n+\cdots+b_1x+b_0
    m1m\ge1次首一整系数多项式,则存在整系数多项式q(x)q(x),r(x)r(x)使得:
    f(x)=q(x)(xpx)+r(x)deg(r(x))<deg(g(x)). f(x)=q(x)(x^p-x)+r(x), deg(r(x))<deg (g(x)).
    证 :分以下两种情形讨论:
    (i)(i) n<mn<m.取q(x)=0q(x)=0,r(x)=f(x)r(x)=f(x),结论成立.
    (i)(i) nmn\ge m.对f(x)f(x)的次数nn做数学归纳法.
    对于 n=mn=m,有
    f(x)ang(x)=(an1anbm1)xn1++(a1anb1)x+a0anb f(x)-a_ng(x)=(a_{n-1}-a_nb_{m-1})x^{n-1}+\cdots+(a_1 -a_n b_1 )x+a_0-a_nb
    因此,q(x)=an,r(x)=f(x)ang(x)q(x)=a_n, r(x)=f(x)-a_ng(x)为所求.
    假设n1mn-1\ge m时,结论成立.
    对于n>mn>m,有
    f(x)anxnmg(x)=(an1anbm1)xn1++(anmanb1)xnm+anm1xnm1++a0anb f(x)-a_nx^{n-m}g(x)=(a_{n-1}-a_nb_{m-1})x^{n-1}+\cdots+(a_{n-m} -a_n b_1 )x^{n-m}+a_{n-m-1}x^{n-m-1}+\cdots+a_0-a_nb
    这说明f(x)anxnmg(x)f(x)-a_nx^{n-m}g(x)是次数n1\le n-1的多项式。对其运用归纳假设,存在整系数多项式q1(x)q_1(x),r1(x)r_1(x)使得:
    f(x)anxnmg(x)=q1(x)g(x)+r1(x)deg(r1(x))<deg(g(x)). f(x)-a_nx^{n-m}g(x)=q_1(x)g(x)+r_1(x), deg(r_1(x))<deg (g(x)).
    因此,q(x)=anxnmg(x)+q1(x),r(x)=r1(x)q(x)=a_nx^{n-m}g(x)+q_1(x),r(x)=r_1(x)为所求.

    多项式欧几里得除法的C语言实现

    我利用整形数组来代替多项式本身进行运算,进行整型数组的加减法和乘法运算,本质上是从右至左进行运算.而用多项式的系数进行运算时为了方便,我们总是默认将多项式的系数从高次至低次依次输入数组,这样直接调用数组元素会加重代码复杂度,降低代码的可读性. 因此,我想到一个解决这个问题简单的方法,就是在进行加减法和乘法之前,现将初始数组倒置,这样就可以直观的进行运算,最终将数组再次倒置,便于阅读.

    倒置函数

    int* Reverse(int *a, int Len)
    {
    	int tmp;
    	for (int i = 0; i < Len / 2; i++)
    	{
    		tmp = a[i];
    		a[i] = a[Len - 1 - i];
    		a[Len - 1 - i] = tmp;
    	}
    	return a;
    }
    
    

    多项式加法

    int* PA(int * a, int Len1, int * b, int Len2)
    {
    	a = Reverse(a, Len1);//倒置数组a
    	b = Reverse(b, Len2);//倒置数组b
    	int Len3 = Max(Len1, Len2);//获得用于表示和多项式的数组的长度
    	int *arr = (int*)malloc(Len3 * sizeof(int));//为和多项式的数组开辟动态内存空间
    	if (Len1 == Len3)//将多项式最高次的次数高的数组赋给新的数组
    		for (int i = 0; i < Len1; i++)
    			arr[i] = a[i];
    	else
    		for (int i = 0; i < Len3; i++)
    			arr[i] = b[i];
    	if (Len1 != Len3)//将多项式最高次的次数低的数组与新数组相加
    		for (int i = 0; i < Len1; i++)
    			arr[i] += a[i];
    	else
    		for (int i = 0; i < Len2; i++)
    			arr[i] += b[i];
    	arr = Reverse(arr, Len3);//倒置和多项式的数组,以便该数组直接表示和多项式从高至低的系数
    	a = Reverse(a, Len1);//保持输入数组a不变
    	b = Reverse(b, Len2);//保持输入数组b不变
    	return arr;
    }
    

    多项式减法

    int* PS(int * a, int Len1, int * b, int Len2)
    {
    	a = Reverse(a, Len1);//倒置数组a
    	b = Reverse(b, Len2);//倒置数组b
    	int Len3 = Max(Len1, Len2);//初步获得用于表示余式的数组的长度(可能比这个长度低,因为数组a和数组b的前多个髙次项系数和次数完全一样)
    	int *arr = (int*)malloc(Len3 * sizeof(int));//为余式的数组开辟动态内存空间
    	if (Len1 == Len3)//若数组a的长度大于等于数组b的长度,只需将数组a赋给新数组,再将数组a的前Len2个元素分别减掉数组b对应的元素
    	{
    		for (int i = 0; i < Len1; i++)//
    			arr[i] = a[i];
    		for (int i = 0; i < Len2; i++)
    			arr[i] -= b[i];
    	}
    	else//若数组a的长度小于数组b的长度,先将数组a赋给新数组的前Len1个元素,再用数组a的元素分别减掉数组b对应的前len1个元素,最终将数组b的后Len3-Len1个元素置负后赋给新数组的后半部分
    	{
    		for (int i = 0; i < Len1; i++)
    			arr[i] = a[i];
    		for (int i = 0; i < Len1; i++)
    			arr[i] -= b[i];
    		for (int i = Len1; i < Len2; i++)
    			arr[i] = -b[i];
    	}
    	arr = Reverse(arr, Len3);//倒置余式的数组,以便该数组直接表示余式从高至低的系数
    	//由于数组a和数组b的前多个髙次项系数和次数完全一样,所以上述操作结束后余式数组arr可能前几项元素为0,即余式系数不再等于输入多项式的最高次项。
    	//而输出的数组应该保留至首个非零的元素,即将系数为零的高次项消除。所以我们需要将余式从高次至低次检查系数是否为零,确保返回的余式首系数不为零。
    	int count = 0;//用于记录余式数组arr需要出掉多少个零元素
    	for (int i = 0; i < Len3; i++)//从左至右判断arr元素是否为零
    	{
    		if (arr[i] == 0)
    			count++;
    		else
    			break;//一旦出现非零元素便跳出循环
    	}
    	if (count != 0)//判断数组arr所代表的余式是否需要保留首个系数不为零及之后的项
    	{
    		int *brr = (int*)malloc((Len3 - count) * sizeof(int));//为首个系数不为零及之后的项分配内存
    		for (int i = 0; i < Len3 - count; i++)//从数组arr首个不为零的元素开始依次赋值给数组brr
    			brr[i] = arr[i + count];
    		free(arr);//释放最初数组arr
    		arr = brr;//将数组brr的首地址赋给arr
    		brr = NULL;//将数组brr置空
    	}
    	a = Reverse(a, Len1);//保持输入数组a不变
    	b = Reverse(b, Len2);//保持输入数组b不变
    	return arr;
    }
    

    多项式乘法

    int* PM(int * a, int Len1, int * b, int Len2)
    {
    	a = Reverse(a, Len1);//倒置数组a
    	b = Reverse(b, Len2);//倒置数组b
    	int *arr = (int*)calloc(Len1 + Len2, sizeof(int));//为积多项式的数组开辟动态内存空间,并顺便将每个元素赋值为0
    	for (int i = 0; i < Len2; i++)//用数组b的元素分别去乘数组a
    		for (int j = 0; j < Len1 ; j++)
    			arr[j+i] += b[i] * a[j];//并向左依次移一维
    	arr = Reverse(arr, Len1 + Len2 - 1);//倒置积多项式的数组,以便该数组直接表示积多项式从高至低的系数
    	a = Reverse(a, Len1);//保持输入数组a不变
    	b = Reverse(b, Len2);//保持输入数组b不变
    	return arr;
    }
    

    多项式除法

    int* PD(int * a, int Len1, int * b, int Len2)
    {
    	if (b[0] != 1)//除式首系数不为1,则该程序无法解决这样的多项式除法
    		return 0;
    	int count;//记录每次做差时,被减式与减式从左至右连续相同的位数
    	int Len11 = Len1;//初始化被减式的位数
    	int count2 = 0;//用于记录除法进行到哪一位
    	int *Q = NULL;//初始化商式
    	int *tmp1 = NULL;//初始化减式
    	int* tmp2 = a;//初始化被减式(刚开始即为数组a)
    	int *tmp3 = a;//初始化中间被差式(也是每一步的余式)
    	while (Len11 >= Len2)//判断余式的最高次数是否小于除式的最高次数,若小于,那么多项式除法结束并返回最新的余式;若大于,那么多项式除法继续进行
    	{
    		printf("第 %d 次循环\n", count2);
    		count = 0;//每次循环需要重新初始化被减式与减式从左至右连续相同的位数
    		if (a[count2] == 0 && tmp2[1]==0)//判断这一循环位是否商零,若商零,用于记录除法进行到哪一位的count2自动加一,且直接进入下一个循环
    		{
    			count2++;
    			continue;
    		}
    		else
    		{
    			printf("Len11 is %d\n", Len11);
    			printf("count2 is %d\n", count2);
    			Q = (int*)calloc(Len11 + 1 - Len2, sizeof(int));//分配本次循环的商式的内存。
    			Q[0] = tmp2[0];//将被减式的首元素赋给商式的首元素
    			printf("Q is \n");
    			for (int j = 0; j < Len11 + 1 - Len2; j++)
    				printf("%d", Q[j]);
    			printf("\n");
    			tmp1 = (int*)malloc((Len11) * sizeof(int));//为本次循环的减式分配内存
    			printf("LenQ is %d\n", Len11 + 1 - Len2);
    			tmp1 = PM(Q, Len11 + 1 - Len2, b, Len2);//计算本次循环的减式
    			printf("tmp1 is \n");
    			for (int j = 0; j < Len11; j++)
    				printf("%d", tmp1[j]);
    			printf("\n");
    			for (int i = 0; i < Len11; i++)//记录本次循环被减式与减式从左至右连续相同的位数
    				if (tmp1[i] == tmp2[i])
    					count++;
    				else
    					break;
    
    			printf("count is %d\n", count);
    			printf("count2 is %d\n", count2);
    			tmp3 = (int*)calloc(Len11 - count, sizeof(int));//为本次循环的余式分配内存
    			printf("Len11 is %d\n", Len11);
    			printf("Lentmp3 is %d\n", Len11 - count);
    			tmp3 = PS(tmp2, Len11, tmp1, Len11);//计算本次循环的余式
    			printf("tmp3 is \n");
    			for (int i = 0; i < Len11 - count; i++)
    				printf("%d", tmp3[i]);
    			printf("\n");
    			
    			tmp2 = NULL;//每次循环到达这一步时,我们已经计算出了下一次循环的被除式,即tmp3,因此我们把旧的被除式置空
    			tmp2 = tmp3;//并将新的被除式tmp3赋给tmp2
    			printf("tmp2 is \n");
    			for (int i = 0; i < Len11 - count; i++)
    				printf("%d", tmp2[i]);
    			printf("\n");
    			Len11 = Len11 - count;//计算下次循环减式的长度
    			
    			count2++;
    			printf("\n");
    			printf("\n");
    		}
    	}
    	return tmp2;//返回最新的余式,
    }
    

    主程序调用

    我在这里会举出一个实际的例子:
    求同余式:
    f(x)=3x14+4x13+2x11+x9+x6+x3+12x2+x0(mod5), f(x)=3x^{14}+4x^{13}+2x^{11}+x^9+x^6+x^3+12x^2+x\equiv 0 (mod 5),
    等价的次数小于5的同余式:r(x)r(x).

    int main()
    {
    	int a[] = { 3,4,0,2,0,1,0,0,1,0,0,1,12,1,0 };
    	int b[] = { 1,0,0,0,-1,0 };
    	int Len1 = sizeof(a) / sizeof(a[0]);
    	int Len2 = sizeof(b) / sizeof(b[0]);
    	int *f = PD(a, Len1, b, Len2);
    	for (int i = 0; i < 4; i++)
    		printf("%d ", f[i]);
    	free(f);
    	_getch();
    	return 0;
    }
    

    运行结果

    在这里插入图片描述
    也就是说:
    f(x)=3x14+4x13+2x11+x9+x6+x3+12x2+x0(mod5), f(x)=3x^{14}+4x^{13}+2x^{11}+x^9+x^6+x^3+12x^2+x\equiv 0 (mod 5),
    在模5的意义下与:
    3x3+16x2+6x 3x^3+16x^2+6x
    等价.在这个问题中我们的除式选择为:
    x5x x^5-x
    原因只需要用费马小定理解释即可!

    注:在解决这个问题的过程中,我使用的编译器为Visual Studio 2017,
    不同版本的编译器在使用我的代码的过程中可能需要简单调试,这里因给大家造成不便而表示歉意.

    展开全文
  • 一元多项式相加

    2015-11-19 15:24:00
    描述: 对于两个一元多项式,如果需要对他们...(2)多项式中系数不为零的每一项,保存其系数与该项的次数。下面分别用这两种思路实现一元多项式加法操作。 思路一(数组实现): 数据结构定义: 1 typedef str...

    描述:

    对于两个一元多项式,如果需要对他们进行多项式相加操作,常见的两种思路如下:(1)对于一个多项式,保存其最高项次数HighPowder,以及一个该多项式对应次数分别为0-HighPowder的各项的系数的数组()。(2)多项式中系数不为零的每一项,保存其系数与该项的次数。下面分别用这两种思路实现一元多项式加法操作。

    思路一(数组实现):

    数据结构定义:

    1 typedef struct Poly
    2 {
    3     int CoeffArray[11];
    4     int HighPower;
    5 } *Polynomial;

    实现:

     1 #include <stdio.h>
     2 #include <stdlib.h>
     3 
     4 typedef struct Poly
     5 {
     6     int CoeffArray[11];
     7     int HighPower;
     8 } *Polynomial;
     9 
    10 void ZeroPolynomial(Polynomial Poly)
    11 {
    12     int i;
    13     for(i = 0; i < 11; i++)
    14     {
    15         Poly->CoeffArray[i] = 0;
    16     }
    17     Poly->HighPower = 0;
    18 }
    19 
    20 void AddPolynomial(Polynomial Poly1,Polynomial Poly2, Polynomial PolySum)
    21 {
    22     int i;
    23     ZeroPolynomial(PolySum);
    24     PolySum->HighPower = Poly1->HighPower > Poly2->HighPower?
    25         Poly1->HighPower:Poly2->HighPower;
    26     for(i = PolySum->HighPower; i >= 0 ; i--)
    27     {
    28         PolySum->CoeffArray[i] = Poly1->CoeffArray[i] + Poly2->CoeffArray[i];
    29     }
    30 }
    31 
    32 int main(void)
    33 {
    34     int i,j,k;
    35     Polynomial P1,P2,Sum;
    36     P1 = malloc(sizeof(struct Poly));
    37     P2 = malloc(sizeof(struct Poly));
    38     Sum = malloc(sizeof(struct Poly));
    39     //初始化
    40     ZeroPolynomial(P1);
    41     ZeroPolynomial(P2);
    42     P1->HighPower = 10;
    43     for(i = 10; i >= 0; i--)
    44     {
    45         P1->CoeffArray[i] = i;
    46     }
    47     
    48     P2->HighPower = 8;
    49     for(j = 8; j >=0; j--)
    50     {
    51         P2->CoeffArray[j] = j;
    52     }
    53     P2->CoeffArray[8] = 8;
    54     AddPolynomial(P1,P2,Sum);
    55 
    56     printf("The high power of the Polynomial is %d\n",Sum->HighPower);
    57     for(k = 0; k <= 10; k++)
    58     {
    59         printf("The Coeff of power %d is %d\n",k,Sum->CoeffArray[k]);
    60     }
    61 
    62     return 0;
    63 }

    它适合大部分项都有的稠密多项式。

    思路二(单链表实现):

    数据结构定义:

    1 typedef struct PolyNode *PtrToNode;
    2 
    3 //定义链表节点,也就是多项式中的某一项;
    4 typedef struct PolyNode
    5 {
    6     int Coeff;
    7     int Exponent;
    8     PtrToNode Next;
    9 } PolyNode;

     

    实现:

      1 #include <stdio.h>
      2 #include <stdlib.h>
      3 
      4 typedef struct PolyNode *PtrToNode;
      5 
      6 //定义链表节点,也就是多项式中的某一项;
      7 typedef struct PolyNode
      8 {
      9     int Coeff;
     10     int Exponent;
     11     PtrToNode Next;
     12 } PolyNode;
     13 
     14 
     15 typedef PtrToNode Polynomial;
     16 
     17 /************************************************************
     18 *多项式相加的函数:
     19 *P、Q为存储两个多项式各项的单链表(含头结点)
     20 *Sum为多项式相加结果存放的单链表
     21 *
     22 ************************************************************/
     23 void AddPolynomial(Polynomial P,Polynomial Q,Polynomial Sum)
     24 {
     25     Polynomial PIndex,QIndex,SumIndex;
     26     PIndex = P->Next;
     27     QIndex = Q->Next;
     28     SumIndex = Sum;
     29     while(!(PIndex == NULL && QIndex == NULL))
     30     {
     31         if(PIndex==NULL)
     32         {
     33             SumIndex->Next = QIndex;
     34             QIndex = QIndex->Next;
     35             SumIndex = SumIndex->Next;
     36         }
     37         else if(QIndex == NULL)
     38         {
     39             SumIndex->Next = PIndex;
     40             PIndex = PIndex->Next;
     41             SumIndex = SumIndex->Next;
     42         }
     43         else
     44         {
     45             if(PIndex->Exponent > QIndex->Exponent)
     46             {
     47                 SumIndex->Next = PIndex;
     48                 PIndex = PIndex->Next;
     49                 SumIndex = SumIndex->Next;
     50                 //continue在判断下面if条件时会有异常,类似Java
     51                 //的空引用异常
     52                 continue;
     53             }
     54             if(PIndex->Exponent == QIndex->Exponent)
     55             {
     56                 Polynomial PP = malloc(sizeof(struct PolyNode));
     57                 PP->Exponent = PIndex->Exponent;
     58                 PP->Coeff = PIndex->Coeff + QIndex->Coeff;
     59                 SumIndex->Next = PP;
     60                 PIndex = PIndex->Next;
     61                 QIndex = QIndex->Next;
     62                 SumIndex = SumIndex->Next;
     63                 continue;
     64             }
     65             if(PIndex->Exponent < QIndex->Exponent)
     66             {
     67                 SumIndex->Next = QIndex;
     68                 QIndex = QIndex->Next;
     69                 SumIndex = SumIndex->Next;
     70                 continue;
     71             }
     72         }
     73     }
     74     SumIndex->Next = NULL;
     75 }
     76 
     77 /************************************************************
     78 *遍历单链表(含头结点)函数:
     79 *P:待遍历的链表
     80 *************************************************************/
     81 void TraversePolynomial(Polynomial P)
     82 {
     83     Polynomial Tmp = P->Next;
     84     while(Tmp != NULL)
     85     {
     86         printf("Coeff is %d and Exponent is %d\n",Tmp->Coeff,Tmp->Exponent);
     87         Tmp = Tmp->Next;
     88     }
     89 }
     90 
     91 
     92 
     93 int main(void)
     94 {
     95     Polynomial Poly1,Poly2,Poly3,Poly11,Poly22;
     96     int i,j;
     97     Poly1 = malloc(sizeof(struct PolyNode));
     98     Poly2 = malloc(sizeof(struct PolyNode));
     99     Poly3 = malloc(sizeof(struct PolyNode));
    100     Poly11 = Poly1;
    101     Poly22 = Poly2;
    102 
    103     //创建两个链表时,需要保证是按照指数递减的方式构造的
    104     for(i = 5;i >= 1;i--)
    105     {
    106         Polynomial Tmp  = malloc(sizeof(struct PolyNode));
    107         Tmp->Coeff = i;
    108         Tmp->Exponent = i;
    109         Poly11->Next = Tmp;
    110         Poly11 = Poly11->Next;
    111     }
    112     Poly11->Next = NULL;
    113     for(j = 11;j >= 3;j--)
    114     {
    115         Polynomial Tmp  = malloc(sizeof(struct PolyNode));
    116         Tmp->Coeff = j;
    117         Tmp->Exponent = j;
    118         Poly22->Next = Tmp;
    119         Poly22 = Poly22->Next;
    120     }
    121     Poly22->Next = NULL;
    122     TraversePolynomial(Poly1);
    123     printf("*****************************************\n");
    124     TraversePolynomial(Poly2);
    125     AddPolynomial(Poly1,Poly2,Poly3);
    126     printf("*****************************************\n");
    127     TraversePolynomial(Poly3);
    128     return 0;
    129 }

     

     

    原文链接

     

    转载于:https://www.cnblogs.com/xjtuchenpeng/p/4977779.html

    展开全文
  • 然而在通常的应用中,多项式的次数可能很高且变化很大,使得顺序存储结构的最大长度很难 决定。特别是在处理形如:S(x) = 1+3x10000+2x20000的多项式时,就要用一长度20001的线性表来 表示,表中仅有三个非元素,...
  • 推广和改进了邱淦悌等人有关定理,主要结果如下:设f是开平面内非常数亚纯函数,b任一非有穷复数,Ff常系数齐次微分多项式,且F不恒为常数,其次数是λ,权是Γ。若f,F分担b IM,(3λ+2)δ(0,f)+2Γ...
  • 多项式全家桶

    2018-07-24 12:35:00
    开头Orz yww,Orz xfz,Orz dtz,Orz lyy 部分转载自yww博客、dtz博客 一些定义 一个关于$x$的多项式$A(x)...其中$a_0,a_1,a_2......a_{n-1}$称为多项式$A(x)$系数,如果$A(x)$最高次数的一个非项系数$...

    开头Orz yww,Orz xfz,Orz dtz,Orz lyy

    部分转载自yww的博客dtz的博客

    一些定义

    一个关于$x$的多项式$A(x)$可以表示为如下形式和:

    $$A(x)=\sum\limits_{i=0}^{n-1}a_{i}x^{i}$$

    其中$a_0,a_1,a_2......a_{n-1}$称为多项式$A(x)$的系数,如果$A(x)$最高次数的一个非零项系数为$a_k$,则称其次数为$k$。任意一个严格大于$k$的整数都可以作为这个多项式的次数界,即对于一个次数界为$n$的多项式,他的次数可以是$[0,n-1]$中的任意一个整数。

    多项式加减法

    多项式乘法

    直接FFT or NTT

    代码:

    FFT:

     1 #include<iostream>
     2 #include<cstring>
     3 #include<cstdio>
     4 #include<cmath>
     5 #define pw(n) (1<<n)
     6 using namespace std;
     7 const double pi=acos(-1);
     8 struct complex{
     9     double a,b;
    10     complex(double _a=0,double _b=0){
    11         a=_a;
    12         b=_b;
    13     }
    14     friend complex operator +(complex x,complex y){return complex(x.a+y.a,x.b+y.b);}
    15     friend complex operator -(complex x,complex y){return complex(x.a-y.a,x.b-y.b);}
    16     friend complex operator *(complex x,complex y){return complex(x.a*y.a-x.b*y.b,x.a*y.b+x.b*y.a);}
    17     friend complex operator *(complex x,double y){return complex(x.a*y,x.b*y);}
    18     friend complex operator /(complex x,double y){return complex(x.a/y,x.b/y);}
    19 }a[100001],b[100001];
    20 int n,m,bit,bitnum=0,rev[pw(20)];
    21 void getrev(int l){//Reverse
    22     for(int i=0;i<pw(l);i++){
    23         rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
    24     }
    25 }
    26 void FFT(complex *s,int op){
    27     for(int i=0;i<bit;i++)if(i<rev[i])swap(s[i],s[rev[i]]);
    28     for(int i=1;i<bit;i<<=1){
    29         complex w(cos(pi/i),op*sin(pi/i));
    30         for(int p=i<<1,j=0;j<bit;j+=p){//Butterfly
    31             complex wk(1,0);
    32             for(int k=j;k<i+j;k++,wk=wk*w){
    33                 complex x=s[k],y=wk*s[k+i];
    34                 s[k]=x+y;
    35                 s[k+i]=x-y;
    36             }
    37         }
    38     }
    39     if(op==-1){
    40         for(int i=0;i<=bit;i++){
    41             s[i]=s[i]/(double)bit;
    42         }
    43     }
    44 }
    45 int main(){
    46     scanf("%d%d",&n,&m);
    47     for(int i=0;i<=n;i++)scanf("%lf",&a[i].a);
    48     for(int i=0;i<=m;i++)scanf("%lf",&b[i].a);
    49     m+=n;
    50     for(bit=1;bit<=m;bit<<=1)bitnum++;
    51     getrev(bitnum);
    52     FFT(a,1);
    53     FFT(b,1);
    54     for(int i=0;i<=bit;i++)a[i]=a[i]*b[i];
    55     FFT(a,-1);
    56     for(int i=0;i<=m;i++)printf("%d ",(int)(a[i].a+0.5));
    57     return 0;
    58 }

    NTT:

     1 #include<algorithm>
     2 #include<iostream>
     3 #include<cstring>
     4 #include<cstdio>
     5 #include<cmath>
     6 #define pw(n) (1<<n)
     7 using namespace std;
     8 const int N=262144,P=998244353,g=3;//或P=1004535809
     9 int n,m,bit,bitnum=0,a[N+5],b[N+5],rev[N+5];
    10 void getrev(int l){
    11     for(int i=0;i<pw(l);i++){
    12         rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
    13     }
    14 }
    15 int fastpow(int a,int b){
    16     int ans=1;
    17     for(;b;b>>=1,a=1LL*a*a%P){
    18         if(b&1)ans=1LL*ans*a%P;
    19     }
    20     return ans;
    21 }
    22 void NTT(int *s,int op){
    23     for(int i=0;i<bit;i++)if(i<rev[i])swap(s[i],s[rev[i]]);
    24     for(int i=1;i<bit;i<<=1){
    25         int w=fastpow(g,(P-1)/(i<<1));
    26         for(int p=i<<1,j=0;j<bit;j+=p){
    27             int wk=1;
    28             for(int k=j;k<i+j;k++,wk=1LL*wk*w%P){
    29                 int x=s[k],y=1LL*s[k+i]*wk%P;
    30                 s[k]=(x+y)%P;
    31                 s[k+i]=(x-y+P)%P;
    32             }
    33         }
    34     }
    35     if(op==-1){
    36         reverse(s+1,s+bit);
    37         int inv=fastpow(bit,P-2);
    38         for(int i=0;i<bit;i++)a[i]=1LL*a[i]*inv%P;
    39     }
    40 }
    41 int main(){
    42     scanf("%d%d",&n,&m);
    43     for(int i=0;i<=n;i++)scanf("%d",&a[i]);
    44     for(int i=0;i<=m;i++)scanf("%d",&b[i]);
    45     m+=n;
    46     for(bit=1;bit<=m;bit<<=1)bitnum++;
    47     getrev(bitnum);
    48     NTT(a,1);
    49     NTT(b,1);
    50     for(int i=0;i<bit;i++)a[i]=1LL*a[i]*b[i]%P;
    51     NTT(a,-1);
    52     for(int i=0;i<=m;i++)printf("%d ",a[i]);
    53     return 0;
    54 } 

    时间复杂度:$O(nlogn)$

    模板:洛谷P3803

    Upd:补一个任意模数fft(mtt)

     

     1 #include<algorithm>
     2 #include<iostream>
     3 #include<cstring>
     4 #include<vector>
     5 #include<cstdio>
     6 #include<cmath>
     7 #include<queue>
     8 #include<stack>
     9 #include<map>
    10 #include<set>
    11 using namespace std;
    12 typedef long long ll;
    13 const long double pi=acos(-1);
    14 struct complex{
    15     long double a,b;
    16     complex(long double _a=0,long double _b=0){
    17         a=_a;
    18         b=_b;
    19     }
    20     friend complex operator +(complex x,complex y){return complex(x.a+y.a,x.b+y.b);}
    21     friend complex operator -(complex x,complex y){return complex(x.a-y.a,x.b-y.b);}
    22     friend complex operator *(complex x,complex y){return complex(x.a*y.a-x.b*y.b,x.a*y.b+x.b*y.a);}
    23     friend complex operator *(complex x,long double y){return complex(x.a*y,x.b*y);}
    24     friend complex operator /(complex x,long double y){return complex(x.a/y,x.b/y);}
    25 }a[1000001],b[1000001],c[1000001],d[1000001];
    26 int n,m,p,bit=1,bitnum=0,A[1000001],B[1000001],rev[1000001];
    27 void fft(complex *s,int op){
    28     for(int i=0;i<bit;i++)if(i<rev[i])swap(s[i],s[rev[i]]);
    29     for(int i=1;i<bit;i<<=1){
    30         complex w(cos(pi/i),op*sin(pi/i));
    31         for(int pp=i<<1,j=0;j<bit;j+=pp){
    32             complex wk(1,0);
    33             for(int k=j;k<i+j;k++,wk=wk*w){
    34                 complex x=s[k],y=wk*s[k+i];
    35                 s[k]=x+y;
    36                 s[k+i]=x-y;
    37             }
    38         }
    39     }
    40     if(op==-1){
    41         for(int i=0;i<bit;i++){
    42             s[i]=s[i]/(double)bit;
    43         }
    44     }
    45 }
    46 int main(){
    47     scanf("%d%d%d",&n,&m,&p);
    48     for(int i=0;i<=n;i++)scanf("%d",&A[i]);
    49     for(int i=0;i<=m;i++)scanf("%d",&B[i]);
    50     n+=m+1;
    51     for(;bit<=n;bit<<=1)++bitnum;
    52     for(int i=0;i<bit;i++){
    53         rev[i]=(rev[i>>1]>>1|((i&1)<<(bitnum-1)));
    54     }
    55     for(int i=0;i<bit;i++){
    56         a[i].a=A[i]>>15;
    57         b[i].a=A[i]&32767;
    58         c[i].a=B[i]>>15;
    59         d[i].a=B[i]&32767;
    60     }
    61     fft(a,1);
    62     fft(b,1);
    63     fft(c,1);
    64     fft(d,1);
    65     for(int i=0;i<bit;i++){
    66         complex s1=a[i],s2=b[i],s3=c[i],s4=d[i];
    67         a[i]=s1*s3;
    68         b[i]=s1*s4+s2*s3;
    69         c[i]=s2*s4;
    70     }
    71     fft(a,-1);
    72     fft(b,-1);
    73     fft(c,-1);
    74     for(int i=0;i<n;i++){
    75         printf("%lld ",(ll)((ll)(a[i].a+0.5)%p*(1LL<<30)%p+(ll)(b[i].a+0.5)%p*(1LL<<15)%p+(ll)(c[i].a+0.5)%p)%p);
    76     }
    77     return 0;
    78 }

     

    模板:洛谷P4245

    多项式求逆

    如果存在多项式$B(x)$使得:

    $$A(x)B(x)≡1(\mod  x^n)$$

    则$B(x)$称为$A(x)$在模$x^n$意义下的乘法逆元;

    一个多项式存在乘法逆元的充要条件是他的常数项存在乘法逆元(不会证)

    假设已经求出了$B'(x)$满足:

    $$A(x)B'(x)≡1(\mod  x^{\lceil \frac{n}{2}\rceil})$$

    $$A(x)B'(x)-1≡0(\mod  x^{\lceil \frac{n}{2}\rceil})$$
    $$(A(x)B'(x)-1)^2≡0(\mod x^n)$$

    $$A^2(x)B'^2(x)-2A(x)B'(x)+1≡0(\mod  x^n)$$
    $$2A(x)B'(x)-A^2(x)B'^2(x)≡1(\mod  x^n)$$

    将此式减去$A(x)B(x)≡1(mod x^n)$,可得

    $$2A(x)B'(x)-A^2(x)B'^2(x)-A(x)B(x)≡0(\mod  x^n)$$

    约去$A(x)$,得

    $$2B'(x)-A(x)B'^2(x)-B(x)≡0(\mod  x^n)$$
    $$2B'(x)-A(x)B'^2(x)≡B(x) (\mod  x^n)$$

     于是就可以每次算出$2B'(x)-A(x)B'^2(x)$然后赋值给$B(x)$进行下一次迭代,因此时间复杂度为$T(n)=T(\frac{n}{2})+O(nlogn)=O(nlogn)$,看着像是两个$log$的,实际上只有一个,这里提供一个lyy的证明:

    设$n=2^k$

    则$T(n)=T(\frac{n}{2})+O(nlogn)=\sum\limits_{i=0}^{k}\frac{n}{2^i}logn=nlogn$

    dtz:轻松证明

    代码:

     1 #include<algorithm>
     2 #include<iostream>
     3 #include<cstring>
     4 #include<vector>
     5 #include<cstdio>
     6 #include<cmath>
     7 #include<queue>
     8 #include<stack>
     9 #include<map>
    10 #include<set>
    11 using namespace std;
    12 typedef long long ll;
    13 const int p=998244353,g=3;
    14 int n,m,a[500001],b[500001],rev[500001],tmp[500001];
    15 int fastpow(int x,int y){
    16     int ret=1;
    17     for(;y;y>>=1,x=(ll)x*x%p){
    18         if(y&1)ret=(ll)ret*x%p;
    19     }
    20     return ret;
    21 }
    22 void ntt(int s[],int n,int op){
    23     for(int i=0;i<n;i++)if(i<rev[i])swap(s[i],s[rev[i]]);
    24     for(int i=1;i<n;i<<=1){
    25         int w=fastpow(g,(p-1)/(i<<1));
    26         for(int pp=i<<1,j=0;j<n;j+=pp){
    27             int wk=1;
    28             for(int k=j;k<i+j;k++,wk=(ll)wk*w%p){
    29                 int x=s[k],y=(ll)s[k+i]*wk%p;
    30                 s[k]=(x+y)%p;
    31                 s[k+i]=(x-y+p)%p;
    32             }
    33         }
    34     }
    35     if(op==-1){
    36         reverse(s+1,s+n);
    37         int inv=fastpow(n,p-2);
    38         for(int i=0;i<n;i++){
    39             s[i]=(ll)s[i]*inv%p;
    40         }
    41     }
    42 }
    43 void GetInv(int a[],int b[],int l){
    44     if(l==1){
    45         b[0]=fastpow(a[0],p-2);
    46         return;
    47     }
    48     GetInv(a,b,(l+1)/2);
    49     int bit=1,bitnum=0;
    50     for(;bit<l*2;bit<<=1)bitnum++;
    51     for(int i=1;i<bit;i++){
    52         rev[i]=(rev[i>>1]>>1|(i&1)<<(bitnum-1));
    53     }
    54     for(int i=0;i<l;i++)tmp[i]=a[i];
    55     for(int i=l;i<bit;i++)tmp[i]=0;
    56     ntt(tmp,bit,1);
    57     ntt(b,bit,1);
    58     for(int i=0;i<bit;i++)b[i]=(ll)b[i]*((2-(ll)tmp[i]*b[i]%p+p)%p)%p;
    59     ntt(b,bit,-1);
    60     for(int i=l;i<bit;i++)b[i]=0;
    61 }
    62 int main(){
    63     scanf("%d",&n);
    64     for(int i=0;i<n;i++)scanf("%d",&a[i]);
    65     GetInv(a,b,n);
    66     for(int i=0;i<n;i++)printf("%d ",b[i]);
    67     return 0;
    68 } 

    模板:洛谷P4238、洛谷P4239(加强版)

    多项式除法(取模)

     给出多项式$A(x)$,$B(x)$,求多项式$C(x)$,$D(x)$满足

    $$A(x)=B(x)C(x)+D(x)$$

    乍一看很难搞,于是我们需要一些玄(fa)学操作。

    定义反转操作,对于一个次数为$n$的多项式,有

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

    这个有什么用呢?这样可以把每个原本次数是$k$的项次数变为$n-k$,相当于把整个多项式的系数反转了过来。

    设$A(x)$的次数为$n$,$B(x)$的次数为$m$,则$C(x)$的次数为$n-m$,$D(x)$的次数为$m-1$

    用$1/x$代替$x$,两边乘以$x^n$,则:

    $$x^{n}A(\frac{1}{x})=x^{m}B(\frac{1}{x})x^{n-m}C(\frac{1}{x})+x^{n-m+1}x^{m-1}D(\frac{1}{x})$$

    $$A^R(x)=B^R(x)C^R(x)+x^{n-m+1}D^R(x)$$

    然后惊人的事情就发生了!我们把整个式子放到模$x^{n-m+1}$意义下,有

    $$A^R(x)=B^R(x)C^R(x)(\mod x^{n-m+1})$$

    $$C^R(x)=A^R(x)(B^R(x))^{-1}(\mod x^{n-m+1})$$

    于是就做完了。。。

    时间复杂度:$O(nlogn)$

    代码:

     1 #include<algorithm>
     2 #include<iostream>
     3 #include<cstring>
     4 #include<vector>
     5 #include<cstdio>
     6 #include<cmath>
     7 #include<queue>
     8 #include<stack>
     9 #include<map>
    10 #include<set>
    11 using namespace std;
    12 typedef long long ll;
    13 const int p=998244353,g=3;
    14 int n,m,a[500001],b[500001],rev[500001],aa[500001],bb[500001],tmp[500001],invb[500001],c[500001],d[500001];
    15 int fastpow(int x,int y){
    16     int ret=1;
    17     for(;y;y>>=1,x=(ll)x*x%p){
    18         if(y&1)ret=(ll)ret*x%p;
    19     }
    20     return ret;
    21 }
    22 void ntt(int s[],int n,int op){
    23     for(int i=0;i<n;i++)if(i<rev[i])swap(s[i],s[rev[i]]);
    24     for(int i=1;i<n;i<<=1){
    25         int w=fastpow(g,(p-1)/(i<<1));
    26         for(int pp=i<<1,j=0;j<n;j+=pp){
    27             int wk=1;
    28             for(int k=j;k<i+j;k++,wk=(ll)wk*w%p){
    29                 int x=s[k],y=(ll)s[k+i]*wk%p;
    30                 s[k]=(x+y)%p;
    31                 s[k+i]=(x-y+p)%p;
    32             }
    33         }
    34     }
    35     if(op==-1){
    36         reverse(s+1,s+n);
    37         int inv=fastpow(n,p-2);
    38         for(int i=0;i<n;i++){
    39             s[i]=(ll)s[i]*inv%p;
    40         }
    41     }
    42 }
    43 void GetInv(int a[],int b[],int l){
    44     if(l==1){
    45         b[0]=fastpow(a[0],p-2);
    46         return;
    47     }
    48     GetInv(a,b,(l+1)/2);
    49     int bit=1,bitnum=0;
    50     for(;bit<l*2;bit<<=1)bitnum++;
    51     for(int i=1;i<bit;i++){
    52         rev[i]=(rev[i>>1]>>1|(i&1)<<(bitnum-1));
    53     }
    54     for(int i=0;i<l;i++)tmp[i]=a[i];
    55     for(int i=l;i<bit;i++)tmp[i]=0;
    56     ntt(tmp,bit,1);
    57     ntt(b,bit,1);
    58     for(int i=0;i<bit;i++)b[i]=(ll)b[i]*((2-(ll)tmp[i]*b[i]%p+p)%p)%p;
    59     ntt(b,bit,-1);
    60     for(int i=l;i<bit;i++)b[i]=0;
    61 }
    62 void GetMul(int a[],int b[],int c[],int n,int m){
    63     int bit=1,bitnum=0;
    64     for(;bit<=n+m;bit<<=1)bitnum++;
    65     for(int i=0;i<=n;i++)aa[i]=a[i];
    66     for(int i=0;i<=m;i++)bb[i]=b[i];
    67     for(int i=1;i<bit;i++){
    68         rev[i]=(rev[i>>1]>>1|(i&1)<<(bitnum-1));
    69     }
    70     ntt(aa,bit,1);
    71     ntt(bb,bit,1);
    72     for(int i=0;i<bit;i++){
    73         c[i]=(ll)aa[i]*bb[i]%p;
    74         aa[i]=bb[i]=0;
    75     }
    76     ntt(c,bit,-1);
    77 }
    78 int main(){
    79     scanf("%d%d",&n,&m);
    80     for(int i=0;i<=n;i++)scanf("%d",&a[i]);
    81     for(int i=0;i<=m;i++)scanf("%d",&b[i]);
    82     reverse(a,a+n+1);
    83     reverse(b,b+m+1);
    84     GetInv(b,invb,n-m+1);
    85     GetMul(a,invb,c,n-m,n-m);
    86     reverse(c,c+n-m+1);
    87     for(int i=0;i<=n-m;i++){
    88         printf("%d ",c[i]);
    89     }
    90     printf("\n");
    91     reverse(a,a+n+1);
    92     reverse(b,b+m+1);
    93     GetMul(c,b,d,n-m,m);
    94     for(int i=0;i<m;i++)d[i]=(a[i]-d[i]+p)%p;
    95     for(int i=0;i<m;i++)printf("%d ",d[i]);
    96     return 0;
    97 } 

    模板:洛谷P4512

    多项式开根

    给出多项式$A(x)$,求多项式$B(x)$满足

    $$B^2(x)≡A(x)(\mod x^n)$$

    类似于求逆,设已经求出了$B'(x)$满足

    $$B'^2(x)≡A(x)(\mod x^{\lceil \frac{n}{2}\rceil})$$

    $$B'^2(x)-A(x)≡0(\mod x^{\lceil \frac{n}{2}\rceil})$$

    $$(B'^2(x)-A(x))^2≡0(\mod x^n)$$

    $$B'^4(x)-2B'^2(x)A(x)+A^2(x)≡0(\mod x^n)$$

    $$B'^4(x)+2B'^2(x)A(x)+A^2(x)≡4B'^2(x)A(x)(\mod x^n)$$

    $$(B'^2(x)+A(x))^2≡(2B'^2(x))A(x)(\mod x^n)$$

    $$(\frac{B'^2(x)+A(x)}{2B'^2(x)})^2≡A(x)(\mod x^n)$$

    因此

    $$B(x)=\frac{B'^2(x)+A(x)}{2B'^2(x)}$$

    每次倍增向上重新赋值,时间复杂度$O(nlogn)$

    代码:

     

      1 #include<algorithm>
      2 #include<iostream>
      3 #include<cstring>
      4 #include<vector>
      5 #include<cstdio>
      6 #include<cmath>
      7 #include<queue>
      8 #include<stack>
      9 #include<map>
     10 #include<set>
     11 using namespace std;
     12 typedef long long ll;
     13 const int p=998244353,g=3;
     14 int inv_2,n,m,bit,bitnum=0,x,a[500001],b[500001],tmp[500001],c[500001],d[500001],rev[500001];
     15 int fastpow(int x,int y){
     16     int ret=1;
     17     for(;y;y>>=1,x=(ll)x*x%p){
     18         if(y&1)ret=(ll)ret*x%p;
     19     }
     20     return ret;
     21 }
     22 void ntt(int s[],int n,int op){
     23     for(int i=0;i<n;i++)if(i<rev[i])swap(s[i],s[rev[i]]);
     24     for(int i=1;i<n;i<<=1){
     25         int w=fastpow(g,(p-1)/(i<<1));
     26         for(int pp=i<<1,j=0;j<n;j+=pp){
     27             int wk=1;
     28             for(int k=j;k<i+j;k++,wk=(ll)wk*w%p){
     29                 int x=s[k],y=(ll)s[k+i]*wk%p;
     30                 s[k]=(x+y)%p;
     31                 s[k+i]=(x-y+p)%p;
     32             }
     33         }
     34     }
     35     if(op==-1){
     36         reverse(s+1,s+n);
     37         int inv=fastpow(n,p-2);
     38         for(int i=0;i<n;i++){
     39             s[i]=(ll)s[i]*inv%p;
     40         }
     41     }
     42 }
     43 void GetInv(int a[],int b[],int l){
     44     if(l==1){
     45         b[0]=fastpow(a[0],p-2);
     46         return;
     47     }
     48     GetInv(a,b,(l+1)/2);
     49     int bit=1,bitnum=0;
     50     for(;bit<l*2;bit<<=1)bitnum++;
     51     for(int i=1;i<bit;i++){
     52         rev[i]=(rev[i>>1]>>1|(i&1)<<(bitnum-1));
     53     }
     54     for(int i=0;i<l;i++)tmp[i]=a[i];
     55     for(int i=l;i<bit;i++)tmp[i]=0;
     56     ntt(tmp,bit,1);
     57     ntt(b,bit,1);
     58     for(int i=0;i<bit;i++)b[i]=(ll)b[i]*((2-(ll)tmp[i]*b[i]%p+p)%p)%p;
     59     ntt(b,bit,-1);
     60     for(int i=l;i<bit;i++)b[i]=0;
     61 }
     62 void GetSqrt(int a[],int b[],int n){
     63     if(n==1){
     64         b[0]=a[0];
     65         return;
     66     }
     67     GetSqrt(a,b,n/2);
     68     for(int i=0;i<=n;i++)c[i]=a[i];
     69     GetInv(b,d,n);
     70     int bit=1,bitnum=0;
     71     for(;bit<n*2;bit<<=1)bitnum++;
     72     for(int i=1;i<bit;i++){
     73         rev[i]=(rev[i>>1]>>1|(i&1)<<(bitnum-1));
     74     }
     75     ntt(c,n*2,1);
     76     ntt(d,n*2,1);
     77     for(int i=0;i<n*2;i++){
     78         d[i]=(ll)d[i]*c[i]%p;
     79     }
     80     ntt(d,n*2,-1);
     81     for(int i=0;i<n;i++){
     82         b[i]=(ll)(b[i]+d[i])%p*inv_2%p;
     83     }
     84     for(int i=0;i<n*2;i++)c[i]=d[i]=0;
     85 }
     86 int main(){
     87     scanf("%d%d",&n,&m);
     88     inv_2=fastpow(2,p-2);
     89     for(int i=1;i<=n;i++)scanf("%d",&x),a[x]++;
     90     for(bit=1;bit<=m;bit<<=1);
     91     for(int i=0;i<bit;i++){
     92         a[i]=(-4*a[i]+p)%p;
     93     }
     94     a[0]++;
     95     GetSqrt(a,b,bit);
     96     for(int i=0;i<bit;i++)a[i]=0;
     97     b[0]=(b[0]+1)%p;
     98     GetInv(b,c,bit);
     99     for(int i=0;i<=m;i++)c[i]=(c[i]+c[i])%p;
    100     for(int i=1;i<=m;i++)printf("%d\n",c[i]);
    101     return 0;
    102 }

     

    模板(?):BZOJ3625小朋友和二叉树

    多项式对数函数

     第一次知道多项式还有相应的初等函数……(连三角函数都有……)

    给出(这个我也不知道叫什么)$A(x)=\sum\limits_{i\ge 1}a_{i}x^{i}$

    则有定义:

    $$ln(1-A(x))=-\sum\limits_{i\ge 1}\frac{A(x)^i}{i}$$

    则若有多项式$A(x)=\sum\limits_{i\ge 1}a_{i}x^{i}+1$,要求多项式$B(x)$满足$B(x)=ln(A(x))$,直接求导即可:

    $$B(x)=\int\frac{A'(x)}{A(x)}$$

    要求个逆元,时间复杂度$O(nlogn)$

    代码:

     1 #include<algorithm>
     2 #include<iostream>
     3 #include<cstring>
     4 #include<vector>
     5 #include<cstdio>
     6 #include<cmath>
     7 #include<queue>
     8 #include<stack>
     9 #include<map>
    10 #include<set>
    11 using namespace std;
    12 typedef long long ll;
    13 const int p=998244353,g=3;
    14 int n,m,a[500001],b[500001],rev[500001],s[500001],ss[500001],tmp[500001];
    15 int fastpow(int x,int y){
    16     int ret=1;
    17     for(;y;y>>=1,x=(ll)x*x%p){
    18         if(y&1)ret=(ll)ret*x%p;
    19     }
    20     return ret;
    21 }
    22 void ntt(int s[],int n,int op){
    23     for(int i=0;i<n;i++)if(i<rev[i])swap(s[i],s[rev[i]]);
    24     for(int i=1;i<n;i<<=1){
    25         int w=fastpow(g,(p-1)/(i<<1));
    26         for(int pp=i<<1,j=0;j<n;j+=pp){
    27             int wk=1;
    28             for(int k=j;k<i+j;k++,wk=(ll)wk*w%p){
    29                 int x=s[k],y=(ll)s[k+i]*wk%p;
    30                 s[k]=(x+y)%p;
    31                 s[k+i]=(x-y+p)%p;
    32             }
    33         }
    34     }
    35     if(op==-1){
    36         reverse(s+1,s+n);
    37         int inv=fastpow(n,p-2);
    38         for(int i=0;i<n;i++){
    39             s[i]=(ll)s[i]*inv%p;
    40         }
    41     }
    42 }
    43 void GetInv(int a[],int b[],int l){
    44     if(l==1){
    45         b[0]=fastpow(a[0],p-2);
    46         return;
    47     }
    48     GetInv(a,b,(l+1)/2);
    49     int bit=1,bitnum=0;
    50     for(;bit<l*2;bit<<=1)bitnum++;
    51     for(int i=1;i<bit;i++){
    52         rev[i]=(rev[i>>1]>>1|(i&1)<<(bitnum-1));
    53     }
    54     for(int i=0;i<l;i++)tmp[i]=a[i];
    55     for(int i=l;i<bit;i++)tmp[i]=0;
    56     ntt(tmp,bit,1);
    57     ntt(b,bit,1);
    58     for(int i=0;i<bit;i++)b[i]=(ll)b[i]*((2-(ll)tmp[i]*b[i]%p+p)%p)%p;
    59     ntt(b,bit,-1);
    60     for(int i=l;i<bit;i++)b[i]=0;
    61 }
    62 void GetDerivation(int a[],int b[],int n){
    63     for(int i=1;i<n;i++)b[i-1]=(ll)i*a[i]%p;
    64     b[n-1]=0;
    65 }
    66 void GetIntegral(int a[],int b[],int n){
    67     for(int i=1;i<n;i++)b[i]=(ll)a[i-1]*fastpow(i,p-2)%p;
    68     b[0]=0;
    69 }
    70 void Getln(int a[],int b[],int n){
    71     GetDerivation(a,s,n);
    72     GetInv(a,ss,n);
    73     int bit,bitnum=0;
    74     for(bit=1;bit<=n;bit<<=1)bitnum++;
    75     for(int i=1;i<bit;i++){
    76         rev[i]=(rev[i>>1]>>1|(i&1)<<(bitnum-1));
    77     }
    78     ntt(s,bit,1);
    79     ntt(ss,bit,1);
    80     for(int i=0;i<bit;i++)s[i]=(ll)s[i]*ss[i]%p;
    81     ntt(s,bit,-1);
    82     GetIntegral(s,b,n);
    83 }
    84 int main(){
    85     int bit; 
    86     scanf("%d",&n);
    87     for(int i=0;i<n;i++)scanf("%d",&a[i]);
    88     for(bit=1;bit<=n;bit<<=1);
    89     Getln(a,b,bit);
    90     for(int i=0;i<n;i++)printf("%d ",b[i]);
    91     return 0;
    92 }

    模板:洛谷P4725

    多项式指数函数

    (听说要用牛顿迭代法+泰勒展开?反正我只会背代码)

    直接写式子:设$B(x)=exp(A(x))$,则

    $$B(x)=B_{0}(x)(1-ln(B_{0}(x))+A(x))$$

    其中$B_{0}(x)$表示$B(x)$的前n项,即$B_{0}(x)≡B(x)(\mod x^n)$

    时间复杂度:$O(nlogn)$

    代码:

     

      1 //未验证正确性 
      2 #include<algorithm>
      3 #include<iostream>
      4 #include<cstring>
      5 #include<vector>
      6 #include<cstdio>
      7 #include<cmath>
      8 #include<queue>
      9 #include<stack>
     10 #include<map>
     11 #include<set>
     12 using namespace std;
     13 typedef long long ll;
     14 const int p=998244353,g=3;
     15 int n,m,a[500001],b[500001],rev[500001],s[500001],ss[500001],tmp[500001],c[500001];
     16 int fastpow(int x,int y){
     17     int ret=1;
     18     for(;y;y>>=1,x=(ll)x*x%p){
     19         if(y&1)ret=(ll)ret*x%p;
     20     }
     21     return ret;
     22 }
     23 void ntt(int s[],int n,int op){
     24     for(int i=0;i<n;i++)if(i<rev[i])swap(s[i],s[rev[i]]);
     25     for(int i=1;i<n;i<<=1){
     26         int w=fastpow(g,(p-1)/(i<<1));
     27         for(int pp=i<<1,j=0;j<n;j+=pp){
     28             int wk=1;
     29             for(int k=j;k<i+j;k++,wk=(ll)wk*w%p){
     30                 int x=s[k],y=(ll)s[k+i]*wk%p;
     31                 s[k]=(x+y)%p;
     32                 s[k+i]=(x-y+p)%p;
     33             }
     34         }
     35     }
     36     if(op==-1){
     37         reverse(s+1,s+n);
     38         int inv=fastpow(n,p-2);
     39         for(int i=0;i<n;i++){
     40             s[i]=(ll)s[i]*inv%p;
     41         }
     42     }
     43 }
     44 void GetInv(int a[],int b[],int l){
     45     if(l==1){
     46         b[0]=fastpow(a[0],p-2);
     47         return;
     48     }
     49     GetInv(a,b,(l+1)/2);
     50     int bit=1,bitnum=0;
     51     for(;bit<l*2;bit<<=1)bitnum++;
     52     for(int i=1;i<bit;i++){
     53         rev[i]=(rev[i>>1]>>1|(i&1)<<(bitnum-1));
     54     }
     55     for(int i=0;i<l;i++)tmp[i]=a[i];
     56     for(int i=l;i<bit;i++)tmp[i]=0;
     57     ntt(tmp,bit,1);
     58     ntt(b,bit,1);
     59     for(int i=0;i<bit;i++)b[i]=(ll)b[i]*((2-(ll)tmp[i]*b[i]%p+p)%p)%p;
     60     ntt(b,bit,-1);
     61     for(int i=l;i<bit;i++)b[i]=0;
     62 }
     63 void GetDerivation(int a[],int b[],int n){
     64     for(int i=1;i<n;i++)b[i-1]=(ll)i*a[i]%p;
     65     b[n-1]=0;
     66 }
     67 void GetIntegral(int a[],int b[],int n){
     68     for(int i=1;i<n;i++)b[i]=(ll)a[i-1]*fastpow(i,p-2)%p;
     69     b[0]=0;
     70 }
     71 void Getln(int a[],int b[],int n){
     72     GetDerivation(a,s,n);
     73     GetInv(a,ss,n);
     74     int bit,bitnum=0;
     75     for(bit=1;bit<=n;bit<<=1)bitnum++;
     76     for(int i=1;i<bit;i++){
     77         rev[i]=(rev[i>>1]>>1|(i&1)<<(bitnum-1));
     78     }
     79     ntt(s,bit,1);
     80     ntt(ss,bit,1);
     81     for(int i=0;i<bit;i++)s[i]=(ll)s[i]*ss[i]%p;
     82     ntt(s,bit,-1);
     83     GetIntegral(s,b,n);
     84 }
     85 void Getexp(int a[],int b[],int n){
     86     if(n==1){
     87         b[0]=1;
     88         return;
     89     }
     90     Getexp(a,b,n/2);
     91     Getln(b,c,n);
     92     for(int i=0;i<n;i++)c[i]=(a[i]-c[i]+p)%p;
     93     c[0]++;
     94     int bit=1,bitnum=0;
     95     for(;bit<n*2;bit<<=1)bitnum++;
     96     for(int i=1;i<bit;i++){
     97         rev[i]=(rev[i>>1]>>1|(i&1)<<(bitnum-1));
     98     }
     99     ntt(b,bit,1);
    100     ntt(c,bit,1);
    101     for(int i=0;i<bit;i++){
    102         b[i]=(ll)b[i]*c[i]%p;
    103     }
    104     ntt(b,bit,-1);
    105     for(int i=n;i<bit;i++)b[i]=0;
    106 }
    107 int main(){
    108     int bit; 
    109     scanf("%d",&n);
    110     for(int i=0;i<n;i++)scanf("%d",&a[i]);
    111     for(bit=1;bit<=n;bit<<=1);
    112     Getexp(a,b,bit);
    113     for(int i=0;i<n;i++)printf("%d ",b[i]);
    114     return 0;
    115 }

     

    模板:洛谷P4726

    多项式快速幂

    有了上面的几个,就可以乱搞了(要注意先把最低次项$ax^d$提出来)

    $$A^k(x)=exp(kln(\frac{A(x)}{ax^d}))(ax^d)^k$$

    时间复杂度:$O(nlogn)$(写什么ln和exp肯定是$O(nlognlogk)快速幂啦$)

    代码:

     

     1 #include<algorithm>
     2 #include<iostream>
     3 #include<cstring>
     4 #include<vector>
     5 #include<cstdio>
     6 #include<cmath>
     7 #include<queue>
     8 #include<stack>
     9 #include<map>
    10 #include<set>
    11 using namespace std;
    12 typedef long long ll;
    13 const int p=1004535809,g=3;
    14 int n,m,k,bit=1,bitnum=0,s[100001],tmp[100001],x,_g,rev[100001],blg[100001],inv,G[100001],a[100001],b[100001],c[100001],sum[100001],ans[100001];
    15 int fastpow(int a,int b,int p){
    16     int ret=1;
    17     for(;b;b>>=1,a=(ll)a*a%p){
    18         if(b&1)ret=(ll)ret*a%p;
    19     }
    20     return ret;
    21 }
    22 bool check(int x,int n){
    23     for(int i=2;i*i<=n;i++){
    24         if((n-1)%i==0&&fastpow(x,(n-1)/i,n)==1)return false;
    25     }
    26     return true;
    27 }
    28 int GetG(int n){
    29     if(n==2)return 1;
    30     for(int i=2;;i++){
    31         if(check(i,n))return i;
    32     }
    33 }
    34 void ntt(int s[],int n,int op){
    35     for(int i=0;i<n;i++)if(i<rev[i])swap(s[i],s[rev[i]]);
    36     for(int i=1;i<n;i<<=1){
    37         int w=fastpow(g,(p-1)/(i<<1),p);
    38         for(int pp=i<<1,j=0;j<n;j+=pp){
    39             int wk=1;
    40             for(int k=j;k<i+j;k++,wk=(ll)wk*w%p){
    41                 int x=s[k],y=(ll)s[k+i]*wk%p;
    42                 s[k]=(x+y)%p;
    43                 s[k+i]=(x-y+p)%p;
    44             }
    45         }
    46     }
    47     if(op==-1){
    48         reverse(s+1,s+n);
    49         int inv=fastpow(n,p-2,p);
    50         for(int i=0;i<n;i++){
    51             s[i]=(ll)s[i]*inv%p;
    52         }
    53     }
    54 }
    55 void mul(int aa[],int bb[],int cc[]){
    56     for(int i=0;i<bit;i++)b[i]=aa[i],c[i]=bb[i];
    57     ntt(b,bit,1);
    58     ntt(c,bit,1);
    59     for(int i=0;i<bit;i++)cc[i]=(ll)b[i]*c[i]%p;
    60     ntt(cc,bit,-1);
    61     for(int i=m-1;i<bit;i++){
    62         cc[i-m+1]=(cc[i-m+1]+cc[i])%p;
    63         cc[i]=0;
    64     }
    65 }
    66 void pow(int a[],int n){
    67     ans[0]=1;
    68     for(;n;n>>=1,mul(a,a,a)){
    69         if(n&1)mul(a,ans,ans);
    70     }
    71 }
    72 int main(){
    73     scanf("%d%d%d%d",&n,&m,&x,&k);
    74     for(int i=1;i<=k;i++)scanf("%d",&s[i]);
    75     for(;bit<m*2;bit<<=1)bitnum++;
    76     for(int i=0;i<bit;i++){
    77         rev[i]=(rev[i>>1]>>1|(i&1)<<(bitnum-1));
    78     }
    79     _g=GetG(m);
    80     //printf("%d\n",_g);
    81     G[0]=1;
    82     for(int i=1;i<m-1;i++){
    83         G[i]=(G[i-1]*_g)%m;
    84         blg[G[i]]=i;
    85     }
    86     for(int i=1;i<=k;i++){
    87         if(s[i])tmp[blg[s[i]]]++;
    88     }
    89     pow(tmp,n);
    90     printf("%d",ans[blg[x]]);
    91     return 0;
    92 }

     

    模板(?):BZOJ3992 [SDOI2015]序列统计

    多项式导数&多项式积分

    From yww

    设$A(x)=\sum_{i\ge 0}$,则$A(x)$的形式导数为:

    $$A'(x)=\sum\limits_{i\ge 1}ia_{i}x^{i-1}$$

    $A(x)$同上,则:

    $$\int\limits A(x)=\sum\limits_{i\ge 1}\frac{a_{i-1}}{i}x^i$$

    多点求值&快速插值

    咕咕咕

    移到了这篇博文

    转载于:https://www.cnblogs.com/dcdcbigbig/p/9359329.html

    展开全文
  • 如果多项式的次数为1,不要输出多余的1. 思路就是先找到一个系数不为1的,然后将其输出,输出的时候注意正负,而且要特判是否系数为1,特判是否为次数为1,特判是否是常数项。 如果找到了一个,那么说明多项式不...
  • 2. 一元多项式乘法

    2020-03-31 20:17:17
    计算两个一元多项式的乘积。 输入格式 每行两个多项式,以一个空格分隔,多项式格式 anxn+…+a1x+a0。 每行长度不超过100,0<n<50。 输出格式 每组数据一行,根据次数由高到低顺序输出两个多项式乘积的非...
  • (多项式的)次数:一个多项式A(x)的最高次的非系数是ak ,则称A(x)的次数为k,记作degree(A)=k 次数界:任何严格大于多项式次数的整数都是该多项式的次数界 30.1 多项式的表示 两种表示形式: 系数表示:就是...
  • 多项式的次数n 让给n+1个系数(xn一直到x0的) 判断该多项式在实数域内能否分解两个多项式相乘 分析: 根据实系数多项式因式分解定理 : 每个次数大于的实系数多项式都可以在实数域上唯一地分解成一些一...
  • 给定一个正整数k,你需要寻找一个系数均为0到k−1之间零多项式f(x),满足对于任意整数x均有f(x)modk=0。你给出多项式次数不能超过60000,且最高次系数必须非0。 输入 输入一行,包含一个正整数k。 ...
  • 给定一个正整数kkk,你需要寻找一个系数均为0到k−1之间零多项式f(x),满足对于任意整数x均有f(x)modk=0。你给出多项式次数不能超过60000,且最高次系数必须非0。 输入格式 输入一行,包含...
  • 此 m 文件返回多项式概率密度函数值,参数 N 和 P 位于 X 中值。请注意,除非 X 是整数,否则密度函数为零。 令 {X1, X2, . . . , Xk}, k > 1, 是一组随机变量,每个变量取值 0, 1, . . . , 名词。 假设有 k 个非...
  • 对于一个次数大于0的多项式f(x)f(x)f(x),如果他因式只有非有理数和f(x)f(x)f(x)相伴元,我们称f(x)f(x)f(x)是一个不可约多项式,否则称其为可约 我们容易得出如下定理: 定理: 下述四条命题等价 p(x)p(x)...
  • 齐次多项式:在数学中,齐次多项式是指各项次数均相同的多项式,例如就是一个五次双变元齐次多项式,其各项次数都是五。 齐次方程: 在方程中只含有未知函数及其一阶导数方程称为一阶微分方程。其...
  • PAT Basic Level 1010

    2021-01-26 11:02:24
    输入格式 以指数递降方式输入多项式非零项系数和指数(绝对值均为不超过 ...“零多项式” 指是第一项指数或者次数为0的多项式,需输出**“0 0”**,若第一项指数或者次数均不为零,而末项指数或者次数为0,则该项
  • PAT乙级小结

    2021-03-06 12:49:36
    PAT乙级小结1010一元多项式...可能出现某类数字不存在或结果为0的情况,因此要保存这类数字出现的次数 1014福尔摩斯的约会 1.“对”指上下两个字符串相同位置的两个字符 2.一个星期有7天,因此字母的取值为A~G 3.小时
  • 研究了二阶微分方程f"+A2(z)P(ez)f'+Aa(z)Q(ez)f=0和f"+(Ai(z)P(ez) +D1(z))f'+(A0 (z) Q (ez )+ D0(z))f=0增长性,其中P(ez)与Q(ez)是ez非常数多项式,它们常数项都为零,且次数不相等.证明了该方程每个...
  • 本文为数据结构之线性结构,根据陈越姥姥网课而整合笔记。 举个栗子来引出线性表:...a[i]:项x^i系数ai(下标为i时,对应次数为i系数) 方法2:顺序存储结构表示非项 每个非项aix^i涉及两个信息:系.
  • 研究了微分方程 f(k)+Ak-1f(k-1)+…+A2f"+A1eb2"f'+A0eb2"f=F解增长性,其中 A0(z)、A1(z)、F(z)是级小于 n整函数,Aj(z)(j=2,3,…,k-1)是次数不超过 m的多项式,a、b复常数. 证明了该 方程所有解 f (z)...
  • [ML] = routh_hurwitz(P,N) 该函数根据数值或符号多项式给出劳斯数组,包括两种特殊情况:(1) 行第一个元素为零; (b) 一排。 P 系数数值或符号数组。 在符号变量情况下,需要将它们定义:>> syms abc ......
  • 特别地,我们定义零多项式的次数为负无穷大(-0)。 定义13.对于有限数列{a0,a1,a2…an-1},我们定义它的生成函数为多项式A(x) ∑=ax。对于无限数列{ao,a1,a2…},我们类似地定义它的生成函数为形式幂级数A(x) 定义1.4...
  • PAT A 1009

    2016-11-20 13:42:26
    输入格式两行,每行第一个数表示这个多项式个数k, 接下来每两个数据表示次数和该次数的系数,共k组。I/OSample Input 2 1 2.4 0 3.2 2 2 1.5 1 0.5 Sample Output 3 3 3.6 2 6.0 1 1.6算法由于k,...
  • 1.多项式除法 ...把减得的差当作新的被除式,再按照上面的方法继续演算,直到余式为0或余式的次数低于除式的次数时为止,被除式=除式×商式+余式。若余式为,说明这个多项式能被另一个多项式整除...
  • pat 1009

    2020-06-25 21:43:31
    a1009 题目大意 多项式乘法。...经过加法后,如果bi为0,那么次数就减一。,然后再次利用sort函数进行倒序输出就可以了。 代码 #include <iostream> #include <vector> #include <al
  • 2、上述两种方法误差取 ,最大迭代次数为200,初始向量为向量,方法是否收敛。3、已知定义在[0,3 ]上函数 。取等距离5个节点,求函数 Lagrange插值多项式 。4、已知函数 ,在[-1,1]上取21个节点。求Lagrange...
  • 选择正确的多项式次数在回归拟合中扮演重要角色,如果选择的次数太高,过拟合的可能性将大大提高。 假设有三个类(123),1:23、2:13、3:12共三种分法。有n个类就有n个1:rest模型。 Sigmoid函数用于转换输出结果...

空空如也

空空如也

1 2
收藏数 33
精华内容 13
关键字:

零多项式的次数为0