HDU2256&&HDU4565：给一个式子的求第n项的矩阵快速幂

时间：2021-12-27 05:53:14

HDU2256

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2256

题意：求（sqrt(2)+sqrt(3)）^2n%1024是多少。

这个题算是hdu4565的一个常数版本了，所以我们先说这道题。对于这道题的做法我们可以计算((sqrt(2)+sqrt(3))^2)^n=(5+2*sqrt(6))^n，对于(5+2*sqrt(6))^n我们知道答案必定是以an+bn*sqrt(6)，而对于下一项我们只需要求(an+bn*sqrt(6))*(5+2*sqrt(6))=5*an+12*bn+2*an*sqrt(6)+5*bn*sqrt(6)，所以a(n+1)=5*an+12*bn; b(n+1)=2*an+5*bn。有了这个递推式我们就可以构造矩阵求an，bn。

这里还有一点对于(5+2*sqrt(6))^n=an+bn*sqrt(6); 同理(5-2*sqrt(6))^n=an-bn*sqrt(6)；两式相加(5+2*sqrt(6))^n+(5-2*sqrt(6))^n=2*an，当n趋于无穷的时候lim(5-2*sqrt(6))^n=0，因为5-2*sqrt(6)<1。

所以我们可以得到答案(5+2*sqrt(6))^n约等于2*an，且实际值是比2*an要小的且小于2*an-1要大的，所以由题目的意思我们向下取整，ans=2*an-1；具体看代码，其他都是矩阵快速幂的模板。

//Author: xiaowuga

#include <bits/stdc++.h>

#define maxx INT_MAX

#define minn INT_MIN

#define inf 0x3f3f3f3f

#define n 2

#define MOD 1024

using namespace std;

typedef long long ll;

struct Matrix{

    ll mat[][];

    Matrix operator * (const Matrix & m) const{

        Matrix tmp;

        for(int i=;i<n;i++)

            for(int j=;j<n;j++){

                tmp.mat[i][j]=;

                for(int k=;k<n;k++){

                    tmp.mat[i][j]+=mat[i][k]*m.mat[k][j]%MOD;

                    tmp.mat[i][j]%=MOD;

                }

            }

        return tmp;

    }

};

Matrix POW(Matrix &m,int k){

    Matrix ans;

    memset(ans.mat,,sizeof(ans.mat));

    for(int i=;i<n;i++) ans.mat[i][i]=;

    while(k){

        if(k&) ans=ans*m;

        k/=;

        m=m*m;

    }

    return ans;

}

int main() {

    ios::sync_with_stdio(false);cin.tie();

    ll T,num;

    cin>>T;

    while(T--){

        cin>>num;

        Matrix m;

        m.mat[][]=; m.mat[][]=; m.mat[][]=; m.mat[][]=;

        Matrix ans=POW(m,num-);

        ll sum=,f[]={,};

        for(int i=;i<;i++)

            sum+=ans.mat[][i]*f[i]%MOD;

        sum%=MOD;

        ll x=(*sum-)%MOD;

        cout<<x<<endl;

    }

    return ;

}

HDU4565

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4565

题意：算是上面那道题的一个升级版本啦。现在是a和b不是固定的的常数了。和上面的做法一样。注意题目中给出a-sqrt(b)<1的条件，所以基本和上道题是一样的了，类比一下吧！很简单的。但是这里是向上取整，所以答案是2*an。具体看代码吧。由于上面那道题在常数情况下已经说得很明白了。这道题就不说了

//Author: xiaowuga

#include <bits/stdc++.h>

#define maxx INT_MAX

#define minn INT_MIN

#define inf 0x3f3f3f3f

#define size 2

int MOD;

using namespace std;

typedef long long ll;

struct Matrix{

    ll mat[][];

    void clear(){

        memset(mat,,sizeof(mat));

    }

    Matrix operator * (const Matrix & m) const{

        Matrix tmp;

        for(int i=;i<size;i++)

            for(int j=;j<size;j++){

                tmp.mat[i][j]=;

                for(int k=;k<size;k++){

                    tmp.mat[i][j]+=mat[i][k]*m.mat[k][j]%MOD;

                    tmp.mat[i][j]%=MOD;

                }

            }

        return tmp;

    }

};

Matrix POW(Matrix &m,int k){

    Matrix ans;

    memset(ans.mat,,sizeof(ans.mat));

    for(int i=;i<size;i++) ans.mat[i][i]=;

    while(k){

        if(k&) ans=ans*m;

        k/=;

        m=m*m;

    }

    return ans;

}

int main() {

    ios::sync_with_stdio(false);cin.tie();

    ll  a,b,n;

    while(cin>>a>>b>>n>>MOD){

        Matrix m;

        m.clear();

        m.mat[][]=m.mat[][]=a%MOD;

        m.mat[][]=b%MOD;m.mat[][]=;

        Matrix ans=POW(m,n-);

        ll sum=(ans.mat[][]*a%MOD+ans.mat[][]%MOD)%MOD;

        cout<<*sum%MOD<<endl;

    }

    return ;

}

相关文章