标签：matrix int 题解 ll ans 矩阵 ++ res 快速

目录

• 快速幂 矩阵快速幂练习题题解12.28
  • HDU 1061
  • HDU 1575
  • HDU 2035
  • HDU 5015
  • HDU 6198

快速幂 矩阵快速幂练习题题解12.28

HDU 1061

题意：给定T组数据，接下来T行有T个数，求N的N次方的个位数的值

注意:因为只求个位数，所以对个位进行快速幂就可以了

思路：一直累乘的话，N的范围是0 ~ 1e9，显然一个N就要运行乘法1e9次，时间复杂度为O(T * N)，显然会TLE，所以就用到了快速幂，把O(T * N)优化到O(T * logn)

代码如下：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        long long n;
        cin >> n;
        long long x = n,ans = 1;
        while(n)
        {
            if(n % 2 == 1) ans *= x;
            x *= x;
            ans %= 10;
            x %= 10;
            n >>= 1;
        }
        cout << ans << endl;
    }
    return 0;
}

HDU 1575

题意：有T组数据，每组数据给定一个n和k，接下来n行是A这个方阵的各个元素，求A的k次方的方阵的迹

思路：显然用矩阵乘法累乘的时间复杂度为O(T * k)，所以要降为O(T * logk),套用矩阵快速幂就可以了

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,k;
const int N = 20,mod = 9973;
ll a[N][N],ans[N][N];

int Tr() // 求矩阵的迹
{
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
        sum += ans[i][i];
        sum %= mod;
    }
    return sum;
}

void f1() // 余1时的操作
{
    ll c[N][N] = {0};
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            for(int t = 0; t < n; t++)
            {
                c[i][j] += ans[i][t] * a[t][j] % mod;
            }
        }
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            ans[i][j] = c[i][j];
        }
    }
}

void f2() // 余0时的操作
{
    ll c[N][N] = {0};
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            for(int t = 0; t < n; t++)
            {
                c[i][j] += a[i][t] * a[t][j] % mod;
            }
        }
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            a[i][j] = c[i][j];
        }
    }
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin >> n >> k;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                cin >> a[i][j];
            }
        }

        memset(ans,0,sizeof(ans));
        for(int i = 0; i < n; i++) ans[i][i] = 1;

        while(k)
        {
            if(k & 1) f1();
            f2();
            k >>= 1;
        }

        cout << Tr() << endl;
    }
    return 0;
}

HDU 2035

题意：给定a和b，求a的b次方的后三位表示的数

思路：同样是要优化时间复杂度，套用快速幂就可以了

代码如下：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a,b;
    while(cin >> a >> b)
    {
        if(a == 0 && b == 0) break;
        int ans = 1;
        while(b)
        {
            if(b & 1) ans *= a;
            a *= a;
            a %= 1000;
            ans %= 1000;
            b >>= 1;
        }
        cout << ans << endl;;
    }
    return 0;
}

HDU 5015

题意：给定n，m两个数，再给出矩阵第一列的n个元素，矩阵中第一行元素为{0，233，2333，...}，矩阵中有a[i][j] = a[i - 1][j] + a[i][j - 1]，求a[n][m]的值

注意：数组下标是从0开始的，所以数组大小应该是(n + 1) * (m + 1)

思路：因为第一行的元素是{0，233，2333，...}，且根据a[i][j] = a[i - 1][j] + a[i][j - 1]，数组中a[0][0]元素的数值并不影响我们求a[n][m]，所以我们可以设a[0][0]为23，这样我们第一行元素就可以用a[0][i] = a[0][i - 1] * 10 + 3这条式子求得，其中i >= 1。

可以根据a[i][j] = a[i - 1][j] + a[i][j - 1]推导得到

所以就可以求得a[i][j]=a[i][j−1]+a[i−1][j−1]+a[i−2][j−1]+...+a[2][j−1]+a[1][j−1]+10∗a[0][j−1]+3

然后就可以发现我们要求的a[n][m]所在的第m列的元素可以如下图求出

一步步逆推，可得出我们只需要将一个行列数都为n + 2的方阵不断累乘m次就可以得到我们最后需要的上图中左边这个矩阵，再将其中第n + 1行乘上给定的列矩阵就可以得到一个数，就是我们的答案了

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


