No.3533 Difficult Counting Problem?
nauclhlt
あいすあうとProblem Statement
There is a $N\times N$ $2$-dimensional grid. The cell in the $i(1\leq i\leq N)$-th row from the top and the $j(1\leq j\leq N)$-th column from the left of this grid is called cell $(i, j)$.
A route that starts at cell $(1, 1)$ and reaches cell $(N, N)$ by repeating a move to an adjacent cell $0$ or more times, and that does not pass through the same cell $2$ or more times, is called a good route.
Given $N$, compute the total number of good routes. Since the answer can be very large, find the remainder when it is divided by $2$.
Solve for $T$ cases.
Formal definition of a good route
Let $I=\lbrace (i, j) \ |\ i, j\in \lbrace 1, 2, \cdots, N\rbrace \rbrace$ be the set of all cell coordinates.
Then a good route is a sequence $X=(X_1, X_2, \cdots, X_K)$ that satisfies all of the following conditions.
- $X_i\in I$ for $i=1, 2, \cdots, K$
- $X_1=(1, 1)$
- $X_K=(N, N)$
- $X_1, X_2, \cdots, X_K$ are pairwise distinct
- For every integer $i$ satisfying $1\leq i\leq K-1$, the cell represented by $X_i$ and the cell represented by $X_{i+1}$ are adjacent, sharing $1$ edge
- That is, taking $i_1, j_1, i_2, j_2$ such that $X_i=(i_1, j_1), X_{i+1}=(i_2, j_2)$, it holds that $|i_1-i_2|+|j_1-j_2|=1$
Also, $2$ routes $A, B$ are counted as different if and only if one of the following holds.
- $|A|\neq |B|$
- $|A|=|B|$ and there exists some $i\ (1\leq i\leq |A|)$ such that $A_i\neq B_i$
Here, $|A|, |B|$ denote the lengths of the sequences $A, B$, respectively.
What does "Solve for $T$ cases" mean?
In this problem, $1$ file contains multiple test cases.
A positive integer $T$ representing the number of test cases is given on the first line. Read it, and then solve the problem described above $T$ times.
The execution time is measured per file. That is, note that even if each of the $T$ test cases is solved within $2$ seconds, the result will be TLE if the total execution time over all $T$ cases exceeds $2$ seconds.
Input
$T$ $N_1$ $N_2$ $\vdots$ $N_T$
$N_i$ represents the value of $N$ in the $i$-th test case.
- $1\leq T\leq 1000$
- $1\leq N\leq 10^9$
- All input values are integers
Output
Output the remainder when the total number of good routes is divided by $2$, on $1$ line.
Print a newline at the end.
Sample
Sample 1
Input
3 1 2 4
Output
1 0 0
- For test case number $1$: when $N=1$, only cell $(1, 1)$ exists and no move is possible, so there is $1$ good route, which does not move from cell $(1, 1)$. Therefore, the answer is $1$.
- For test case number $2$: when $N=2$, there are exactly $2$ good routes, so the answer is $0$.
- For test case number $3$: when $N=4$, there are exactly $184$ good routes, so the answer is $0$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。