首页 > 代码库 > HDU 1757 矩阵相乘，快速幂模板题

HDU 1757 矩阵相乘，快速幂模板题

2024-09-01 11:59:51   223人阅读

HDU 1757

题意： 　If x < 10, f(x) = x;  

　　　　 If x >= 10, f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10); 

　　　　  给出k和mod，求f(k)。

总结： 1、特别注意，矩阵相乘不满足交换律，即a*b != b*a。  2、感觉推方程有点困难。 3、矩阵初始化注意。


f(x-10)   0 0 0 0 0 0 0 0 0        ( first矩阵 )      
f(x-9)     0 0 0 0 0 0 0 0 0
f(x-8)     0 0 0 0 0 0 0 0 0
f(x-7)     0 0 0 0 0 0 0 0 0
f(x-6)     0 0 0 0 0 0 0 0 0
f(x-5)     0 0 0 0 0 0 0 0 0
f(x-4)     0 0 0 0 0 0 0 0 0
f(x-3)     0 0 0 0 0 0 0 0 0
f(x-2)     0 0 0 0 0 0 0 0 0
f(x-1)     0 0 0 0 0 0 0 0 0

*

  0 1 0 0 0 0 0 0 0 0　　　　　　( temp矩阵 )
  0 0 1 0 0 0 0 0 0 0
  0 0 0 1 0 0 0 0 0 0
  0 0 0 0 1 0 0 0 0 0
  0 0 0 0 0 1 0 0 0 0
  0 0 0 0 0 0 1 0 0 0
  0 0 0 0 0 0 0 1 0 0
  0 0 0 0 0 0 0 0 1 0
  0 0 0 0 0 0 0 0 0 1

a9 8 7 6 5 4 3 2 1 0  (这一行是ai)

=
            
f(x-9)     0 0 0 0 0 0 0 0 0
f(x-8)     0 0 0 0 0 0 0 0 0
f(x-7)     0 0 0 0 0 0 0 0 0
f(x-6)     0 0 0 0 0 0 0 0 0
f(x-5)     0 0 0 0 0 0 0 0 0
f(x-4)     0 0 0 0 0 0 0 0 0
f(x-3)     0 0 0 0 0 0 0 0 0
f(x-2)     0 0 0 0 0 0 0 0 0
f(x-1)     0 0 0 0 0 0 0 0 0
f(x)        0 0 0 0 0 0 0 0 0   

技术分享 
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<bitset>
#include<vector>
#include<set>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define F(i,a,b)  for (int i=a;i<b;i++)
#define FF(i,a,b) for (int i=a;i<=b;i++)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N = 1e5+10, Maxn = 15;

ll k,m=100;
struct Mat
{
    ll mat[Maxn][Maxn];
    Mat() {
        mes(mat,0);
        F(i,0,Maxn) mat[i][i]=1;
    }
} E;
Mat first, temp;

Mat operator * (Mat a, Mat b)
{
    Mat ans;
    memset(ans.mat, 0, sizeof(ans.mat));
    for (int i = 0; i < Maxn; i++)
        for (int j = 0; j < Maxn; j++)
            for (int k = 0; k < Maxn; k++)
                ans.mat[i][j] = (ans.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % m;
    return ans;
}
Mat operator ^ (Mat a,ll x)
{
    Mat p = E, q = a;
    while (x) {
        if(x&1)  p = p*q;
        x>>=1;
        q = q*q;
    }
    return p;
}
int main()
{
    mes(first.mat, 0);
    F(i,0,10) first.mat[i][0]=i;
    while(~scanf("%lld%lld", &k, &m)) {
        mes(temp.mat, 0);
        FF(i,0,8) temp.mat[i][i+1]=1;
        F(i,0,10) {
            scanf("%lld", &temp.mat[9][9-i]);
        }
        if(k<10) {
            printf("%lld\n", k);
            continue;
        }
        Mat ans= (temp^(k-9))*first;   //注意，这里顺序不要反了
        printf("%lld\n", ans.mat[9][0]);
    }

    return 0;
}
View Code

 

矩阵模板

const int MOD , Maxn;  //MOD作余，Maxn为矩阵范围  
struct Mat
{
    ll mat[Maxn][Maxn];     //开的long long
    Mat() {
        mes(mat,0);
        F(i,0,Maxn) mat[i][i]=1;    //对角线初始化为1，其它为0
    }
} E;   //单位矩阵
Mat first, temp;

Mat operator * (Mat a, Mat b)   //重载 * ，特别注意，矩阵相乘不满足交换律，即a*b != b*a
{
    Mat ans;
    memset(ans.mat, 0, sizeof(ans.mat));
    for (int i = 0; i < Maxn; i++)
        for (int j = 0; j < Maxn; j++)
            for (int k = 0; k < Maxn; k++)
                ans.mat[i][j] = (ans.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD;
    return ans;
}

Mat operator ^ (Mat a,ll x)    ////重载 ^
{
    Mat p = E, q = a;
    while (x) {
        if(x&1)  p = p*q;
        x>>=1;
        q = q*q;
    }
    return p;
}

Mat mul(Mat a,Mat b)    //函数 *
{
    Mat ans;
    int i,j,k;
    for(i=0;i<Maxn;i++){
        for(j=0;j<Maxn;j++)
        {
            ans.mat[i][j]=0;
            for(k=0;k<Maxn;k++){
                ans.mat[i][j]+=a.mat[i][k]*b.mat[k][j]%m;
                ans.mat[i][j]%=m;
            }
        }
    }
    return ans;
}

Mat Pow_Mod(Mat s, int b){   //函数开方
    Mat ans;
    for(int i=0; i<Maxn; ++i) ans.mat[i][i]=1;
    while(b){
        if(b&1) ans=mul(ans, s);
        s= mul(s, s);
        b>>=1;
    }
    return ans;
}

void prMat(Mat a)   //打印矩阵
{
    int i,j;
    for(i=0;i<Maxn;i++)
    {
        for(j=0;j<Maxn;j++)
            printf("%d ",a.mat[i][j]);
        puts("");
    }
    puts("");
    return ;
}

 

HDU 1757 矩阵相乘，快速幂模板题


联系
我们