一、

整数：求a^n，把n化为2*（k1+k2+..+km)； 

矩阵：注意矩阵乘法。

复杂度：O(logn)

tip：取了模（根据题目要求）

1 #include
      
        2 #define mem(a) memset(a,0,sizeof(a)) 3 #define ll long long 4 using namespace std; 5 ll mod=1e9; 6 ll quickpow(ll a,ll n){ 7     ll ans=1; 8     while(n){ 9         if(n&1)10             ans=(ans*a)%mod; //取模11         n>>=1;12         a=(a*a)%mod;13     }14     return  ans%mod;15 }16 int main(){17    cout<
      

1 #include
      
        2 #define mem(a) memset(a,0,sizeof(a)) 3 #define ll long long 4 const int N=1e6+5; 5 using namespace std; 6 ll mod=1e9; 7 struct matrix{ 8   int m[N][N]; 9 };10 matrix mat_multi(matrix a, matrix b){11    matrix ans;12    for(int i=0;i
       
        >=1;36         a=mat_multi(a,a);37     }38     return  ans;39 }
       
      

二、题目

①基础

（1）

关键是循环节

tips：string->int：m=atoi(n.c_str());  

         去字符串：substr(起始，长度）

1 #include
      
        2 #define mem(a) memset(a,0,sizeof(a)) 3 #define ll long long 4 #define inf 0x3f3f3f3f 5 const int N=1e6+5; 6 using namespace std; 7 ll mod=1e4; 8 ll Mod=500; 9 ll ans[205];10 ll quickpow(ll a,ll n){11    ll ans=1;12    while(n){13       if(n&1) ans=(ans*a)%mod;14       n>>=1;15       a=(a*a)%mod;16    }17    return ans%mod;18 }19 int main(){20    int k;21 22    string n;23    cin>>k;24    while(k--){25     cin>>n;26     int len=n.size();27     int m;28     if(len>5){29         string n1=n.substr(len-4,4); //起始，长度30         m=atoi(n1.c_str()); //返回一个const *char,内容相同31     }32     else33     m=atoi(n.c_str());34     cout<
       
        <