程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu-4656-So Easy!-遞推式+矩陣優化

hdu-4656-So Easy!-遞推式+矩陣優化

編輯：C++入門知識

題意非常簡單，a,b,n都是正整數，求

Sn=⌈(a+b√)n⌉%m,(a−1)2

這個題目也是2008年Google Codejam Round 1A的C題。

做法其實非常簡單，記(a+b√)n為An，配項

Cn=An+Bn=(a+b√)n+(a−b√)n

兩項恰好共轭，所以Cn是整數。又根據限制條件

(a−1)2

也就是說Cn=⌈An⌉

Sn=(Cn)%m

求Cn的方法是遞推。對Cn乘以(a+b√)+(a−b√)

於是

Cn+1=2aCn−(a2−b)Cn−1

把這個遞推式寫成矩陣形式

[Cn+1Cn]=[2a1−(a2−b)0][CnCn−1]

於是就可以用矩陣快速冪來做了

[Cn+1Cn]=[2a1−(a2−b)0]n[C1C0]

---------------------------------------------------------------------------- 以上是原版的題解。這個題目是我做訓練賽的時候做到的，當時沒做出來，後來看題解，一開始不明白為什麼C[N]=[ A[N] ]; 後來的時候百度了一下共轭的定義發現： C[N]一定是一個整數。 B[N]又小於1. 所以 C[N]=[ A[N] ]=A[N]+B[N];

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
using namespace std;
#define maxn 3001
#define LL long long
struct matrix
{
    LL mat[3][3];
    matrix()
    {
        memset(mat,0,sizeof(mat));
    }
};
int m;
matrix mul(matrix A,matrix B)
{
    matrix C;
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=2;j++)
        {
            C.mat[i][j]=0;
            for(int k=1;k<=2;k++)
            {
                C.mat[i][j]+=A.mat[i][k]*B.mat[k][j];
            }
            C.mat[i][j]%=m;
            if(C.mat[i][j]<0)C.mat[i][j]+=m;
        }
    }
    return C;
}
matrix pows(matrix A,LL p)
{
    matrix B;
    B.mat[1][1]=B.mat[2][2]=1;
    while(p)
    {
        if(p&1)B=mul(B,A);
        A=mul(A,A);
        p>>=1;
    }
    return B;
}
int main()
{
    int a,b,n;
    while(~scanf(%d%d%d%d,&a,&b,&n,&m))
    {
        matrix A;
        A.mat[1][1]=2;
        A.mat[2][1]=2*a;
        matrix B;
        B.mat[1][1]=0;     B.mat[1][2]=1;
        B.mat[2][1]=b-a*a; B.mat[2][2]=2*a;
        B=pows(B,n);
        A=mul(B,A);
        cout<