UVA_10229

    将斐波那契数用矩阵形式表示，然后再做快速幂取模即可。

#include
     
       #include
      
        #define MAXD 50 long long int N, M, D, a[MAXD][4], b[4]; void pow_mod(long long int n, int e) {
   if(n == 1)     {
           a[e][0] = a[e][1] = a[e][2] = 1;         a[e][3] = 0; return ;     }     pow_mod(n / 2, e + 1);     a[e][0] = (a[e + 1][0] * a[e + 1][0] + a[e + 1][1] * a[e + 1][2]) % D;     a[e][1] = (a[e + 1][0] * a[e + 1][1] + a[e + 1][1] * a[e + 1][3]) % D;     a[e][2] = (a[e + 1][2] * a[e + 1][0] + a[e + 1][3] * a[e + 1][2]) % D;     a[e][3] = (a[e + 1][2] * a[e + 1][1] + a[e + 1][3] * a[e + 1][3]) % D; if(n % 2)     {
           b[0] = (a[e][0] * a[0][0] + a[e][1] * a[0][2]) % D;         b[1] = (a[e][0] * a[0][1] + a[e][1] * a[0][3]) % D;         b[2] = (a[e][2] * a[0][0] + a[e][3] * a[0][2]) % D;         b[3] = (a[e][2] * a[0][1] + a[e][3] * a[0][3]) % D;         a[e][0] = b[0], a[e][1] = b[1], a[e][2] = b[2], a[e][3] = b[3];     } } void solve() {
   int i;     D = 1; for(i = 0; i < M; i ++)         D <<= 1;     pow_mod(N - 1, 1);     printf("%lld\n", a[1][0]); } int main() {
       a[0][0] = a[0][1] = a[0][2] = 1;     a[0][3] = 0; while(scanf("%lld%lld", &N, &M) == 2)     {
   if(N == 0 || M == 0)             printf("0\n"); else if(N == 1)             printf("1\n"); else             solve();     } return 0; }