12801 大凤号装甲空母

思路

先将题目待求式子打表观察，发现将偶数项+1后的数列满足递推式：

$$a[i]=a[i-2]+a[i-1]$$

因此可以用矩阵快速幂求出前两项为1，3，递推式为上式的数列，如果询问到偶数项，答案在取模意义下减一，奇数项直接输出。
注意输入n小于2的情况会导致矩阵快速幂传入负数，所以需要特殊处理一下。
以及注意p有可能为1，输出时要注意取模。

赛后推导

1.斐波那契数列通项公式：

F ( n ) = 1 5 × [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ] F\left(n\right) =\frac{1}{\sqrt 5} \times \left[ \left( \frac{1+\sqrt5}{2} \right)^n-\left( \frac{1-\sqrt5}{2} \right)^n \right] F(n)=5 ​1​×[(21+5 ​​)n−(21−5 ​​)n]

2.斐波那契数列二倍项的关系：

F ( 2 n ) F ( n ) = F ( n − 1 ) + F ( n + 1 ) \frac{F\left(2n\right)}{F\left(n\right)}=F\left(n-1\right)+F\left(n+1\right) F(n)F(2n)​=F(n−1)+F(n+1)

将第2n项使用平方差公式展开：

F ( 2 n ) = 1 5 × [ ( 1 + 5 2 ) 2 n − ( 1 − 5 2 ) 2 n ] F ( 2 n ) = 1 5 × [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ] × [ ( 1 + 5 2 ) n + ( 1 − 5 2 ) n ] F ( 2 n ) = F ( n ) × [ ( 1 + 5 2 ) n + ( 1 − 5 2 ) n ] F ( 2 n ) F ( n ) = ( 1 + 5 2 ) n + ( 1 − 5 2 ) n F ( n − 1 ) + F ( n + 1 ) = ( 1 + 5 2 ) n + ( 1 − 5 2 ) n a [ n ] = ( 1 + 5 2 ) n + ( 1 − 5 2 ) n ( 1 + 5 2 ) n = a [ n ] − ( 1 − 5 2 ) n \begin{aligned} F\left(2n\right) &= \frac{1}{\sqrt 5} \times \left[ \left( \frac{1+\sqrt5}{2} \right)^{2n}-\left( \frac{1-\sqrt5}{2} \right)^{2n} \right] \\ F\left(2n\right) &= \frac{1}{\sqrt 5} \times \left[ \left( \frac{1+\sqrt5}{2} \right)^{n}-\left( \frac{1-\sqrt5}{2} \right)^{n} \right] \times \left[ \left( \frac{1+\sqrt5}{2} \right)^{n}+\left( \frac{1-\sqrt5}{2} \right)^{n} \right] \\ F\left(2n\right) &=F\left(n\right) \times \left[ \left( \frac{1+\sqrt5}{2} \right)^{n}+\left( \frac{1-\sqrt5}{2} \right)^{n} \right] \\ \frac{F\left(2n\right)}{F\left(n\right)} &= \left( \frac{1+\sqrt5}{2} \right)^{n}+\left( \frac{1-\sqrt5}{2} \right)^{n} \\ F\left(n-1\right)+F\left(n+1\right) &= \left( \frac{1+\sqrt5}{2} \right)^{n}+\left( \frac{1-\sqrt5}{2} \right)^{n} \\ a\left[n\right] &= \left( \frac{1+\sqrt5}{2} \right)^{n}+\left( \frac{1-\sqrt5}{2} \right)^{n} \\ \left( \frac{1+\sqrt5}{2} \right)^{n} &=a\left[n\right] -\left( \frac{1-\sqrt5}{2} \right)^{n} \end{aligned} F(2n)F(2n)F(2n)F(n)F(2n)​F(n−1)+F(n+1)a[n](21+5 ​​)n​=5 ​1​×⎣⎡​(21+5 ​​)2n−(21−5 ​​)2n⎦⎤​=5 ​1​×[(21+5 ​​)n−(21−5 ​​)n]×[(21+5 ​​)n+(21−5 ​​)n]=F(n)×[(21+5 ​​)n+(21−5 ​​)n]=(21+5 ​​)n+(21−5 ​​)n=(21+5 ​​)n+(21−5 ​​)n=(21+5 ​​)n+(21−5 ​​)n=a[n]−(21−5 ​​)n​

等号左侧即为答案，等号右侧的第一项a[n]即为上文构造出的前两项为1，3，满足上述递推式的数列，接下来看第二项。
由于 $-1<\displaystyle\frac{1-\sqrt5}{2} <0 $，因此$\displaystyle\left|\left( \frac{1-\sqrt5}{2} \right)^{n}\right|<1$，因此有：

1. 当n为奇数时， 0 < − ( 1 − 5 2 ) n < 1 0<\displaystyle-\left( \frac{1-\sqrt5}{2} \right)^{n}<1 0<−(21−5 ​​)n<1
2. 当n为偶数时， − 1 < − ( 1 − 5 2 ) n < 0 -1<\displaystyle-\left( \frac{1-\sqrt5}{2} \right)^{n}<0 −1<−(21−5 ​​)n<0

所以n为奇数时 ⌊ ( 1 + 5 2 ) n ⌋ = a [ n ] \displaystyle\lfloor\left( \frac{1+\sqrt5}{2} \right)^{n}\rfloor=a[n] ⌊(21+5 ​​)n⌋=a[n]，n为偶数时 ⌊ ( 1 + 5 2 ) n ⌋ = a [ n ] − 1 \displaystyle\lfloor\left( \frac{1+\sqrt5}{2} \right)^{n}\rfloor=a[n]-1 ⌊(21+5 ​​)n⌋=a[n]−1。

代码

#include 
typedef long long ll;
using namespace std;
int mod=1e9+7;
const int N=50;
const int M=5;
int K=2;
struct Matrix
{ll a[M][M];
};
Matrix mul(Matrix &a,Matrix b)
{Matrix tmp;for(int i=0;i<=K;i++)for(int j=0;j<=K;j++)tmp.a[i][j]=0;for(int i=1;i<=K;i++)for(int j=1;j<=K;j++)for(int k=1;k<=K;k++)tmp.a[i][j]=(tmp.a[i][j]+a.a[i][k]*b.a[k][j])%mod;return tmp;
}
Matrix pow(Matrix &a,ll b)
{Matrix ans;for(int i=1;i<=K;i++)for(int j=1;j<=K;j++)ans.a[i][j]=i==j?1:0;while(b){if(b&1) ans=mul(ans,a);a=mul(a,a);b>>=1;}return ans;
}
int main()
{//打表找规律部分/*long double d=5;for(int i=1;i<=20;i++){printf("%lf %lf\n",pow((sqrt(5)+1)/2.0,i),pow((sqrt(5)-1)/2.0,i));a[i]=floor(pow((sqrt(5)+1)/2.0,i));cout<ll n,p;scanf("%lld%lld",&n,&p);if(n<=1){cout<<1ll%p;return 0;}if(n==2){cout<<2ll%p;return 0;}mod=p;Matrix a;a.a[1][1]=a.a[1][2]=a.a[2][1]=1;a.a[2][2]=0;Matrix b;b.a[1][1]=3;b.a[2][1]=1;Matrix ans,tmp;tmp=pow(a,n-2);ans=mul(tmp,b);if(n%2==1) printf("%lld",ans.a[1][1]%p);else printf("%lld",((ans.a[1][1]-1)%p+p)%p);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！