問題一覧 > 教育的問題

No.2448 Linear Transformation and Area

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 3
作問者 : 👑 p-adic / テスター : tko919 tko919
お気に入りにしたユーザー ProblemId : 9664 / 自分の提出
問題文最終更新日: 2023-08-25 21:14:38
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

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