No.2444 一次変換と体積
タグ : / 解いたユーザー数 28
作問者 : 👑
p-adic
/ テスター :
Kazun
問題文
入力に $2$ 個の正整数 $N$ と $B$ と、非負整数係数 $3$ 次正方行列 $A$ が与えられます。
$\mathbb{R}^3$ の部分集合 $\{x \in \mathbb{R}^3 \mid A^N x \in [0,1]^3\}$ を $X$ と置き、$X$ の体積を $V$ と置きます。
ここでは正実数の逆数の定義を拡張し、$0^{-1}$ を $\infty$ と定義し、$\infty^{-1}$ を $0$ と定義します。また $\infty$ を $B$ で割った余りを $\infty$ と定義します。
この時 $V^{-1}$ は非負整数または $\infty$ であることが証明可能であるので、それを $B$ で割った余りを求めてください。
以下、集合の記法や体積などの厳密な定義を知らない人向けの説明をします。（クリックで開く）
$\mathbb{R}^3$ は $3$ 次元実数ベクトル全体の集合を表し、$[0,1]^3$ は $3$ 次元実数ベクトルであって各成分が $0$ 以上 $1$ 以下であるもの全体の集合を表します。
$X$ の定義 $\{x \in \mathbb{R}^3 \mid A^N x \in [0,1]^3\}$ は $A^N x \in [0,1]^3$ を満たす $\mathbb{R}^3$ の要素 $x$ 全体の集合を表します。
$\mathbb{R}^3$ の部分集合の体積は断りのない限りルベーグ測度を用いて定式化されます。具体的には、$\mathbb{R}^3$ の部分集合 $U$ がルベーグ可則である時にのみ $U$ の体積が定義され、その値は $U$ を $\mathbb{R}^3$ のルベーグ測度に代入した値（または等価な言い換えとして、定数関数 $1$ を $U$ 上でルベーグ積分した値）として定められます。
例えば $1$ 頂点から伸びる $3$ 辺の長さがそれぞれ $a,b,c$ である直方体の体積は $abc$ となるなど、この定式化は高校までで習う体積の公式と整合的です。
今回扱う部分集合 $X$ はルベーグ可測であることが知られているためその体積 $V$ は非負実数または $\infty$ として定まり、それが正実数である（つまり $0$ でも $\infty$ でもない）時は結果的に $V^{-1}$ が正整数となることが証明可能です。
なお積分などで現れる $\infty$ は、$\mathbb{R}$ に属さないことが分かっている１つの項を適当に固定してそれを $\infty$ と置くことで定式化されます。どんな項を $\infty$ と置いても影響が出ないように議論をするため具体的にどう置くかを明言しないことが多いのですが、定式化の具体例が必要な場合は $\infty$ を例えば $\mathbb{R}$ そのものであると定義してしまえば $\infty$ が $\mathbb{R}$ に属さないこと、すなわち実数と区別できることが分かります。そして必要ならば $\mathbb{R} \cup \{\infty\}$ には $\mathbb{R}$ の順序や演算を拡張するようなものを適宜定めて使うことが多いです。
入力
$3$ 以下の各正整数 $i,j$ に対し、$A$ の $(i,j)$ 成分を $A_{i,j}$ と置きます。この時、入力は以下の形式で標準入力から与えられます：
$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}$
- $1$ 行目に $N, B$ が半角空白区切りで与えられます。
- $3$ 以下の各正整数 $i$ に対し、$1+i$ 行目に $A_{i,1}, A_{i,2}, A_{i,3}$ が半角空白区切りで与えられます。
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 10^6$ を満たす整数
- $B$ は $1 \leq B \leq 10^6$ を満たす整数
- $3$ 以下の任意の正整数 $i,j$ に対し、$A_{i,j}$ は $0 \leq A_{i,j} \leq 10^6$ を満たす整数
出力
$V^{-1}$ を $B$ で割った余りを $1$ 行に出力してください。
ただし $\infty$ を出力する時はinftyと出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 2 1 0 0 0 1 0 0 0 1
出力
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) $
であり、$X$ は $1$ 辺の長さが $1$ の立方体となりその体積 $V$ は $1$ です。$1^{-1} = 1$ を $B = 2$ で割った余りは $1$ です。
サンプル2
入力
1 2 1 1 1 1 2 1 1 1 2
出力
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) $
であり、$X$ は平行六面体となりその体積 $V$ は $1$ です。$1^{-1} = 1$ を $B = 2$ で割った余りは $1$ です。
サンプル3
入力
2 3 1 1 1 1 1 1 1 1 1
出力
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) $
であり、$X$ は平面を正の有限幅だけ平行移動させた軌跡として得られる立体となりその体積 $V$ は $\infty$ です。
$\infty^{-1}$ は $0$ と定義したので、$\infty^{-1}$ を $B$ で割った余りは $0$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。