试题 算法训练 奇异的虫群 -> 矩阵快速幂

#include using namespace std; 

const int mod = 1000000007;

typedef long long ll;

int main() 
{
    ll n;
    cin >> n;
    ll a = 1;
    ll b = 1;
    ll ans = 1;
    for (int i = 2; i ) 
    {
        int temp = a;
        a = (a % mod + b % mod) % mod;
        b = temp; 
    }
    cout  endl;
    return 0;
}
// 超时代码

#include using namespace std; 
typedef long long ll;

ll mul(ll a, ll b, ll p)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans ;
}

int main() 
{
    ll a, b, p;
    cin >> a >> b >> p;
    cout  endl;
    return 0;
}

#include 
#include 
#include 
#include using namespace std; 

typedef long long ll;

const int N = 105, mod = 1000000007;

int n;
ll k;

struct Mat
{
    ll a[N][N]; // longlong存矩阵 否则过程中会爆掉
    Mat()
    {
        memset(a, 0, sizeof a);
    }
    inline void build() //建造单位矩阵
    {
        for (int i = 1; i 1;
    }
}mat;

Mat operator * (const Mat &x, const Mat &y) //重载运算符
{
    Mat z;
    for (int k = 1; k  )
        for (int i = 1; i  )
            for (int j = 1; j  )
                z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j] % mod) % mod;
            
    return z;
}

int main() 
{
    cin >> n >> k;
    for (int i = 1; i )
        for (int j = 1; j  )
            cin >> mat.a[i][j];
    
    Mat ans; 
    ans.build(); // 实际相当于求快速幂中ans=1 这里ans为矩阵 所以初始化为单位矩阵
    while (k)
    {
        if (k & 1) ans = ans * mat;
        mat = mat * mat;
        k >>= 1;
    }
    for (int i = 1; i  )
    {
        for (int j = 1; j  )
            cout ‘ ‘;
        cout  endl;
    }
    return 0;
}

#include 
#include 
#include 
#include using namespace std; 

typedef long long ll;

const int mod = 1000000007;

ll n, k;

struct Mat
{
    ll a[2][2];
    Mat()
    {
        memset(a, 0, sizeof a);
    }
    inline void build()
    {
        for (int i = 0; i 2; i ++ )
            a[i][i] = 1;
    }
}base;

Mat operator * (const Mat &x, const Mat &y)
{
    Mat z;
    for (int k = 0; k 2; k ++ )
        for (int i = 0; i 2; i ++ )
            for (int j = 0; j 2; j ++) 
                z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j] % mod) % mod;
    return z;
}

int main() 
{
    cin >> n;
    base.a[0][0] = 1, base.a[0][1] = 1, base.a[1][0] = 1, base.a[1][1] = 0; //将base初始化为要求n次幂的矩阵
    Mat ans;
    ans.build();
    while (n)
    {
        if (n & 1) ans = ans * base;
        base = base * base;
        n >>= 1;
    }
    cout 0][0]  endl;
    // cout 
    return 0;
}