ブログ名

競技プログラミングやお歌のお話をする高菜です。

トップ > AGC 044 C - Strange Dance の解説

AGC 044 C - Strange Dance の解説

問題

atcoder.jp

解説

0 \le i, \ 0 \le j \lt 3 ^ i に対し、 \sigma _ { i, j } は、 3 ^ i で割って j 余るような数の、3 進数表示の下から i 桁目（0 - based index です。）を 1 増加させる写像だとします。

すると、

  • \sigma _ { i, j } は位数 3 です。
  • i が同じもの同士は可換です。
  • \sigma _ { i, j } \sigma _ { k, l } \sigma _ { i, j } ^ { -1 } = \sigma _ { k, \sigma _ { i, j } ( l ) } if 0 \le i \lt k です。
  • ルンバは R = \sigma _ { 0, 0 } \sigma _ { 1, 2 } \sigma _ { 2, 8 } \sigma _ { 3, 26 } \dots と書けます。
  • サルサ S による共役作用は S \sigma _ { i, j } S = \sigma _ { i, S(j) } と書けます。（サルサは位数 2 です。）

上述の可換性を鑑みて、 0 \le i, m \in \mathbb N ^ { 3 ^ i } に対して、 \sigma _ { i, m } = \prod _ { j = 0 } ^ { 3 ^ i - 1 } \sigma _ { i , j } ^ { m _ j } と書きましょう。

すると、サルサとルンバの生成する群の任意の元は、 S^ { k _ S } \cdot \sigma _ { 0, m_0 } \sigma _ { 1, m_1 } \sigma _ { 2, m_ 2 } \dots と書けます。これは、サルサやルンバがこの形でかけることと、この形の元に左からサルサやルンバを掛けてもこの形であることから従います。

あとは、いままで作用したもの全部の掛け算を先述の形で管理して、適宜更新をしていくと良いです。サルサの更新は簡単です。ルンバの更新は、元を N 個掛ける必要がありますが、それぞれについて N 回程度の交換をすることで適切な位置まで持っていくことが出来ます。さらに共役作用は余りを見て適宜条件分岐をするだけですから、定数時間です。したがって更新の時間計算量は N ^ 2 で、これを 3 ^ N 回行いますから、合計で \Theta( 3 ^ N \cdot N ^ 2) のお時間が掛かります。

ツイッターのご様子

そのとおりです。 \Theta( ( 3 ^ N + T ) \cdot N ^ 2) です。ごめんなさい。

う、そのとおりです。修正を怠ってしまって申し訳ない気持ちです（泣）