构造矩阵

0 1 * a = b

1 1 b a+b

然后快速幂

也可以按照题目所给的直接快速幂

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define N 30 using namespace std; const int mod = 10000; struct matrix { int a[2][2]; }origin; int n=2,m; matrix multiply(matrix x,matrix y) { matrix temp; memset(temp.a,0,sizeof(temp.a)); for(int i=0;i
       
        >=1; A=multiply(A,A); } return res; } void print(matrix x) { for(int i=0;i