比较无聊的题，求斐波那契数的第N^M项。 f(0) = 0, f(1) = 1, f(n) = f(n - 1) + f(n - 2)，结果对10000103取模。 N, M在[0..10^7]之间。要求复杂度：时间O(log(N * M))，空间O(1)。

分析： fib数取模有周期，并且对质数的周期一定是从最开头开始。也就在对P取模下，一定有f(T) == f(0)。关于周期的求法有原根之类的方法……但是本题直接暴力就行。算得

T = 20000208。后面就是矩阵乘方了。

代码：

// you can also use includes, for example:

// #include <algorithm>

#include <vector>

const int MOD = 10000103;

const int T = 20000208;

int mul(long long x,long long y,int M) {

    return x * y % M;

}

int add(int x,int y,int M) {

    return ((x += y) < M)?x:(x - M);

}

void mulmatrix(int a[2][2],int b[2][2],int c[2][2]) {

 int i,j,k;

    for (i = 0; i < 2; ++i) {

        for (j = 0; j < 2; ++j) {

            c[i][j] = 0;

            for (k = 0; k < 2; ++k) {

                c[i][j] = add(c[i][j], mul(a[i][k], b[k][j], MOD), MOD);

            }

        }

    }

}

void make(int a[2][2],int b[2][2]) {

int i,j;

    for (i = 0; i < 2; ++i) {

        for (j = 0; j < 2; ++j) {

            a[i][j] = b[i][j];

        }

    }

}

int solution(int N, int M) {

    // write your code here...

/*int T;

    vector<int> f;

    f.push_back(0);

    f.push_back(1);

    for (T = 2; ; ++T) {

        f.push_back(add(f[T - 1], f[T - 2], MOD));

        if ((f[T] == 1) && (f[T - 1] == 0)) {

            --T;

            break;

        }

    }

    return T;*/

    int p = 1, x = N;

    for (; M; M >>= 1) {

        if (M & 1) {

            p = mul(p,x,T);

        }

        x = mul(x,x,T);

    }

    if (p-- == 0) {

        return 0;

    }

    int a[2][2],b[2][2],c[2][2];

    a[0][0] = a[1][1] = b[0][1] = b[1][0] = b[1][1] = 1;

    a[0][1] = a[1][0] = b[0][0] = 0;

    for (; p; p >>= 1) {

        if (p & 1) {

            mulmatrix(a, b, c);

            make(a, c);

        }

        mulmatrix(b, b, c);

        make(b, c);

    }

    return a[1][1];

}