个人思路仅供参考,如有不足欢迎交流。

问题描述

小明现在在学习多项式的展开:就是把一个形如

(x+a1) (x+a2) … (x+an)

展开成如下形式:

x^n + b1x^(n-1) + b2x^(n-2) + … + bn-1^x + bn

比如 (x+1)(x+2)=x^2 + 3x + 2

(x+1)^3 = x^3 +3x^2 +3x + 1

小明做了很多练习,但是不知道对错,现在请求你的帮助,判断小明的展开式是否正确。

输入格式

有多组测试数据。

每组测试数据有三行,第一行是一个正整数N,表示多项式最高指数。N=0表示输入结束,并且不需要处理。

第二行N个整数ai,用空格隔开,i=1,…,N(-100≤ai≤100)

第三行N个整数bi,用空格隔开,i=1,…,N,(-10^9≤bi≤10^9)

40%的测试数据 1 ≤ N < 5;

30%的测试数据 5 ≤ N < 10;

20%的测试数据10 ≤ N < 15;

10%的测试数据 15 ≤N≤ 20;

输出格式

  对于每组测试数据,输出一行一个字符‘Y’如果展开式是正确的,输出‘N’如果展开式错误。

样例输入

2
1 2
3 2
3
1 1 1
3 3 1
4
0 0 0 1
0 0 0 1
0

样例输出

Y
Y
N

思路和做法

  • 题目中已经说明了输入的ai、bi的含义,可以直接模拟多项式的乘法;
  • 提交代码如下(10/10分,C++):
//56.相等的多项式
#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main()
{
    int n;                      //多项式最高次数
    vector<int> ai;             //多项式a
    map<int, int> bi, aiExband; //多项式b、多项式a的展开
    //map<次数,对应项的系数>
    while (cin >> n && n != 0)
    {
        int temp;
        ai.clear(), bi.clear(), aiExband.clear();
        for (int i = 0; i < n; i++)
        {
            cin >> temp;
            ai.push_back(temp);
        }
        bi[n] = 1;
        for (int i = n - 1; i >= 0; i--)
        {
            cin >> temp;
            bi[i] = temp;
        }

        //多项式a的展开
        aiExband[0] = ai[0], aiExband[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            for (int j = i; j >= 0; j--)
            {
                if (j != i && j != 0)
                {
                    aiExband[j] = aiExband[j] * ai[i - 1] + aiExband[j - 1];
                }
                else if (j == i) //当前最高次数项的系数一定是1
                {
                    aiExband[j] = 1;
                }
                else //j=0
                {
                    aiExband[j] *= ai[i - 1];
                }
            }
        }
        if (bi == aiExband)
        {
            cout << 'Y' << endl;
        }
        else
        {
            cout << 'N' << endl;
        }
    }
    return 0;
}