P2544 [AHOI2004] 数字迷阵题解

思路分析:

知道前两项的斐波那契数列可以直接矩阵快速幂求出任意一项，而根据题目说的

A_{i,2}=2A_{i,1}−(i−1)

，我们现在的问题就是求出这个矩阵的第一列。

首先把这个数列拿出来：

1,4,6,9,12,14,17,19,22,25,27,30,33,35,38,40,43,46,48,51\cdots

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

得到：

y=2.62x-1.52

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

y=2.62x-1

发现小的数据对了，提交发现没分……这意味着不能得出

O(1)

的公式吗？不可能，秉持着先相信后相信的原则，再结合与斐波那契数列相关的黄金分割，我们注意到

2.62=2+0.62\approx 2+0.618\approx 2+\dfrac{\sqrt5-1}{2}=\dfrac{\sqrt5+3}{2}

！这看起来很对，提交通过了所以就对了吧……

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

AC Code:

CPP

#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;
}

P2544 [AHOI2004] 数字迷阵题解

文章操作

思路分析:

AC Code:

相关推荐

评论

P2544 [AHOI2004] 数字迷阵题解