2450. Counting Rabbits

そろそろ試験もほぼ終わって春休みに入るので、日記を再開。

といことでこの問題。

https://www.spoj.pl/problems/RABBIT1/

なんかいろいろ書いてあるけど、fib(N) mod 2^M を求めればいいらしい。値の範囲が 1 <= M <= 20, 1 <= N <= 2147483647 なので fib(N) が O(log N) で求まらないと無理っぽい。ググってみると行列をn乗することに帰着できるらしい。

http://d.hatena.ne.jp/ha-tan/20080607/1212810690

ということで行列のn乗を O(log N) で計算できればいい。

A^2 = A^1 * A^1
A^4 = A^2 * A^2
A^8 = A^4 * A^4
 ...

とやっていくと、A^(2^k) は O(log N) で計算できるので、例えば N=11 のときは

A^11 = A^(8 + 2 + 1) = A^8 * A^2 * A^1

と分解すると A^N を O(log N) のコストで計算できる。

#include <stdio.h>

// dest <- lhs * rhs & mask
inline void mul(int dest[], const int lhs[], const int rhs[], int mask)
{
    int a = lhs[0] * rhs[0] + lhs[1] * rhs[2];
    int b = lhs[0] * rhs[1] + lhs[1] * rhs[3];
    int c = lhs[2] * rhs[0] + lhs[3] * rhs[2];
    int d = lhs[2] * rhs[1] + lhs[3] * rhs[3];
    dest[0] = a & mask;
    dest[1] = b & mask;
    dest[2] = c & mask;
    dest[3] = d & mask;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        int N, M;
        scanf("%d%d", &N, &M);
        int a[] = {1, 1, 1, 0};
        int b[] = {1, 0, 0, 1};
        int d = 1;
        int mask = (1 << M) - 1;
        while (N > 0) {
            if (N & d) {
                mul(b, b, a, mask);
                N ^= d;
            }
            mul(a, a, a, mask);
            d <<= 1;
        }
        printf("%d\n", b[0]);
    }
}