ZZULI 1478 不死兔子 - 矩阵连乘求超大斐波那契数

#include <iostream>
#define M 2011403
using namespace std;
struct mat{
        int a[2][2];
};
mat mul(mat x,mat y) {
        mat ret;
        int i,j,k;
        for(i = 0; i < 2; ++ i)
        for(j = 0; j < 2; ++ j){
                long c = 0;
                for(k = 0; k < 2; ++ k)
                c = (c + (long long )x.a[i][k] * y.a[k][j] % M) % M;
                ret.a[i][j] = c;
        }
        return ret;
}
int fib(int n){
        if(n <= 1) return 1;
        mat F,t;
        F.a[0][0] = 1;F.a[0][1] = 1;
        F.a[1][0] = 1;F.a[1][1] = 0;
        t=F; 
        n-=2;
        while(n){
                if(n & 1) F = mul(F,t);
                t = mul(t,t);
                n >>= 1;
        }
        return (F.a[0][0] + F.a[0][1] ) % M;
}
int main() {
        int n,N;
        cin>>N;
        while (N--) {
                cin>>n;
                cout<<fib(n)<<endl;
        }
        return 0;
}