多项式加法和乘法
- 多项式的加法
- 题目描述
- 输入输出
- 样例
- 步骤
- 代码段
- 全局变量设定
- 新建结点
- 合并链表
- 完整代码
- 多项式乘法
- 题目描述
- 输入输出
- 样例
- 代码段
- 计算两多项式结果
- 输入
- 完整代码
多项式的加法
题目描述
输入输出
样例
步骤
总体思想是用链表来做
① 我们发现输入样例中，系数和指数是分开输入的。也就是说，输入系数的时候，我们并不知道他对应的指数是多少。因此，我们先定义一个两个数组，一个放系数，一个放指数，然后转换为结点（用结构体，存放每一项的系数和指数），放进链表。
②输入第二个多项式的时候，要在合适的地方插入链表
- 如果遍历到指数相同的节点，则指数相加，不建立新的节点
- 如果遍历到第一个指数比自己大的节点，则插入到这个节点之前
- 如果直接遍历到链表尾端了，那就插在最后
代码段
全局变量设定
typedef struct node{//存放系数和指数
ll ind;
ll exp;
struct node* next;
}NODE;
NODE* head;//合并之后链表的头结点
int n,m;//多项式1和2的长度
ll ret;//记录系数非零的节点数目
注意一点，因为是多组数据输入，因此每一次都要确保全局变量ret清零
新建结点
NODE* createNode(ll i,ll e){
NODE* newnode = (NODE*)malloc(sizeof(NODE));
newnode->ind=i;
newnode->exp=e;
newnode->next=NULL;
return newnode;
}
用于合并两个链表时使用
合并链表
合并两个有序链表是非常经典的链表算法，这里我传的参数并不是链表，但是也是用到了合并链表的思想
void merge(ll* ind1,ll*exp1,ll*ind2,ll*exp2){
NODE* tail = head;
int i1 =0;
int i2=0;//i1和i2分别记录两个多项式的当前最后一位
while(i1!=n&&i2!=m){
if(exp1[i1]>exp2[i2]){
NODE* new = createNode(ind2[i2],exp2[i2]);
tail->next = new;
i2++;
}else if(exp1[i1]<exp2[i2]){
NODE* new = createNode(ind1[i1],exp1[i1]);
tail->next = new;
i1++;
}else{
NODE* new = createNode(ind1[i1]+ind2[i2],exp1[i1]);
tail->next = new;
i1++;
i2++;
}
tail=tail->next;
ret++;
}
while(i1!=n){
NODE* new = createNode(ind1[i1],exp1[i1]);
tail->next = new;
i1++;ret++;
tail=tail->next;
}
while(i2!=m){
NODE* new = createNode(ind2[i2],exp2[i2]);
tail->next = new;
i2++;ret++;
tail=tail->next;
}
}
完整代码
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
#include<time.h>
#include<limits.h>
typedef long long ll;
#define MAX_N 100005
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
typedef struct node{//存放系数和指数
ll ind;
ll exp;
struct node* next;
}NODE;
NODE* head;
int n,m;
ll ret;//记录系数非零的节点数目
NODE* createNode(ll i,ll e){
NODE* newnode = (NODE*)malloc(sizeof(NODE));
newnode->ind=i;
newnode->exp=e;
newnode->next=NULL;
return newnode;
}
void merge(ll* ind1,ll*exp1,ll*ind2,ll*exp2){
NODE* tail = head;
int i1 =0;
int i2=0;//i1和i2分别记录两个多项式的当前最后一位
while(i1!=n&&i2!=m){
if(exp1[i1]>exp2[i2]){
NODE* new = createNode(ind2[i2],exp2[i2]);
tail->next = new;
i2++;
}else if(exp1[i1]<exp2[i2]){
NODE* new = createNode(ind1[i1],exp1[i1]);
tail->next = new;
i1++;
}else{
NODE* new = createNode(ind1[i1]+ind2[i2],exp1[i1]);
tail->next = new;
i1++;
i2++;
}
tail=tail->next;
ret++;
}
while(i1!=n){
NODE* new = createNode(ind1[i1],exp1[i1]);
tail->next = new;
i1++;ret++;
tail=tail->next;
}
while(i2!=m){
NODE* new = createNode(ind2[i2],exp2[i2]);
tail->next = new;
i2++;ret++;
tail=tail->next;
}
}
int main(){
//初始化链表头结点,作为哑结点
head =(NODE*)malloc(sizeof(NODE));
head->ind=head->exp=-1;
head->next=NULL;
int t;
scanf("%d",&t);
while(t--){
ret=0;
scanf("%d",&n);
ll arr1_ind[n];//存放第一个多项式的系数
for(int i=0;i<n;i++){
scanf("%lld",&arr1_ind[i]);
}
ll arr1_exp[n];//存放第一个多项式的指数
for(int i=0;i<n;i++){
scanf("%lld",&arr1_exp[i]);
}
scanf("%d",&m);
ll arr2_ind[m];//存放第二个多项式的系数
for(int i=0;i<m;i++){
scanf("%lld",&arr2_ind[i]);
}
ll arr2_exp[m];//存放第二个多项式的指数
for(int i=0;i<m;i++){
scanf("%lld",&arr2_exp[i]);
}
//合并两个多项式
merge(arr1_ind,arr1_exp,arr2_ind,arr2_exp);
//输出最后合并的结果
printf("%lld\n",ret);
NODE* cur = head->next;
while(cur!=NULL){
printf("%lld ",cur->ind);
cur = cur->next;
}
printf("\n");
cur = head->next;
while(cur!=NULL){
printf("%lld ",cur->exp);
cur = cur->next;
}
printf("\n");
}
return 0;
}
多项式乘法
题目描述
输入输出
样例
代码段
计算两多项式结果
ll cal(ll base1,ll base2,ll* a,ll* b){
ll ret1 = 0;
ll x=1;
for(int i=0;i<=n;i++){
ret1=(ret1%MOD+x*a[i]%MOD)%MOD;
x=(x*base1)%MOD;
}
ll ret2 = 0;
x=1;
for(int i=0;i<=m;i++){
ret2=(ret2%MOD+x*b[i]%MOD)%MOD;
x=(x*base2)%MOD;
}
return (ret1*ret2)%MOD;
}
注意取模的规则
输入
cin>>n;
ll a[n+1];//注意要多开辟一个空间
for(int i=0;i<=n;i++){
cin>>a[i];
}
cin>>m;
ll b[m+1];
for(int i=0;i<=m;i++){
cin>>b[i];
}
两个系数数组都要记得多开辟一个空间，因为n和m代表最高次数，1-n次再加上一个0次，一共需要n+1个空间
完整代码
#include <iostream>
using namespace std;
#define MOD 10007
typedef long long ll;
int n,m,q;
ll cal(ll base1,ll base2,ll* a,ll* b){
ll ret1 = 0;
ll x=1;
for(int i=0;i<=n;i++){
ret1=(ret1%MOD+x*a[i]%MOD)%MOD;
x=(x*base1)%MOD;
}
ll ret2 = 0;
x=1;
for(int i=0;i<=m;i++){
ret2=(ret2%MOD+x*b[i]%MOD)%MOD;
x=(x*base2)%MOD;
}
return (ret1*ret2)%MOD;
}
int main(){
cin>>n;
ll a[n+1];
for(int i=0;i<=n;i++){
cin>>a[i];
}
cin>>m;
ll b[m+1];
for(int i=0;i<=m;i++){
cin>>b[i];
}
cin>>q;
for(int i=0;i<q;i++){
ll base1,base2;
cin>>base1>>base2;
cout<<cal(base1,base2,a,b)<<endl;
}
}
