Official

069 - Colorful Blocks 2(★3) Editorial by Kazu1998k


場合の数を求める.

まず, この問題を解くためには, 条件を満たす色の塗り方が何通りかを求められなければならないので, まずは剰余 (割った余り) を気にせずに求めていく.

  • \(N=1\) のとき: 唯一存在するブロックには \(K\) 色の中からどれでも1色塗ることができる. よって, \(K\) 通りである.

  • \(N=2\) のとき: 塗り方が条件を満たすことと, \(2\) つのブロックに塗った色が異なることが必要十分条件である. よって, \(K\) 色の中から異なる \(2\) つの色を順番を区別する場合の選び方は, \(K(K-1)\) 通りである.

  • \(N \geq 3\) のとき: 以下のようにして考えることができる.

    • ブロック \(1\) については \(K\) 色の中から好きな色を選ぶことができる.
    • ブロック \(2\) については \(K\) 色のうち, ブロック \(1\) に塗っていない \((K-1)\) 色の中から好きな色を選ぶことができる.
    • ブロック\(i~(i \geq 3)\) については \(K\) 色のうち, ブロック \((i-2)\) とブロック \((i-1)\) に塗っていない好きな色を選ぶことができる. ここで, 色はブロック \(1,2,\dots,i-1\) の順に塗っていることから, ブロック \((i-2)\) とブロック \((i-1)\) に縫っている色は異なっている. このことから, ブロック \(i\) に塗る色の候補は \((K-2)\) 通りである.

    よって, 条件を満たす色の塗り方は \(K(K-1)(K-2)^{N-2}\) である.

以上の事をまとめると,

\[\begin{cases} K & (N=1) \\ K(K-1) & (N=2) \\ K(K-1)(K-2)^{N-2} & (N \geq 3) \end{cases}=\begin{cases} K & (N=1) \\ K(K-1)(K-2)^{N-2} & (N \geq 2) \end{cases}\]

である. これで条件を満たす色の塗り方の数を求めることができたが, \(N\) が非常に大きいとき, 愚直に \((K-2)^{N-2}\) を計算しようとすると, 時間計算量 \(O(N)\) になり間に合わない. そこで, どのようにして高速化する必要があるのだろうか?


累乗の計算方法

以下, \(M\) を正の整数とし, \(x \in \mathbb{Z}/M\mathbb{Z}\) と非負整数 \(a \in \mathbb{N}\) に対して, \(x^a\) を求めることを考える. つまり, \(x^a\)\(M\) で割った余りはいくつかを求める.

ここで, このテーマに関する重要な式を記す. 非負整数 \(n\) に対して, 以下の等式が成り立つ.

\[x^n=\begin{cases} 1 & (n=0) \\ x \cdot x^{n-1} & (n: 奇数) \\ \left(x^{\frac{n}{2}} \right)^2 & (n:偶数) \end{cases}\]

例; \(3^{13} \pmod{10}\) を求める.

\[3^{13}=3 \cdot 3 ^{12}=3 \cdot (3^6)^2= 3 \cdot ((3^3)^2)^2=3 \cdot ((3 \cdot 3^2)^2)^2\]

\[=3 \cdot ((3 \cdot (3^1)^2)^2)^2=3 \cdot ((3 \cdot (3 \cdot 3^0)^2)^2)^2=3 \cdot ((3 \cdot (3 \cdot 1)^2)^2)^2\]

\[=3 \cdot ((3 \cdot 3^2)^2)^2=3 \cdot ((3 \cdot 9)^2)^2 \equiv 3 \cdot (7^2)^2 \equiv 3 \cdot 9^2 \equiv 3 \cdot 1=3\]

より, \(3^{13} \pmod{10}=3\) である.

この等式を用いて, 以下のようなアルゴリズムを設計する. ただし, \({\tt Power}(x,n,m)\)\(x^n \pmod{m}\) を返す関数とする.

\({\tt Power}(x,n,m)\)

  • \(n=0\) のとき, \(1\) を返す.
  • \(n\) が奇数のとき, \((x \cdot {\tt Power}(x,n-1,m)) \pmod{m}\) を返す.
  • \(n\) が偶数のとき, \(a \gets {\tt Power}(x,n/2,m)\) として, \(a \cdot a \pmod{m}\) を返す.

この \({\tt Power}(x,n,m)\) の計算量について考慮すると, 第2引数について, 高々 2 回の再帰呼び出しで第2引数を半分以下にすることができる. よって, 計算量は \(O(\log n)\) であることがわかった.


このように累乗の部分を計算することによって, 計算量 \(O(\log N) \)でこの問題を解くことができました。

posted:
last update: