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

· · 题解

首先我们可以判断出每行都是变形的斐波那契数列,又因为a[i][2]=2a[i][1]-(i-1),所以本质上a[i][j]只与第i行的第一个元素有关,那么关键求a[i][1]

我们发现第一列增加的值为2或3,其实我们可以发现第一次(第二行)+3,后面两次(3,4行)分别+2-3,再后面的3次是前两次的序列和,即3-2-3......

每一次往后推的项数满足斐波那契数列,且就是前面两次的那些项连起来.即第一列通项为f[i]=trunc(i*t+t-1),其中t=(1+sqrt(5))/2

所以我们可以用O(1)的时间求a[i][1],但是需要O(N)的时间求a[i][j],那么我们可以令f[0]=1,f[1]=1,a=1,b=1,则

m=(1+sqrt(5))/2,k=(1-sqrt(5))/2,f[n]=((k^n)*(1-m)-(m^n)*(1-k))/(k-m)

即f[n]=(m^(n+1)-k^(n+1))/sqrt(5);

其实就是斐波那契数列通项公式

其他行就是初值不一样而已,代码不想写注释,自己都觉得奇丑无比......

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long LL;
int n,m,p;
int x[101][3][3],y[3][3],z[3][3],a[101],k1,k2,ans;
int i,j,k,l;

int main() {
    scanf("%d%d%d",&n,&m,&p);
    m--;
    x[0][1][2]=x[0][2][1]=x[0][2][2]=1;
    a[0]=1;
    for(i=1;a[i-1]*2<=m;i++) {
        a[i]=a[i-1]*2;
        for(j=1;j<=2;j++)
            for(k=1;k<=2;k++) 
                for(l=1;l<=2;l++)
                    x[i][j][k]=(x[i][j][k]+(LL)x[i-1][j][l]*x[i-1][l][k])%p;
    }
    y[1][1]=y[2][2]=1;
    for(i--;i>=0;i--) {
        if(a[i]<=m) {
            m-=a[i];
            for(j=1;j<=2;j++) 
                for(k=1;k<=2;k++)
                    for(l=1;l<=2;l++) 
                        z[j][k]=(z[j][k]+(LL)x[i][j][l]*y[l][k])%p;
            for(j=1;j<=2;j++) 
                for(k=1;k<=2;k++) {
                    y[j][k]=z[j][k];
                    z[j][k]=0;
                }
        }
    }
    k1=((LL)(n*(1+sqrt(5))/2+n-1))%p;
    k2=((2*k1-n+1)%p+p)%p;
    ans=((LL)k1*y[1][1]+(LL)k2*y[1][2])%p;
    printf("%d\n",ans);
    return 0;
}