問題一覧 > 教育的問題

No.2444 Linear Transformation and Volume

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 29
作問者 : 👑 p-adic / テスター : 👑 Kazun
お気に入りにしたユーザー ProblemId : 8942 / 自分の提出
問題文最終更新日: 2023-09-05 23:33:27
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 402 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。