一元多项式乘法

Love The Way You Lie 2022-06-02 04:43 211阅读 0赞

# 2. 一元多项式乘法 #

[DESCRIPTION][] [SUBMIT][] [STATISTICS][] [1 DISCUSSION][]

**Time limit per test:** 2.0 seconds

**Memory limit:** 256 megabytes

计算两个一元多项式的乘积。

### Input ###

每行两个多项式，以一个空格分隔，多项式格式为 anxn\+…\+a1x\+a0。

每行长度不超过100，0<n<50。

### Output ###

每组数据一行，根据次数由高到低顺序输出两个多项式乘积的非零项系数，两个系数之间由一个空格分隔。

### Examples ###

input

x+1 x-1
    x^2-3x+1 x^3
    x+2 2

output

1 -1
    1 -3 1
    2 4

### Source ###

编程实践第1次考试

## 解题思路： ##

将多项式的系数提取出来，x的n次的系数存放在下标为n的数组中，记录下每个多项式的最高次数，处理完毕后直接用系数计算。

注意处理负数，而且系数不仅是一位数。

窝退役之后太长时间没写代码，手生的不行……

这段AC代码真是又臭又长，自己都不忍直视啊…好蓝瘦哇…QAQ

#include<bits/stdc++.h>
    using namespace std;
    #define INF 0xfffffff
    #define MAXN 55
    long long a[MAXN],b[MAXN],ans[3000];
    string s1,s2;
    int s1Max=0,s2Max=0;
    int char2int(char str)
    {
        if(str=='-') return -1;
        return int(str-'0');
    }
    void fun(string s,long long t[],int &Max)//将s表示的最高次数为Max的多项式的系数存入t数组
    {
        int len=s.length();
        int j,sig=1,d=0;
        bool flag=false;
        int cnt=0;
        for(j=len-1; j>=0; --j) //常数项
        {
            if(s[j]>='0'&&s[j]<='9')
            {
                ++cnt;
                flag=true;
                continue;
            }
            if(flag&&s[j]!='^')
            {
                if(s[j]=='-')
                {
                    for(int i=len-1; i>j; --i)
                    {
                        d+=(sig*char2int(s[i]));
                        sig*=10;
                    }
                    d*=(-1);
                    t[0]=d;
                    break;
                }
                else if(s[j]=='+')
                {
                    for(int i=len-1; i>j; --i)
                    {
                        d+=(sig*char2int(s[i]));
                        sig*=10;
                    }
                    t[0]=d;
                    break;
                }
                break;
            }
        }
        sig=1,d=0;
        if(cnt==len)//仅有常数项
        {
            for(int i=len-1; i>=0; --i)
            {
                d+=(sig*char2int(s[i]));
                sig*=10;
            }
            t[0]=d;
        }
        else if(cnt==len-1&&s[0]=='-')
        {
            for(int i=len-1; i>0; --i)
            {
                d+=(sig*char2int(s[i]));
                sig*=10;
            }
            t[0]=-1*d;
        }
        for(int i=0; i<len; ++i)
            if(s[i]=='x')
            {
                if(i==0&&s[i+1]!='^') t[1]=1,Max=max(Max,1);//首项为x
                else if(i==0&&s[i+1]=='^') //首项为x^n
                {
                    sig=1,d=0;
                    for(j=i+2; s[j]>='0'&&s[j]<='9'; ++j);
                    for(int k=j-1; k>=i+2; --k)
                    {
                        d+=(sig*char2int(s[k]));
                        sig*=10;
                    }
                    t[d]=1;
                    Max=max(Max,d);
                }
                else
                {
                    if(s[i+1]!='^') //mx
                    {
                        sig=1,d=0,flag=false;
                        for(j=i-1; s[j]>='0'&&s[j]<='9'; --j)
                        {
                            flag=true;
                            d+=(sig*char2int(s[j]));
                            sig*=10;
                        }
                        if(!flag) d=1;
                        if(s[j]=='-') d*=(-1);
                        t[1]=d;
                        Max=max(Max,1);
                    }
                    else //mx的n次方
                    {
                        /*mx*/
                        sig=1,d=0,flag=false;
                        for(j=i-1; s[j]>='0'&&s[j]<='9'; --j)
                        {
                            flag=true;
                            d+=(sig*char2int(s[j]));
                            sig*=10;
                        }
                        if(!flag) d=1;
                        if(s[j]=='-') d*=(-1);
                        /*mx^n*/
                        sig=1;
                        int dd=0;
                        for(j=i+2; s[j]>='0'&&s[j]<='9'; ++j);
                        for(int k=j-1; k>=i+2; --k)
                        {
                            dd+=(sig*char2int(s[k]));
                            sig*=10;
                        }
                        t[dd]=d;
                        Max=max(Max,dd);
                    }
                }
            }
    }
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("F:/cb/read.txt","r",stdin);
        //freopen("F:/cb/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        while(cin>>s1>>s2)
        {
            s1Max=0,s2Max=0;
            memset(a,0,sizeof(a));
            memset(b,0,sizeof(b));
            memset(ans,0,sizeof(ans));
            fun(s1,a,s1Max);
            fun(s2,b,s2Max);
            /*cout<<s1Max<<" "<<s1<<endl;
            for(int i=0; i<=s1Max; ++i)
                cout<<a[i]<<" ";
            cout<<endl;
            cout<<s2Max<<" "<<s2<<endl;
            for(int i=0; i<=s2Max; ++i)
                cout<<b[i]<<" ";
            cout<<endl;*/
            for(int i=0; i<=s1Max; ++i)
                for(int j=0; j<=s2Max; ++j)
                    ans[i+j]+=(a[i]*b[j]);
            for(int i=s1Max+s2Max; i>=0; --i)
                if(ans[i]!=0) cout<<ans[i]<<" ";
            cout<<endl;
        }
    }

[DESCRIPTION]: http://acm.ecnu.edu.cn/problem/2/
[SUBMIT]: http://acm.ecnu.edu.cn/problem/2/submit/
[STATISTICS]: http://acm.ecnu.edu.cn/problem/2/statistics/
[1 DISCUSSION]: http://acm.ecnu.edu.cn/problem/2/discussion/