# 我會因式分解
https://neoj.sprout.tw/problem/514/
### 題目敘述
因式分解國中都有教，但很多人還是不會，所以我們要讓電腦幫我們做。

現在給你 $N$ 個候選的 $D$ 次因式，接下來有 $Q$ 個 $2D$ 次多項式，請輸出它由哪兩個因式組成。

### 輸入
第一行有三個整數 $D,\ N,\ Q$ 分別代表因式的次數、因式的個數、多項式的個數。
接下來有 $N$ 行，每行有 $D+1$ 個整數 $c_0,\ c_1,\ ...\ c_i\ ...\ c_D$ ，代表因式的 $i$ 次係數（升冪排序）。
接下來有 $Q$ 行，每行有 $2D+1$ 個整數 $e_0,\ e_1,\ ...\ e_i\ ...\ e_{2D}$ ，代表多項式的 $i$ 次係數（升冪排序）。

### 輸出
請輸出 $Q$ 行，每行形如 $(c_0 + c_1x^1, ... c_Dx^D)(c'_0 + c_1x^1, ... c_Dx^D)$，且左項不比右項晚被輸入。

輸入限制
$1 \le D < 10$
$1 \le N < 30$
$1 \le Q < 10$
$|c| \le 10000$
保證 $Q$ 個多項式 $q$ 皆可在前 $N$ 個因式中找到 $n_1,\ n_2$，使得 $q(x) = n_1(x) * n_2(x)$。

### 範例輸入輸出
#### 範例輸入 I

1 2 2
1 1
2 1
1 2 1
2 3 1

#### 範例輸出 I

(1 + 1x^1)(1 + 1x^1)
(1 + 1x^1)(2 + 1x^1)

#### 範例輸入 II

3 3 1
9 8 2 3
1 0 0 -1
-1 0 0 1
-1 0 0 2 0 0 -1

#### 範例輸出 II

(1 + 0x^1 + 0x^2 + -1x^3)(-1 + 0x^1 + 0x^2 + 1x^3)

### Hint
你可以直接使用下面的程式碼，並填入有寫 TODO 的部份。

#include <iostream>
#include <cstring>
#define MAXN 30
#define MAXD 10

// 多項式乘法，res = a*b，並回傳 res 陣列。
int *convolution(int a[], int b[], int res[], int D){
	memset(res, 0, (2 * D + 1) * sizeof(int));
  // TODO
	return res;
}
// 讀一個 D 次多項式到陣列 p
void readPoly(int p[], int D){
  // TODO
}
// 印出形如 (c_0 + c_1x^1 ... c_Dx^D) 的多項式 p
void printPoly(int p[], int D){
  // TODO
}

int main(){
  int D, N, Q;
  int factor[MAXN][MAXD + 1];
  int input[MAXD * 2 + 1];
  int result[MAXD * 2 + 1];
  std::cin >> D >> N >> Q;
  for(int i = 0; i < N; i++)
    readPoly(factor[i], D);
  while(Q--){
    readPoly(input, D * 2);
    for(int i = 0; i < N; i++)
      for(int j = i; j < N; j++)
        if(memcmp(convolution(factor[i], factor[j], result, D), input, (2 * D + 1) * sizeof(int)) == 0)
        {
          printPoly(factor[i], D);
          printPoly(factor[j], D);
          std::cout << std::endl;
        }
  }
}

# Code

#include <iostream>
#include <cstring>
#define MAXN 30
#define MAXD 10

using namespace std;

int *convolution(int a[], int b[], int res[], int D){
  memset(res, 0, (2 * D + 1) * sizeof(int));
  for (int i = 0 ; i <= D ; i++)
    for (int j = 0 ; j <= D ; j++)
      res[i + j] += a[i] * b[j];
  return res;
}

void readPoly(int p[], int D){
  for (int i = 0 ; i <= D ; i++)
    cin >> p[i];
}

void printPoly(int p[], int D){
  cout << "(";
  for (int i = 0 ; i <= D ; i++){
    cout << p[i];

    if (i != 0)
        cout << "x^" << i;
    if (i != D)
        cout << " + ";
  }
  cout << ")";
}

int main(){
  int D, N, Q;
  int factor[MAXN][MAXD + 1];
  int input[MAXD * 2 + 1];
  int result[MAXD * 2 + 1];
  cin >> D >> N >> Q;
  for (int i = 0; i < N; i++)
    readPoly(factor[i], D);
  while (Q--)
  {
    readPoly(input, D * 2);
    for (int i = 0 ; i < N; i++)
      for (int j = i; j < N; j++)
        if (memcmp(convolution(factor[i], factor[j], result, D),
            input, (2 * D + 1) * sizeof(int)) == 0)
        {
          printPoly(factor[i], D);
          printPoly(factor[j], D);
          cout << "\n";
        }
  }
}