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