| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Busy Beaver has a polynomial equation that he doesn't know how to solve, and he needs your help!
For a bivariate polynomial $P(x,y)=\sum\limits_{i,j \ge 0}a_{i,j}x^iy^j,ドル define its degree $\deg P = \max\limits_{a_{i,j}\neq 0}(i+j)$. For example, $\deg (x + y + xy) = 2$. Furthermore, we take the degree of the zero polynomial $\deg 0$ to be $-1$.
Given a bivariate polynomial $P(x,y)$ with integer coefficients and an integer $d \geq -1,ドル determine whether there exists a bivariate polynomial $S(x, y)$ and non-constant univariate polynomials $Q, R$ such that
If a solution exists, output any valid $Q, R$. Note that you do not need to output $S$.
1i.e. when expanded, the two sides of the equation have equal coefficients modulo $p$.
Each test contains multiple test cases. The first line contains the number of test cases $T$ (1ドル \leq T \leq 100$). The description of the test cases follows.
The first line of each test case contains two integers $n, d$ (1ドル \leq n \leq 2.5 \cdot 10^3,ドル $-1 \leq d < n$) --- the value of $\deg P$ and the upper bound on $\deg S,ドル respectively.
The $i$-th of the next $n + 1$ lines contains $n + 2 - i$ integers $a_{i-1, 0}, \dots, a_{i-1, n+1-i}$ (0ドル \leq a_{i,j} < 10^9 + 7$) --- the coefficients of $P$ so that $P(x,y)=\sum\limits_{i,j \ge 0, i+j \leq n}a_{i,j}x^iy^j$. It is guaranteed that $P$ has degree $n,ドル i.e. at least one of $a_{0,n}, a_{1,n-1}, \dots, a_{n,0}$ is nonzero.
It is guaranteed that the sum of $n$ across all test cases is no more than 2ドル.5 \cdot 10^3$.
The first line of output for each test case should contain the string "YES" (without quotes) if a solution exists, and "NO" (without quotes) otherwise.
If you claim that a solution exists, continue outputting the solution as follows:
The second line of output for each test case should contain three integers $q, r$ (1ドル \leq q, r \leq 5 \cdot 10^3$) --- the degrees of the polynomials $Q, R$ respectively.
The third line of output for each test case should contain $q + 1$ integers $b_0, \dots, b_q$ (0ドル \leq b_i < 10^9 + 7,ドル $b_q \neq 0$) --- the coefficients of $Q(t) = \sum_{i=0}^q b_i t^i$.
The fourth line of output for each test case should contain $r + 1$ integers $c_0, \dots, c_r$ (0ドル \leq c_i < 10^9 + 7,ドル $c_r \neq 0$) --- the coefficients of $R(t) = \sum_{i=0}^r c_i t^i$.
Note that you do not need to output $S$ --- the judge will determine if a suitable choice of $S$ exists for your claimed $Q, R$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | The sum of $n$ across all test cases is no more than 10ドル,ドル and $d = -1,ドル i.e. we constrain that $S$ is the zero polynomial. |
| 2 | 5 | $d = n - 1$. |
| 3 | 30 | $d = -1,ドル i.e. we constrain that $S$ is the zero polynomial. |
| 4 | 30 | The sum of $n$ across all test cases is no more than 500ドル$. |
| 5 | 30 | No additional constraints. |
5 2 -1 40 9 13 9 0 13 4 2 1000000000 1 1000000001 2 1 1 1000000000 2 0 999999999 2 1 2 0 1 4 2 1000000000 1 1000000001 2 1 1 1000000000 1 0 999999999 1 1 2 0 1 4 2 120 50 61 235 169 50 81 119 0 61 119 169 235 0 169 9 5 17 18 19 20 21 22 2 6 0 1 16 8 8 4 8 0 2 0 0 15 8 0 4 0 0 0 0 14 4 4 2 4 0 1 13 8 0 4 0 0 12 0 0 0 0 2 2 0 1 6 0 0 0 0 1
YES 2 4 20 9 13 400 360 601 234 169 NO YES 2 6 1 1 1 2 4 7 7 6 3 1 NO YES 3 12 0 2 0 1 0 0 0 16 16 24 32 12 24 2 8 0 1
In the first test case, the given polynomial is $$P(x, y) = 13x^2 + 13y^2 + 9x + 9y + 40.$$ We can take $S = 0,ドル $Q(t) = 13t^2 + 9t + 20,ドル $R(t) = (13t^2 + 9t + 20)^2,ドル which gives a valid solution.
In the second test case, it can be shown that no solution exists.
University > MIT > M(IT)^2 > M(IT)^2 Spring 2025 Invitational > Finals 5번