問題一覧 > 教育的問題

No.2448 一次変換と面積

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 5
作問者 : 👑 p-adicp-adic / テスター : tko919tko919 tko919tko919
1 ProblemId : 9664 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-08-25 21:14:38

問題文

まずは記法の導入です。正整数 NN と整数係数 22 次正方行列 AA に対し、R2\mathbb{R}^2 の部分集合

{xR2|y[0,1]2,x=i=1NAiy}\displaystyle \left\{ x \in \mathbb{R}^2 \middle| \exists y \in [0,1]^2, x = \sum_{i=1}^{N} A^i y \right\}

XN,AX_{N,A} と置き、XN,AX_{N,A} の面積を SN,AS_{N,A} と置きます。SN,AS_{N,A} は非負整数であることが証明可能です。

以下、集合の記法や面積の厳密な定義を知らない人向けの説明をします。(クリックで開く)

 

R2\mathbb{R}^222 次元実数ベクトル全体の集合を表し、[0,1]2[0,1]^222 次元実数ベクトルであって各成分が 00 以上 11 以下であるもの全体の集合を表します。

XAX_A の定義

{xR2|y[0,1]2,x=i=1NAiy}\displaystyle \left\{ x \in \mathbb{R}^2 \middle| \exists y \in [0,1]^2, x = \sum_{i=1}^{N} A^i y \right\}

は、ある y[0,1]2y \in [0,1]^2 を用いて

x=i=1NAiy\displaystyle x = \sum_{i=1}^{N} A^i y

と表せるような R2\mathbb{R}^2 の要素 xx 全体の集合を表します。

R2\mathbb{R}^2 の部分集合の面積は断りのない限りルベーグ測度を用いて定式化されます。具体的には、R2\mathbb{R}^2 の部分集合 UU がルベーグ可則である時にのみ UU の面積が定義され、その値は UUR2\mathbb{R}^2 のルベーグ測度に代入した値(または等価な言い換えとして、定数関数 11UU 上でルベーグ積分した値)として定められます。

例えば 11 頂点から伸びる 22 辺の長さがそれぞれ a,ba,b である長方形の面積は abab となるなど、この定式化は高校までで習う面積の公式と整合的です。

今回扱う部分集合 XN,AX_{N,A} はルベーグ可測であることが知られているためその面積 SN,AS_{N,A} は非負実数または \infty として定まり、今回は特に非負整数となることが証明可能です。

 

ここで次のような問題を考えます:

入力に 22 個の正整数 N,BN, B と整数係数 22 次正方行列 AA が与えられます。

SN,AS_{N,A}BB で割った余りを求めてください。

 

入力の最初に正整数 TT が与えられます。TT 個の問題に答えてください。

入力

この時、入力は以下の形式で標準入力から 1+3T1+3T 行で与えられます:

  • 11 行目に TT が与えられます。
  • TT 以下の各正整数 tt に対し、3t13t - 1 行目から 3t+13t + 1 行目までに tt 番目の問題に対する入力が与えられます。
TT
(11 番目の問題に対する入力)
\vdots
(TT 番目の問題に対する入力)

ここで TT 以下の各正整数 tt に対し、tt 番目の問題に対する入力を Nt,Bt,AtN_t, B_t, A_t と表し、22 以下の各正整数に対する AtA_t(i,j)(i,j) 成分を At,i,jA_{t,i,j} と表すと、tt 番目の問題に対する入力は以下の形式で標準入力から 33 行(入力全体の 3t13t - 1 行目から 3t+13t + 1 行目まで)で与えられます:

  • 11 行目に Nt,BtN_t, B_t が半角空白区切りで与えられます。
  • 22 行目に At,1,1,At,1,2A_{t,1,1}, A_{t,1,2} が半角空白区切りで与えられます。
  • 33 行目に At,2,1,At,2,2A_{t,2,1}, A_{t,2,2} が半角空白区切りで与えられます。
NtN_t BtB_t
At,1,1A_{t,1,1} At,1,2A_{t,1,2}
At,2,1A_{t,2,1} At,2,2A_{t,2,2}

制約

入力は以下の制約を満たします:

  • TT1T1031 \leq T \leq 10^3 を満たす整数
  • TT 以下の各正整数 tt に対し、
    • NtN_t1Nt10181 \leq N_t \leq 10^{18} を満たす整数
    • BtB_t1Bt1091 \leq B_t \leq 10^9 を満たす整数
    • 22 以下の各正整数 i,ji,j に対し At,i,jA_{t,i,j}109At,i,j109-10^9 \leq A_{t,i,j} \leq 10^9 を満たす整数

出力

TT 以下の各正整数 tt に対し、tt 行目に SNt,AtS_{N_t,A_t}BtB_t で割った余りを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
1
1 1
1 0
0 1
出力
0

i=1N1A1i=(1001)1=(1001)\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)

であり、XN1,A1X_{N_1,A_1}11 辺の長さが 11 の正方形となりその面積 SN1,A1S_{N_1,A_1}11 です。11B1=1B_1 = 1 で割った余りは 00 です。

サンプル2
入力
1
1 2
1 1
1 1
出力
0

i=1N1A1i=(1111)1=(1111)\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)

であり、XN1,A1X_{N_1,A_1} は原点 (0,0)(0,0) と点 (2,2)(2,2) を結ぶ線分となりその面積 SN1,A1S_{N_1,A_1}00 です。00B=2B = 2 で割った余りは 00 です。

サンプル3
入力
2
2 3
1 0
0 2
1 4
1 0
0 -3
出力
0
3

まずは 11 個目の問題を考えます。

i=1N1A1i=(1002)1+(1002)2=(2006)\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)

であり、XN1,A1X_{N_1,A_1}22 辺の長さがそれぞれ 2,62,6 の長方形となりその面積 SN1,A1S_{N_1,A_1}1212 です。1212B=3B = 3 で割った余りは 00 です。

 

次に 22 個目の問題を考えます。

i=1N2A2i=(1003)1=(1003)\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)

であり、XN2,A2X_{N_2,A_2}22 辺の長さがそれぞれ 1,31,3 の長方形となりその面積 SN2,A2S_{N_2,A_2}33 です。33B=4B = 4 で割った余りは 33 です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。