naoya_t@hatenablog

いわゆるチラシノウラであります

〈蟻本拾い読み〉対称性のある数え上げ(p.268), スタックの利用(p.298)

蟻本拾い読み

対称性のある数え上げ(p.268) - ポリア(ポーヤ)の数え上げ定理 (Pólya enumeration theorem)

「回転すると同じになるパターンは排除する」タイプの数え上げに使える定理。

ジョージ・ポリア(ポーヤ)はハンガリー生まれの数学者。
いかにして問題をとくか」の著者。

いかにして問題をとくか
G. ポリア
丸善
売り上げランキング: 7,998

例えば90度\displaystyle(=\frac{2π}{4})単位で回転できる場合

田の字のような4マスをc色で塗り分けるとする。

  • 90度 (=1x2π/4) 回転したら同じになるもの → 1マスの塗り分け → c通り
  • 180度 (=2x2π/4) 回転したら同じになるもの → 2マスの塗り分け → c^2通り
  • 270度 (=3x2π/4) 回転したら同じになるもの → 1マスの塗り分け → c通り
  • 360度 (=4x2π/4) (=0度) 回転したら同じになるもの → 4マスの塗り分け → c^4通り

をそれぞれ数え上げて、それらの相加平均を取ったものが答え。

kマス分回転するとしたら gcd(k,4) マスの塗り分けになるので c^{gcd(k,4)}通り。
それぞれ c, c^2, c, c^4 通りあるので \displaystyle\frac{c+c^2+c+c^4}{4} が答え。

回転の単位が \displaystyle\frac{2π}{n} の場合。

  • \displaystyle 1\cdot\frac{2π}{n} 回転したら同じになるもの → gcd(1,n)=1マスの塗り分け
  • \displaystyle 2\cdot\frac{2π}{n} 回転したら同じになるもの → gcd(2,n)マスの塗り分け
  • ...
  • \displaystyle (n-1)\cdot\frac{2π}{n} 回転したら同じになるもの → gcd(n-1,n)=1マスの塗り分け
  • \displaystyle n\cdot\frac{2π}{n}=2π 回転したら同じになるもの → gcd(n,n)=nマスの塗り分け

をそれぞれ数え上げて、合計してnで割る。
$$ \frac{1}{n}\sum_{k=1}^{n} c^{gcd(k,n)} $$
ただこれ n=10^9 とかになるとTLEするよね

nの約数だけ調べる

  • 1\le k\le n のとき gcd(k,n)n の約数のどれかを取る。(たぶん自明だよね)
  • では、それぞれ何回ずつ取る?
  • 約数 df(d) 回現れるとするなら

$$ \frac{1}{n}\sum_{d∈nの約数}^{n} f(d)\cdot c^d $$

1 が現れる回数、即ちgcd(k,n)=1となるkの個数は n と素なすべての自然数 k (1\le k\le n) の個数なので、オイラーのトーシェント関数φを用いてφ(n)と書くことができる。

では d が現れる回数は? gcd(k,n)=d となるkの個数はgcd(\frac{k}{d},\frac{n}{d})=1 となる \frac{k}{d} (1\le\frac{k}{d}\le\frac{n}{d}) の個数なので φ(\frac{n}{d})と書ける。
従って f(d)=φ(\frac{n}{d}) であり
$$ \frac{1}{n}\sum_{d∈nの約数}^{n} φ(\frac{n}{d})\cdot c^d $$
これならnの約数の個数分だけ計算すればいいので余裕でなんとかなる。
n=2^{30}(≒10^9)でも約数は31個。素因数分解済みならφ()の計算は容易である。

参考実装(自分用)

スタックの利用(p.298)

例題はヒストグラムに含まれる長方形面積の最大値を求める問題(どこかで見たことがある)。

自分で思いつくのは、高い順に並べて1つずつ繋げながら長方形の面積の最大値を更新していく方法。
(繋げて新しく出来た山の左右の端にマーキングしておいて、隣りに来た時に山に繋げられるようにしておく)
ソートするのでO(NlogN)。

蟻本で紹介しているのはスタックを使ってO(N)で解く方法。

  • 高さは縦長バーのいずれかの高さに等しいわけで
  • その長方形の高さを左右に伸ばして行って伸ばせなくなる直前までなわけで
  • とすると、あるx座標の縦長バーから左右に伸ばしたときの左限と右限が分かれば (右-左+1)×高さ、で長方形の面積が求まるので
    • その左限と右限を(すべてのx座標について)調べるの、スタックを使えば O(N) で出来るよ
  • それをN通り試せばよくて
    • 表を作っておけばそれぞれO(1)だから、合計でO(N)


スタックを使うところ
  • スタックを用意する。
  • ヒストグラムを左から走査。
  • スタックに今のバーより高い地点の座標が入っていたら捨てる。
    • スタックには今のバーより低い地点の座標しか入っていない、あるいは空の状態になる。
  • ということは
  • スタックのtopにあるのは「現在地点から左に伸ばしてこれ以上伸ばせなくなった地点」=「現在地点から左に伸ばしたときの左限の1つ左」であるから、それ+1が求める左限である
  • 同様に右限を右からの走査で求める。

イデアは分かるんだけど、こういうの(スタックじゃなくて)priority_queueで書いてしまってO(NlogN)から計算量下がらんやんけ、みたいになりがちだったので、スタックでO(N)だよというのは使えるようになりたい。