No.2448 Linear Transformation and Area
Problem Statement
First, we introduce some notation. For a positive integer $N$ and a square matrix $A$ of order $2$ with integer entries, let the subset of $\mathbb{R}^2$
$\displaystyle \left\{ x \in \mathbb{R}^2 \middle| \exists y \in [0,1]^2, x = \sum_{i=1}^{N} A^i y \right\} $
be denoted by $X_{N,A}$, and let the area of $X_{N,A}$ be denoted by $S_{N,A}$. It can be proved that $S_{N,A}$ is a non-negative integer.
Below is an explanation for those who are not familiar with set notation or the rigorous definition of area. (Click to open)
$\mathbb{R}^2$ denotes the set of all $2$-dimensional real vectors, and $[0,1]^2$ denotes the set of all $2$-dimensional real vectors each of whose components is at least $0$ and at most $1$.
The definition of $X_A$,
$\displaystyle \left\{ x \in \mathbb{R}^2 \middle| \exists y \in [0,1]^2, x = \sum_{i=1}^{N} A^i y \right\} $
denotes the set of all elements $x$ of $\mathbb{R}^2$ that can be expressed, using some $y \in [0,1]^2$, as
$\displaystyle x = \sum_{i=1}^{N} A^i y $
.
Unless otherwise stated, the area of a subset of $\mathbb{R}^2$ is formulated using the Lebesgue measure. Specifically, the area of a subset $U$ of $\mathbb{R}^2$ is defined only when $U$ is Lebesgue measurable, and its value is defined as the value obtained by substituting $U$ into the Lebesgue measure of $\mathbb{R}^2$ (or, equivalently, the value of the Lebesgue integral of the constant function $1$ over $U$).
This formulation is consistent with the area formulas taught up through high school; for example, the area of a rectangle whose $2$ sides extending from $1$ vertex have lengths $a,b$ respectively is $ab$.
Since the subset $X_{N,A}$ considered here is known to be Lebesgue measurable, its area $S_{N,A}$ is determined as a non-negative real number or $\infty$, and in this problem it can be proved to be, in particular, a non-negative integer.
Now consider the following problem:
You are given as input $2$ positive integers $N, B$ and a square matrix $A$ of order $2$ with integer entries.
Find the remainder when $S_{N,A}$ is divided by $B$.
A positive integer $T$ is given at the beginning of the input. Answer $T$ problems.
Input
The input is given from standard input in $1+3T$ lines in the following format:
- Line $1$ contains $T$.
- For each positive integer $t$ not exceeding $T$, lines $3t - 1$ through $3t + 1$ contain the input for the $t$-th problem.
$T$ ($1$ 番目の問題に対する入力) $\vdots$ ($T$ 番目の問題に対する入力)
Here, for each positive integer $t$ not exceeding $T$, denote the input for the $t$-th problem by $N_t, B_t, A_t$, and denote the $(i,j)$ entry of $A_t$, for each positive integer not exceeding $2$, by $A_{t,i,j}$. Then the input for the $t$-th problem is given from standard input in $3$ lines (lines $3t - 1$ through $3t + 1$ of the whole input) in the following format:
- Line $1$ contains $N_t, B_t$, separated by a space.
- Line $2$ contains $A_{t,1,1}, A_{t,1,2}$, separated by a space.
- Line $3$ contains $A_{t,2,1}, A_{t,2,2}$, separated by a space.
$N_t$ $B_t$
$A_{t,1,1}$ $A_{t,1,2}$
$A_{t,2,1}$ $A_{t,2,2}$
Constraints
The input satisfies the following constraints:
- $T$ is an integer satisfying $1 \leq T \leq 10^3$.
- For each positive integer $t$ not exceeding $T$,
- $N_t$ is an integer satisfying $1 \leq N_t \leq 10^{18}$.
- $B_t$ is an integer satisfying $1 \leq B_t \leq 10^9$.
- For each pair of positive integers $i,j$ not exceeding $2$, $A_{t,i,j}$ is an integer satisfying $-10^9 \leq A_{t,i,j} \leq 10^9$.
Output
For each positive integer $t$ not exceeding $T$, print on line $t$ the remainder when $S_{N_t,A_t}$ is divided by $B_t$.
Print a newline at the end.
Sample
Sample 1
Input
1 1 1 1 0 0 1
Output
0
$\displaystyle \sum_{i=1}^{N_1} A_1^i = \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right)^1 = \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right) $
Thus, $X_{N_1,A_1}$ is a square, $1$ side of which has length $1$, and its area $S_{N_1,A_1}$ is $1$. The remainder when $1$ is divided by $B_1 = 1$ is $0$.
Sample 2
Input
1 1 2 1 1 1 1
Output
0
$\displaystyle \sum_{i=1}^{N_1} A_1^i = \left( \begin{array}{cc} 1 & 1 \\ 1 & 1 \\ \end{array} \right)^1 = \left( \begin{array}{cc} 1 & 1 \\ 1 & 1 \\ \end{array} \right) $
Thus, $X_{N_1,A_1}$ is the line segment connecting the origin $(0,0)$ and the point $(2,2)$, and its area $S_{N_1,A_1}$ is $0$. The remainder when $0$ is divided by $B = 2$ is $0$.
Sample 3
Input
2 2 3 1 0 0 2 1 4 1 0 0 -3
Output
0 3
First, consider problem $1$.
$\displaystyle \sum_{i=1}^{N_1} A_1^i = \left( \begin{array}{cc} 1 & 0 \\ 0 & 2 \end{array} \right)^1 + \left( \begin{array}{cc} 1 & 0 \\ 0 & 2 \end{array} \right)^2 = \left( \begin{array}{cc} 2 & 0 \\ 0 & 6 \end{array} \right) $
Thus, $X_{N_1,A_1}$ is a rectangle whose $2$ sides have lengths $2,6$ respectively, and its area $S_{N_1,A_1}$ is $12$. The remainder when $12$ is divided by $B = 3$ is $0$.
Next, consider problem $2$.
$\displaystyle \sum_{i=1}^{N_2} A_2^i = \left( \begin{array}{cc} 1 & 0 \\ 0 & -3 \end{array} \right)^1 = \left( \begin{array}{cc} 1 & 0 \\ 0 & -3 \end{array} \right) $
Thus, $X_{N_2,A_2}$ is a rectangle whose $2$ sides have lengths $1,3$ respectively, and its area $S_{N_2,A_2}$ is $3$. The remainder when $3$ is divided by $B = 4$ is $3$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
tko919