No.2444 Linear Transformation and Volume
Problem Statement
The input gives $2$ positive integers $N$ and $B$, and a square matrix $A$ of order $3$ with non-negative integer coefficients.
Let $X$ be the subset $\{x \in \mathbb{R}^3 \mid A^N x \in [0,1]^3\}$ of $\mathbb{R}^3$, and let $V$ be the volume of $X$.
Here, we extend the definition of the reciprocal of positive real numbers: we define $0^{-1}$ as $\infty$, and $\infty^{-1}$ as $0$. We also define the remainder of $\infty$ divided by $B$ as $\infty$.
It can then be proved that $V^{-1}$ is a non-negative integer or $\infty$, so find its remainder when divided by $B$.
Below is an explanation for those who are not familiar with set notation or the rigorous definition of volume and so on. (Click to open)
$\mathbb{R}^3$ denotes the set of all $3$-dimensional real vectors, and $[0,1]^3$ denotes the set of all $3$-dimensional real vectors each of whose components is between $0$ and $1$, inclusive.
The definition of $X$, namely $\{x \in \mathbb{R}^3 \mid A^N x \in [0,1]^3\}$, denotes the set of all elements $x$ of $\mathbb{R}^3$ satisfying $A^N x \in [0,1]^3$.
Unless otherwise stated, the volume of a subset of $\mathbb{R}^3$ is formulated using the Lebesgue measure. Specifically, the volume of a subset $U$ of $\mathbb{R}^3$ is defined only when $U$ is Lebesgue measurable, and its value is determined as the value obtained by substituting $U$ into the Lebesgue measure of $\mathbb{R}^3$ (or, equivalently, the value of the Lebesgue integral of the constant function $1$ over $U$).
For example, the volume of a rectangular cuboid whose $3$ edges extending from $1$ vertex have lengths $a,b,c$, respectively, is $abc$; in this way, the formulation is consistent with the volume formulas learned up through high school.
Since the subset $X$ considered here is known to be Lebesgue measurable, its volume $V$ is determined as a non-negative real number or $\infty$, and when it is a positive real number (that is, neither $0$ nor $\infty$), it can be proved that $V^{-1}$ turns out to be a positive integer.
Note that the $\infty$ appearing in integrals and the like is formulated by arbitrarily fixing one term known not to belong to $\mathbb{R}$ and calling it $\infty$. Since the arguments are made so that it does not matter which term is called $\infty$, how exactly it is chosen is often left unstated; but if a concrete formulation is needed, one can, for example, define $\infty$ to be $\mathbb{R}$ itself, and then it follows that $\infty$ does not belong to $\mathbb{R}$, that is, it can be distinguished from real numbers. Then, if necessary, an order and operations extending those of $\mathbb{R}$ are often defined as appropriate on $\mathbb{R} \cup \{\infty\}$ and used.
Input
For each positive integer $i,j$ at most $3$, let $A_{i,j}$ be the $(i,j)$ entry of $A$. Then, the input is given from standard input in the following format:
$N$ $B$
$A_{1,1}$ $A_{1,2}$ $A_{1,3}$
$A_{2,1}$ $A_{2,2}$ $A_{2,3}$
$A_{3,1}$ $A_{3,2}$ $A_{3,3}$
- Line $1$ contains $N, B$, separated by a single-byte space.
- For each positive integer $i$ at most $3$, line $1+i$ contains $A_{i,1}, A_{i,2}, A_{i,3}$, separated by single-byte spaces.
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 10^6$
- $B$ is an integer satisfying $1 \leq B \leq 10^6$
- For any positive integers $i,j$ at most $3$, $A_{i,j}$ is an integer satisfying $0 \leq A_{i,j} \leq 10^6$
Output
Print the remainder of $V^{-1}$ divided by $B$ on $1$ line.
However, when printing $\infty$, print infty.
Print a newline at the end.
Sample
Sample 1
Input
1 2 1 0 0 0 1 0 0 0 1
Output
1
$\displaystyle A^N = \left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right)^1 = \left( \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right) $
Thus, $X$ is a cube in which $1$ edge has length $1$, and its volume $V$ is $1$. The remainder of $1^{-1} = 1$ divided by $B = 2$ is $1$.
Sample 2
Input
1 2 1 1 1 1 2 1 1 1 2
Output
1
$\displaystyle A^N = \left( \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{array} \right)^1 = \left( \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{array} \right) $
Thus, $X$ is a parallelepiped, and its volume $V$ is $1$. The remainder of $1^{-1} = 1$ divided by $B = 2$ is $1$.
Sample 3
Input
2 3 1 1 1 1 1 1 1 1 1
Output
0
$\displaystyle A^N = \left( \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array} \right)^2 = \left( \begin{array}{ccc} 3 & 3 & 3 \\ 3 & 3 & 3 \\ 3 & 3 & 3 \end{array} \right) $
Thus, $X$ is a solid obtained as the trace of a plane translated by a positive finite width, and its volume $V$ is $\infty$.
Since $\infty^{-1}$ is defined as $0$, the remainder of $\infty^{-1}$ divided by $B$ is $0$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun