만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

조화 함수

시간 제한1초메모리 제한1024 MB

요약
차수가 4 이하인 정수 계수 다항식 f와 g가 주어질 때, f를 조화 관계인 다항식으로 반복해서 바꿔 g에 도달할 수 있는지 판단합니다.
난이도

보통10점 중 7점

유형
수학, 구현
정답자
아직 제출이 없습니다

문제

실수 전체를 정의역으로 갖고 모든 계수가 실수인 다항함수 p(x)p(x)와 q(x)q(x)에 대해, p′(q(x))=q′(p(x))p'(q(x))=q'(p(x))이면 두 함수가 조화를 이룬다고 한다. 이 조건을 만족하지 않으면 두 함수는 조화를 이루지 않는다. 다항함수 u(x)u(x)에 대하여 u′(x)u'(x)는 u(x)u(x)의 도함수이다.

실수 전체를 정의역으로 갖는 다항함수 f(x)=anxn+an−1xn−1+⋯+a0f(x)=a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0와 g(x)=bmxm+bm−1xm−1+⋯+b0g(x)=b_m x^m + b_{m-1} x^{m-1} + \cdots + b_0가 주어진다. f(x)f(x)와 g(x)g(x)의 모든 계수는 정수이다.

한 번의 시행에서는 f(x)f(x)와 조화를 이루고 모든 계수가 실수인 다항함수 h(x)h(x)를 선택하여, f(x)f(x)를 h(x)h(x)로 바꿀 수 있다.

유한 번의 시행으로 f(x)=g(x)f(x)=g(x)가 되게 할 수 있는지 판별하라.

입력

첫 번째 줄에 테스트 케이스의 개수 TT가 주어진다. 이후 TT개의 테스트 케이스가 하나씩 주어진다.

각 테스트 케이스의 첫 번째 줄에는 f(x)f(x)와 g(x)g(x)의 차수를 나타내는 두 정수 nn과 mm이 공백으로 구분되어 주어진다. 입력의 편의를 위해 모든 상수함수의 차수는 00으로 간주한다.

두 번째 줄에는 f(x)f(x)의 각 항의 계수 an,an−1,⋯ ,a0a_n, a_{n-1}, \cdots, a_0 즉 n+1n+1개의 정수가 공백으로 구분되어 주어진다.

세 번째 줄에는 g(x)g(x)의 각 항의 계수 bm,bm−1,⋯ ,b0b_m, b_{m-1}, \cdots, b_0 즉 m+1m+1개의 정수가 공백으로 구분되어 주어진다.

출력

총 TT개의 줄에 각 테스트 케이스의 정답을 출력한다. 유한 번의 시행으로 f(x)=g(x)f(x)=g(x)가 되게 할 수 있으면 YES, 없으면 NO를 출력한다.

제한

  • 1≤T≤1041 \le T \le 10^{4}
  • 0≤n,m≤40 \le n, m \le 4
  • −106≤ai,bi≤106-10^{6} \le a_i, b_i \le 10^{6}
  • n≠0n \neq 0이면 an≠0a_n \neq 0이다.
  • m≠0m \neq 0이면 bm≠0b_m \neq 0이다.

예제2

  1. 예제 1

    입력
    2
    1 1
    -10 2
    -10 5
    3 2
    1 2 2 5
    -1 5 3
    
    예상 출력
    YES
    NO
    
  2. 예제 2

    입력
    1
    3 3
    1 4 -11 3
    1 4 -11 3
    
    예상 출력
    YES