题解 P2544 【[AHOI2004]数字迷阵】

· · 题解

矩阵快速幂 + 斐波那契数列通项公式

第一列的通项公式

*f[i]=trunc(it+t-1) , t=(1+sqrt(5))/2 trunc为取整**

求出第一列的数 再用第一列和第二列的关系 求出第二列的数

这里的时候要判断一下 输入的 j 若 <=2 就输出即可 注意：输出的时候也要取模

然后就是矩阵快速幂

四格矩阵：x1,x2,x3,x4 为矩阵从上到下从左到右的四个数

两格矩阵：x,y 为从上到下的两个数

然后应用矩阵快速幂和 矩阵乘法 求出结果就可以了

注意：快速幂的终止条件为：单位矩阵 见下图

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue> 
#define MAXN 1000005
#define LL long long
#define MOD 100000007
using namespace std;
struct juzhen{
    LL int x,y;
};
struct jz{
    LL int x1,x2,x3,x4;
};
LL int a,b,m,d1,d2;
juzhen t,ans;
jz n,q;
jz mul(jz x,jz y)
{
    jz tt;
    tt.x1=(x.x1*y.x1%m+x.x2*y.x3%m)%m;
    tt.x2=(x.x1*y.x2%m+x.x2*y.x4%m)%m;
    tt.x3=(x.x3*y.x1%m+x.x4*y.x3%m)%m;
    tt.x4=(x.x3*y.x2%m+x.x4*y.x4%m)%m;
    return tt;
}
juzhen mull(jz x,juzhen y)
{
    juzhen tt;
    tt.x=(x.x1*y.x%m+x.x2*y.y%m)%m;
    tt.y=(x.x3*y.x%m+x.x4*y.y%m)%m;
    return tt;
}
jz fast(jz x,int p)
{
    if(p==0)
        return q;
    jz l=fast(x,p/2);
    if(p%2==0)
        return mul(l,l);
    return mul(mul(l,l),n);
}
int main()
{
    n.x1=n.x2=n.x3=1;
    n.x4=0;
    q.x1=q.x4=1;
    q.x2=q.x3=0;
    scanf("%lld%lld%lld",&a,&b,&m);
    d1=(a*((1+sqrt(5))/2)+a-1);
    d2=2*d1-a+1;
    if(b==1)
    {
        printf("%lld",d1%m);
        return 0;
    }
    if(b==2)
    {
        printf("%lld",d2%m);
        return 0;
    }
    t.x=d2;t.y=d1;
    ans=mull(fast(n,b-2),t);
    printf("%lld",ans.x);
    return 0;
}