A Simple Math Problem HDU - 1757(矩阵快速幂优化递推)

﹏ヽ暗。殇╰゛Y 2024-04-17 20:45 62阅读 0赞

[题目连接][Link 1]

对于这种题，只要构造出矩阵（可能每个构造出的矩阵不同），  
然后用矩阵快速幂去递推。

要注意的是矩阵乘法没有交换律。  
本人很懒不做解释。

#include<bits/stdc++.h>
    #define ll long long
    
    using namespace std;
    const ll N=10;
    
    ll tmp[N][N];
    
    void mul(ll a[][N],ll b[][N],ll n,ll Mod)
    { 
    
        memset(tmp,0,sizeof tmp);
        for(ll i=0; i<n; i++)
    
            for(ll j=0; j<n; j++)
    
                for(ll k=0; k<n; k++)
    
                    tmp[i][j]=(tmp[i][j]%Mod+(a[i][k]%Mod*b[k][j]%Mod)%Mod)%Mod;
    
        for(ll i=0; i<n; i++)
    
            for(ll j=0; j<n; j++)
    
                a[i][j]=tmp[i][j];
    
    }
    ll res[N][N];
    void Pow(ll a[][N],ll n, ll Mod)
    { 
    
        memset(res,0,sizeof res);//n是幂，N是矩阵大小
        for(ll i=0; i<N; i++) res[i][i]=1;
    
        while(n)
        { 
    
            if(n%2)
            { 
                mul(res,a,N, Mod);//res=res*a;复制直接在multi里面实现了；
            }
            mul(a,a,N, Mod);//a=a*a
            n/=2;
    
        }
    
    }
    
    void mult(ll f[][1], ll a[][10], ll Mod)
    { 
        ll tmp[10][1];
        memset(tmp, 0, sizeof(tmp));
        for(int i = 0; i < 10; i++)
        { 
            for(int k = 0; k < 10; k++)
            { 
                tmp[i][0] = (tmp[i][0]%Mod+a[i][k]%Mod*f[k][0]%Mod)%Mod;
            }
        }
        for(int i = 0; i < 10; i++)
        { 
            f[i][0] = tmp[i][0];
        }
    }
    ll a[10][10];
    ll f[10][1];
    int main()
    { 
        ll k, m;
        while(cin>>k>>m)
        { 
    
            if(k < 10)// 小于10 直接输出
            { 
                cout << k<<endl;
                continue;
            }
    
            for(ll i = 0; i < 10; i++) // 初始化f矩阵
            { 
                f[i][0] = (9-i);
            }
    
            // a 矩阵初始值
            memset(a, 0, sizeof(a));
            for(ll i = 0; i < 10; i++)cin>>a[0][i];
            for(ll i= 1; i < 10; i++)a[i][i-1] = 1;
    
            Pow(a, k-9, m); // 矩阵快速幂
            mult( f, res, m);//最后一步
            
            cout <<f[0][0]<<endl;
    
        }
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1757