struct matrix {
    int N;
    ll a[15][15];
    matrix(int N_) //初始化单位矩阵
    {
        N = N_;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                a[i][j] = 0;
            }
        }
    }
    matrix matrix_mul(matrix A, matrix B, ll mod)
    {   // 2个矩阵相乘
        matrix C(A.N);
        for (int i = 0; i < A.N; i++)
        {
            for (int j = 0; j < A.N; j++)
            {
                C.a[i][j] = 0;
                for (int k = 0; k < A.N; k++)
                {
                    C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j] % mod) % mod;
                }
            }
        }
        return C;
    }
    matrix unit(ll n)// 返回一个大小为n×n的单位矩阵
    {
        matrix res(n);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i == j) res.a[i][j] = 1;
                else res.a[i][j] = 0;
            }
        }
        return res;
    }
    matrix matrix_pow(matrix A, ll n, ll mod) // 矩阵快速幂
    {
        matrix res = unit(A.N);
        while (n > 0)
        {
            if (n & 1)                         
                res = matrix_mul(res, A, mod); 
            A = matrix_mul(A, A, mod);         
            n >>= 1;                           
        }
        return res;
    }
    matrix matrix_sum(int n, ll mod)
    {
        matrix res(N * 2);
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                res.a[i][j] = a[i][j];
            }
        }
        //右上角为单位矩阵
        for (int i = 0; i < N; i++)
        {
            for (int j = N; j < 2 * N; j++)
            {
                if (i == j - N) res.a[i][j] = 1;
                else res.a[i][j] = 0;
            }
        }
        //左下角为0矩阵
        for (int i = N; i < 2 * N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                res.a[i][j] = 0;
            }
        }
        //右下角为单位矩阵
        for (int i = N; i < 2 * N; i++)
        {
            for (int j = N; j < 2 * N; j++)
            {
                if (i == j) res.a[i][j] = 1;
                else res.a[i][j] = 0;
            }
        }
        res = matrix_pow(res, n + 1, mod);
        matrix ans(N);
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                ans.a[i][j] = res.a[i][j + N];
            }
        }
        return ans;
    }
    void print() //显示矩阵全部元素
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                cout << a[i][j] << " ";
            }
            cout << endl;
        }

    }
};
ll mod = 10000007;
ll p[11]; // 第一列元素

int main()
{
    int n;
    ll m;
    while (cin >> n >> m)
    {
        for (int i = 1; i <= n; i++)
        {
            cin >> p[i];
        }
        p[0] = 23;
        p[n + 1] = 3;
        matrix A(n + 2);
        for (int i = 0; i <= n; i++)
        {
            A.a[i][0] = 10;
            A.a[i][n + 1] = 1;
        }
        A.a[n + 1][n + 1] = 1;
        for (int i = 1; i <= n; i++) // 下三角矩阵
        {
            for (int j = 1; j <= i; j++)
            {
                A.a[i][j] = 1;
            }
        }
        A = A.matrix_pow(A, m, mod);
        ll ans = 0;
        for (int i = 0; i <= n + 1; i++)
        {
            ans += A.a[n][i] * p[i];
            ans %= mod;
        }
        cout << ans << endl;
    }
	return 0;
}

HDU 6198

题意：找出不能由k个斐波那契数构成的最小数

思路：打表找规律

k	结果
1	4
2	12
3	33
……	……

由此可以看出答案是F(2 * k + 3) - 1，又因为k的数据范围过大，递归求斐波那契数列的时间复杂度为O(2^n),无法直接求得斐波那契数列的值，所以用矩阵来求斐波那契数列的值

注意：可以搜一下如何利用矩阵求得斐波那契数列

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 998244353;

struct Matrix {
    ll n = 2,m = 2;
	ll v[2][2];
    void init()
    {
        memset(v,0,sizeof(v));
    }
};

Matrix Matrix_mul(Matrix &a,Matrix &b)
{
    Matrix res;
    res.init();
    for (int i = 0; i < a.n; i++)
		for (int j = 0; j < b.m; j++)
			for (int k = 0; k < a.m; k++)
				res.v[i][j] = (a.v[i][k] * b.v[k][j] % mod + res.v[i][j]) % mod;
	return res;
}
ll _pow(Matrix &a,int n)
{
    Matrix res;
    res.init();
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            res.v[i][j] = 1;
        }
    }
    while(n)
    {
        if(n & 1) res = Matrix_mul(res,a);
        n >>=1;
        a = Matrix_mul(a,a);
    }
    return (res.v[0][0] + res.v[1][1] * 0) % mod;
}

int main()
{
    int k;
    while(cin >> k)
    {
        Matrix A;
        A.v[0][0] = A.v[0][1] = A.v[1][0] = 1;
        A.v[1][1] = 0;
        ll ans = _pow(A,2 * k + 1);
        ans = (ans - 1 + mod) % mod;
        cout << ans << endl;
    }
    return 0;
}

本次题解如有发现问题的话，麻烦联系计算机214顾芝瑜，谢谢

标签：matrix,int,题解,ll,ans,矩阵,++,res,快速
From： https://www.cnblogs.com/gugu-0369/p/17008310.html