Codeforces Round #140 (Div. 1) A : Flying Saucer Segments
問題概要
N(<10^9)個のリングがあるハノイの塔で、3つある柱のうち隣接する柱にのみ移動することができる。最小手順を求める問題。
解法
f(n+1) = 3*f(n) + 2なので、これを解いてf(n)=3^n - 1
acceptされたコード
int solve() { return int((calcPow(3, N, M) + M - 1) % M); }
N(<10^9)個のリングがあるハノイの塔で、3つある柱のうち隣接する柱にのみ移動することができる。最小手順を求める問題。
f(n+1) = 3*f(n) + 2なので、これを解いてf(n)=3^n - 1
int solve() { return int((calcPow(3, N, M) + M - 1) % M); }