問題一覧 > 教育的問題

No.2447 行列累乗根

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 6
作問者 : 👑 p-adicp-adic / テスター : hotman78hotman78
0 ProblemId : 9464 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-08-30 09:55:32

問題文

まずは用語の導入です。実数 xx(1,5)(1,5) 桁小数表示とは、xx の小数表示であって整数部分と小数部分がそれぞれ 11 桁と 55 桁であるもののことです。

小数表示について知らない人向けの説明はこちらです。(クリックで開く)

 

xx(1,5)(1,5) 桁小数表示とは、以下を満たす文字列 ss のことです:

  • 99 以下の非負整数のみからなる長さ 66 の数列 (a0,a1,a2,a3,a4,a5)(a_0,a_1,a_2,a_3,a_4,a_5) であって以下の全てを満たすものが存在する:
    • x0x \geq 0 ならば、x=i=0510iaix = \sum_{i=0}^{5} 10^{-i} a_i である。
    • x<0x < 0 ならば、x=i=0510iaix = - \sum_{i=0}^{5} 10^{-i} a_i である。
    • x>0x > 0 ならば、s=a0.a1a2a3a4a5s = a_0.a_1 a_2 a_3 a_4 a_5 である。
    • x=0x = 0 ならば、s=a0.a1a2a3a4a5s = a_0.a_1 a_2 a_3 a_4 a_5 または s=a0.a1a2a3a4a5s = -a_0.a_1 a_2 a_3 a_4 a_5 である。
    • x<0x < 0 ならば、s=a0.a1a2a3a4a5s = - a_0.a_1 a_2 a_3 a_4 a_5 である。

ただし xx(1,5)(1,5) 桁小数表示は一意であるとも存在するとも限らないことに注意してください。

 

実数係数 22 次正方行列 MM の近似的 33 乗根とは、以下の 22 条件を全て満たす実数係数 22 次正方行列 NN のことです:

  1. MN3M - N^3 の各成分の絶対値が 10310^{-3} 未満である。
  2. NN の各成分は (1,5)(1,5) 桁小数表示を持つ。

 

ここで、次の問題を考えます:

入力に実数係数 22対称行列 MM が与えられます。

MM の近似的 33 乗根が存在するか否かを判定し、存在する場合は 11 つ求めてください。

 

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

入力

以下、TT 以下の各正整数 tt に対し、tt 個目の問題に対する入力を MtM_t と表します。また実数係数 22 次正方行列 MM22 以下の正整数 i,ji,j に対し、Mi,jM_{i,j}MM(i,j)(i,j) 成分を表します。

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

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

ここで TT 以下の各正整数 tt に対し、tt 個目の問題に対する入力は以下の形式で標準入力から 22 行(入力全体の 2t2t 行目から 2t+12t + 1 行目まで)で与えられます:

  • 11 行目に (Mt)1,1,(Mt)1,2(M_t)_{1,1}, (M_t)_{1,2}(1,5)(1,5) 桁小数表示が半角空白区切りで与えられます。
  • 22 行目に (Mt)2,1,(Mt)2,2(M_t)_{2,1}, (M_t)_{2,2}(1,5)(1,5) 桁小数表示が半角空白区切りで与えられます。
(Mt)1,1(M_t)_{1,1} (Mt)1,2(M_t)_{1,2}
(Mt)2,1(M_t)_{2,1} (Mt)2,2(M_t)_{2,2}

制約

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

  • TT1T1051 \leq T \leq 10^5 を満たす正整数である。
  • TT 以下の各正整数 tt に対し、tt 個目の問題に対する入力 MtM_t は以下を満たす:
    • MtM_t は実数係数 22対称行列である。
    • MtM_t の各成分は (1,5)(1,5) 桁小数表示を持つ。

出力

TT 以下の各正整数 tt に対し、tt 個目の問題に対する回答を以下の形式で 2t12t-1 行目と 2t2t 行目に出力してください:

  • MtM_t の近似的 33 乗根が存在しないならば、2t12t-1 行目と 2t2t 行目の両方Noと出力してください。
  • No
    No
    
  • MtM_t の近似的 33 乗根が存在するならば、その 11 つを NtN_t と置き、
    • 2t12t-1 行目に (Nt)1,1,(Nt)1,2(N_t)_{1,1}, (N_t)_{1,2}(1,5)(1,5) 桁小数表示を半角空白区切りで出力してください。
    • 2t2t 行目に (Nt)2,1,(Nt)2,2(N_t)_{2,1}, (N_t)_{2,2}(1,5)(1,5) 桁小数表示を半角空白区切りで出力してください。
    (Nt)1,1(N_t)_{1,1} (Nt)1,2(N_t)_{1,2}
    (Nt)2,1(N_t)_{2,1} (Nt)2,2(N_t)_{2,2}
    

なおこの問題はスペシャルジャッジ問題です。正解は 11 つではないかもしれませんが、11 つだけ出力してください。

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

サンプル

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

(0.000000.000000.000000.00000)3(0.000000.000000.000000.00000)=(0.000000.000000.000000.00000) \left( \begin{array}{cc} \displaystyle 0.00000 &\displaystyle 0.00000 \\ \displaystyle 0.00000 &\displaystyle 0.00000 \end{array} \right)^3 - \left( \begin{array}{cc} \displaystyle 0.00000 &\displaystyle 0.00000 \\ \displaystyle 0.00000 &\displaystyle 0.00000 \end{array} \right) = \left( \begin{array}{cc} \displaystyle 0.00000 &\displaystyle 0.00000 \\ \displaystyle 0.00000 &\displaystyle 0.00000 \end{array} \right)

です。この他にも

0.00001 0.00001
0.00001 0.00001

0.00000 9.99999
-0.00000 0.00000

などが正解です。今回は T=1T = 1 なのでこれで全ての問題に答えられました。

サンプル2
入力
1
1.00000 0.00000
0.00000 1.00000
出力
1.00000 0.00000
0.00000 1.00000

(1.000000.000000.000001.00000)3(1.000000.000000.000001.00000)=(0.000000.000000.000000.00000) \left( \begin{array}{cc} \displaystyle 1.00000 &\displaystyle 0.00000 \\ \displaystyle 0.00000 &\displaystyle 1.00000 \end{array} \right)^3 - \left( \begin{array}{cc} \displaystyle 1.00000 &\displaystyle 0.00000 \\ \displaystyle 0.00000 &\displaystyle 1.00000 \end{array} \right) = \left( \begin{array}{cc} \displaystyle 0.00000 &\displaystyle 0.00000 \\ \displaystyle 0.00000 &\displaystyle 0.00000 \end{array} \right)

です。今回は T=1T = 1 なのでこれで全ての問題に答えられました。

サンプル3
入力
2
1.00000 0.00000
0.00000 -1.00000
1.00000 -0.00000
-0.00000 -1.00000
出力
1.00000 0.00000
0.00000 -1.00000
1.00000 -0.00000
-0.00000 -1.00000

(1.000000.000000.000001.00000)3(1.000000.000000.000001.00000)=(0.000000.000000.000000.00000) \left( \begin{array}{cc} \displaystyle 1.00000 &\displaystyle 0.00000 \\ \displaystyle 0.00000 &\displaystyle -1.00000 \end{array} \right)^3 - \left( \begin{array}{cc} \displaystyle 1.00000 &\displaystyle 0.00000 \\ \displaystyle 0.00000 &\displaystyle -1.00000 \end{array} \right) = \left( \begin{array}{cc} \displaystyle 0.00000 &\displaystyle 0.00000 \\ \displaystyle 0.00000 &\displaystyle 0.00000 \end{array} \right)

です。今回は T=2T = 2 なのでこれで全ての問題に答えられました。

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