14604 - Big Orange Cat's Polynomial I   

Status  |  Limits Submit

Description

You are given definitions of multiple polynomials, such as F(x)=+2x^2 +3x +1 and G(x)=+2x +1 , along with several operations to perform on these polynomials, like F(2)+G(3), You need to compute the results of these operations.

This problem is a partial judge.
Please implement functions defined in the header file:

  • Polynomial(int deg, const int *coeffs) Constructor: Initializes polynomial with degree and coefficient array 
  • Polynomial(const Polynomial& other) Copy constructor: Creates a copy of another polynomial 
  • Polynomial operator+(const Polynomial& other) const Addition operator: Adds two polynomials 
  • Polynomial operator-(const Polynomial& other) const Subtraction operator: Subtracts one polynomial from another 
  • Polynomial operator*(const Polynomial& other) const Multiplication operator: Multiplies two polynomials
  • Polynomial& operator=(const Polynomial& other) Assignment operator: Assigns one polynomial to another
  • int evaluate(int x) const Evaluates polynomial at given value x, The result must be taken modulo 109+7.  If the result is negative, add 109+7 after taking the modulo to ensure the final answer is non-negative.
  • friend std::ostream& operator<<(std::ostream& os, const Polynomial& poly) Output stream operator: Prints polynomial to output stream

Input

The first line contains two positive integers n and m, where n is the number of polynomials, and m is the number of operations to perform

The next n lines describe the polynomials. Each line is in one of two formats:

  1. <symbol> = <polynomial>, which defines the mathematical expression for that polynomial (e.g., "F = 2x^2 + 3x + 1").
  2. <symbol1> = <symbol2>, which means the polynomial defined by <symbol1> is the same as the polynomial defined by <symbol2>.
The next m lines each contain an operation in the format <func1> <op> <func2> <x>, where:
  • <func1> and <func2> are the names of two polynomials.
  • <op> is an operator, which can be +, -, or *, indicating the operation to perform (addition, subtraction, or multiplication).
  • <x> is the value of x to substitute into the polynomials

Constraints

  • The degree of each polynomial is at most 100.
  • 1 <= n <= 26
  • 1 <= m <= 1000
  • All coefficients and values in the polynomials are less than or equal to 105
  • The symbol will only consist of a single uppercase letter.

Subtasks

  • testcase 1: The operation will only involve addition (+)
  • testcase 2: The operation will only involve subtraction (-)
  • testcase 3: The operation will only involve multiplication (*)
  • testcases 4 ~ 6: No additional restrictions

Output

For each operation, you need to output the result in the format <poly> = <ans>, where:
  • <poly> is the mathematical expression of the resulting polynomial after performing the operation on <func1> and <func2>.
  • <ans> is the value of the resulting polynomial evaluated at x = x.
  • If a polynomial has a coefficient of 0, represent it as +0.
  • The result <ans> must be taken modulo 109+7.  If the result is negative, add 109+7 after taking the modulo to ensure the final answer is non-negative.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14604.cpp

Partial Judge Header

14604.h

Tags




Discuss