問題一覧 >
教育的問題
No.2444 一次変換と体積
レベル :
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ :
/
解いたユーザー数 29
作問者 : 👑
/ テスター :
👑
問題文最終更新日: 2023-09-05 23:33:27
問題文
入力に 2 2 2 N N N B B B 3 3 3 A A A
R 3 \mathbb{R}^3 R 3 { x ∈ R 3 ∣ A N x ∈ [ 0 , 1 ] 3 } \{x \in \mathbb{R}^3 \mid A^N x \in [0,1]^3\} { x ∈ R 3 ∣ A N x ∈ [ 0 , 1 ] 3 } X X X X X X V V V
ここでは正実数の逆数の定義を拡張し、0 − 1 0^{-1} 0 − 1 ∞ \infty ∞ ∞ − 1 \infty^{-1} ∞ − 1 0 0 0 ∞ \infty ∞ B B B ∞ \infty ∞
この時 V − 1 V^{-1} V − 1 ∞ \infty ∞ B B B
以下、集合の記法や体積などの厳密な定義を知らない人向けの説明をします。（クリックで開く）
R 3 \mathbb{R}^3 R 3 3 3 3 [ 0 , 1 ] 3 [0,1]^3 [ 0 , 1 ] 3 3 3 3 0 0 0 1 1 1
X X X { x ∈ R 3 ∣ A N x ∈ [ 0 , 1 ] 3 } \{x \in \mathbb{R}^3 \mid A^N x \in [0,1]^3\} { x ∈ R 3 ∣ A N x ∈ [ 0 , 1 ] 3 } A N x ∈ [ 0 , 1 ] 3 A^N x \in [0,1]^3 A N x ∈ [ 0 , 1 ] 3 R 3 \mathbb{R}^3 R 3 x x x
R 3 \mathbb{R}^3 R 3 ルベーグ測度 を用いて定式化されます。具体的には、R 3 \mathbb{R}^3 R 3 U U U U U U U U U R 3 \mathbb{R}^3 R 3 1 1 1 U U U
例えば 1 1 1 3 3 3 a , b , c a,b,c a , b , c a b c abc ab c
今回扱う部分集合 X X X V V V ∞ \infty ∞ 0 0 0 ∞ \infty ∞ V − 1 V^{-1} V − 1
なお積分などで現れる ∞ \infty ∞ R \mathbb{R} R ∞ \infty ∞ ∞ \infty ∞ ∞ \infty ∞ R \mathbb{R} R ∞ \infty ∞ R \mathbb{R} R R ∪ { ∞ } \mathbb{R} \cup \{\infty\} R ∪ { ∞ } R \mathbb{R} R
入力
3 3 3 i , j i,j i , j A A A ( i , j ) (i,j) ( i , j ) A i , j A_{i,j} A i , j
N N N B B B A 1 , 1 A_{1,1} A 1 , 1 A 1 , 2 A_{1,2} A 1 , 2 A 1 , 3 A_{1,3} A 1 , 3 A 2 , 1 A_{2,1} A 2 , 1 A 2 , 2 A_{2,2} A 2 , 2 A 2 , 3 A_{2,3} A 2 , 3 A 3 , 1 A_{3,1} A 3 , 1 A 3 , 2 A_{3,2} A 3 , 2 A 3 , 3 A_{3,3} A 3 , 3
1 1 1 N , B N, B N , B
3 3 3 i i i 1 + i 1+i 1 + i A i , 1 , A i , 2 , A i , 3 A_{i,1}, A_{i,2}, A_{i,3} A i , 1 , A i , 2 , A i , 3
制約
入力は以下の制約を満たします：
N N N 1 ≤ N ≤ 1 0 6 1 \leq N \leq 10^6 1 ≤ N ≤ 1 0 6
B B B 1 ≤ B ≤ 1 0 6 1 \leq B \leq 10^6 1 ≤ B ≤ 1 0 6
3 3 3 i , j i,j i , j A i , j A_{i,j} A i , j 0 ≤ A i , j ≤ 1 0 6 0 \leq A_{i,j} \leq 10^6 0 ≤ A i , j ≤ 1 0 6
出力
V − 1 V^{-1} V − 1 B B B 1 1 1
ただし ∞ \infty ∞ inftyと出力してください。
最後に改行してください。
サンプル
サンプル1
入力サンプルをコピー
入力
1 2
1 0 0
0 1 0
0 0 1
出力
1
A N = ( 1 0 0 0 1 0 0 0 1 ) 1 = ( 1 0 0 0 1 0 0 0 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)
A N = 1 0 0 0 1 0 0 0 1 1 = 1 0 0 0 1 0 0 0 1
であり、X X X 1 1 1 1 1 1 V V V 1 1 1 1 − 1 = 1 1^{-1} = 1 1 − 1 = 1 B = 2 B = 2 B = 2 1 1 1
サンプル2
入力サンプルをコピー
入力
1 2
1 1 1
1 2 1
1 1 2
出力
1
A N = ( 1 1 1 1 2 1 1 1 2 ) 1 = ( 1 1 1 1 2 1 1 1 2 ) \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)
A N = 1 1 1 1 2 1 1 1 2 1 = 1 1 1 1 2 1 1 1 2
であり、X X X V V V 1 1 1 1 − 1 = 1 1^{-1} = 1 1 − 1 = 1 B = 2 B = 2 B = 2 1 1 1
サンプル3
入力サンプルをコピー
入力
2 3
1 1 1
1 1 1
1 1 1
出力
0
A N = ( 1 1 1 1 1 1 1 1 1 ) 2 = ( 3 3 3 3 3 3 3 3 3 ) \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)
A N = 1 1 1 1 1 1 1 1 1 2 = 3 3 3 3 3 3 3 3 3
であり、X X X V V V ∞ \infty ∞
∞ − 1 \infty^{-1} ∞ − 1 0 0 0 ∞ − 1 \infty^{-1} ∞ − 1 B B B 0 0 0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
p-adic
/ テスター :
👑 
Kazun