No.2448 一次変換と面積
タグ : / 解いたユーザー数 5
作問者 : 👑
p-adic
/ テスター :
tko919
tko919
問題文
まずは記法の導入です。正整数 $N$ と整数係数 $2$ 次正方行列 $A$ に対し、$\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\} $
を $X_{N,A}$ と置き、$X_{N,A}$ の面積を $S_{N,A}$ と置きます。$S_{N,A}$ は非負整数であることが証明可能です。
以下、集合の記法や面積の厳密な定義を知らない人向けの説明をします。（クリックで開く）
$\mathbb{R}^2$ は $2$ 次元実数ベクトル全体の集合を表し、$[0,1]^2$ は $2$ 次元実数ベクトルであって各成分が $0$ 以上 $1$ 以下であるもの全体の集合を表します。
$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\} $
は、ある $y \in [0,1]^2$ を用いて
$\displaystyle x = \sum_{i=1}^{N} A^i y $
と表せるような $\mathbb{R}^2$ の要素 $x$ 全体の集合を表します。
$\mathbb{R}^2$ の部分集合の面積は断りのない限りルベーグ測度を用いて定式化されます。具体的には、$\mathbb{R}^2$ の部分集合 $U$ がルベーグ可則である時にのみ $U$ の面積が定義され、その値は $U$ を $\mathbb{R}^2$ のルベーグ測度に代入した値（または等価な言い換えとして、定数関数 $1$ を $U$ 上でルベーグ積分した値）として定められます。
例えば $1$ 頂点から伸びる $2$ 辺の長さがそれぞれ $a,b$ である長方形の面積は $ab$ となるなど、この定式化は高校までで習う面積の公式と整合的です。
今回扱う部分集合 $X_{N,A}$ はルベーグ可測であることが知られているためその面積 $S_{N,A}$ は非負実数または $\infty$ として定まり、今回は特に非負整数となることが証明可能です。
ここで次のような問題を考えます：
入力に $2$ 個の正整数 $N, B$ と整数係数 $2$ 次正方行列 $A$ が与えられます。
$S_{N,A}$ を $B$ で割った余りを求めてください。
入力の最初に正整数 $T$ が与えられます。$T$ 個の問題に答えてください。
入力
この時、入力は以下の形式で標準入力から $1+3T$ 行で与えられます：
- $1$ 行目に $T$ が与えられます。
- $T$ 以下の各正整数 $t$ に対し、$3t - 1$ 行目から $3t + 1$ 行目までに $t$ 番目の問題に対する入力が与えられます。
$T$ ($1$ 番目の問題に対する入力) $\vdots$ ($T$ 番目の問題に対する入力)
ここで $T$ 以下の各正整数 $t$ に対し、$t$ 番目の問題に対する入力を $N_t, B_t, A_t$ と表し、$2$ 以下の各正整数に対する $A_t$ の $(i,j)$ 成分を $A_{t,i,j}$ と表すと、$t$ 番目の問題に対する入力は以下の形式で標準入力から $3$ 行（入力全体の $3t - 1$ 行目から $3t + 1$ 行目まで）で与えられます：
- $1$ 行目に $N_t, B_t$ が半角空白区切りで与えられます。
- $2$ 行目に $A_{t,1,1}, A_{t,1,2}$ が半角空白区切りで与えられます。
- $3$ 行目に $A_{t,2,1}, A_{t,2,2}$ が半角空白区切りで与えられます。
$N_t$ $B_t$
$A_{t,1,1}$ $A_{t,1,2}$
$A_{t,2,1}$ $A_{t,2,2}$
制約
入力は以下の制約を満たします：
- $T$ は $1 \leq T \leq 10^3$ を満たす整数
- $T$ 以下の各正整数 $t$ に対し、
- $N_t$ は $1 \leq N_t \leq 10^{18}$ を満たす整数
- $B_t$ は $1 \leq B_t \leq 10^9$ を満たす整数
- $2$ 以下の各正整数 $i,j$ に対し $A_{t,i,j}$ は $-10^9 \leq A_{t,i,j} \leq 10^9$ を満たす整数
出力
$T$ 以下の各正整数 $t$ に対し、$t$ 行目に $S_{N_t,A_t}$ を $B_t$ で割った余りを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 1 1 1 0 0 1
出力
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) $
であり、$X_{N_1,A_1}$ は $1$ 辺の長さが $1$ の正方形となりその面積 $S_{N_1,A_1}$ は $1$ です。$1$ を $B_1 = 1$ で割った余りは $0$ です。
サンプル2
入力
1 1 2 1 1 1 1
出力
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) $
であり、$X_{N_1,A_1}$ は原点 $(0,0)$ と点 $(2,2)$ を結ぶ線分となりその面積 $S_{N_1,A_1}$ は $0$ です。$0$ を $B = 2$ で割った余りは $0$ です。
サンプル3
入力
2 2 3 1 0 0 2 1 4 1 0 0 -3
出力
0 3
まずは $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) $
であり、$X_{N_1,A_1}$ は $2$ 辺の長さがそれぞれ $2,6$ の長方形となりその面積 $S_{N_1,A_1}$ は $12$ です。$12$ を $B = 3$ で割った余りは $0$ です。
次に $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) $
であり、$X_{N_2,A_2}$ は $2$ 辺の長さがそれぞれ $1,3$ の長方形となりその面積 $S_{N_2,A_2}$ は $3$ です。$3$ を $B = 4$ で割った余りは $3$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。