P2544 [AHOI2004] 数字迷阵 题解

Satellite_system · 2025-11-20 16:16:10 · 题解

思路分析:

知道前两项的斐波那契数列可以直接矩阵快速幂求出任意一项，而根据题目说的 A_{i,2}=2A_{i,1}−(i−1)，我们现在的问题就是求出这个矩阵的第一列。

首先把这个数列拿出来：

这个似乎是线性增长的，我们使用神秘工具拟合直线。

得到：

尝试直接取整，发现有有些值偏小了，我们大胆猜想系数不会很复杂，于是调整成：

发现小的数据对了，提交发现没分……这意味着不能得出 O(1) 的公式吗？不可能，秉持着先相信后相信的原则，再结合与斐波那契数列相关的黄金分割，我们注意到 2.62=2+0.62\approx 2+0.618\approx 2+\dfrac{\sqrt5-1}{2}=\dfrac{\sqrt5+3}{2}！这看起来很对，提交通过了所以就对了吧……

于是我们给公式猜出来了……

AC Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int mod;
struct Mat{int d[2][2];}a,b;
Mat operator*(Mat x,Mat y){
    Mat z;
    z.d[0][0]=(x.d[0][0]*y.d[0][0]+x.d[0][1]*y.d[1][0])%mod;
    z.d[0][1]=(x.d[0][0]*y.d[0][1]+x.d[0][1]*y.d[1][1])%mod;
    z.d[1][0]=(x.d[1][0]*y.d[0][0]+x.d[1][1]*y.d[1][0])%mod;
    z.d[1][1]=(x.d[1][0]*y.d[0][1]+x.d[1][1]*y.d[1][1])%mod;
    return z;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m;cin>>n>>m>>mod;
    a.d[0][0]=(int)(n*(3+sqrt(5))/2-1)%mod;
    a.d[0][1]=(2*a.d[0][0]-n%mod+1+mod)%mod;
    b.d[0][1]=b.d[1][0]=b.d[1][1]=1;
    if(m==1)return cout<<a.d[0][0],0;
    m-=2;
    while(m){
        if(m&1)a=a*b;
        b=b*b,m>>=1;
    }cout<<a.d[0][1];
    return 0;
}