十进制矩阵快速幂
<pre><code class="language-cpp">#include <iostream>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
struct Max{
ll a[5][5];
Max operator*(const Max &m){
Max M;
for(int i = 1; i <= 2; i++){
for(int j = 1; j <= 2; j++){
ll sum = 0;
for(int k = 1; k <= 2; k++){
sum = (sum + this->a[i][k] * m.a[k][j] % mod) % mod;
}
M.a[i][j] = sum;
}
}
return M;
}
Max(){
this->a[1][1] = this->a[2][2] = 1;
this->a[1][2] = this->a[2][1] = 0;
}
};
Max qpow(Max a, string s){
Max m;
int n = s.size() - 1;
while(n >= 0){
int b = s[n] - '0';
for(int i = 1; i <= b; i++)
m = m * a;
a = a * a;
Max y = a * a;
Max z = y * y;
a = a * z;
n--;
}
return m;
}</code></pre>