大凤号装甲空母
第一次写博客，希望大家见谅
大凤号装甲空母 时间限制: 1 Sec 内存限制: 128 MB 提交: 108 解决: 15 [提交] [状态] [命题人:admin] 题目描述 大凤号航空母舰很喜欢算术。 它，是旧日本海军中最为先进的航空母舰。 它，是旧日本海军中最为短命的航空母舰。 同时，她还是最平的航空母舰（龙骧：你说啥？） 如此多第一 …… 一生二，二生三，三生万物 …… 这也许就是大凤喜欢算术的原因吧。 有一天，她看到了这样一道题： 令 电探发现了来自远处的鱼雷，时间不多了。
输入 一行由空格隔开的两个非负整数，分别是n和p。
输出 一行表示答案。
样例输入 复制样例数据 5 97 样例输出 11
解题思路
由x我们可以联想到与斐波那契数列的关系，斐波那契数的通项公式 我们可以用第2n项除以第n项（平方差公式）， 得到结果 右边小于1的先不用考虑，左边第2n项/第n项，考虑直接除的话会爆掉long long，逆元的话做当大于p的时候答案错误。 那只好找规律，打表发现，满足1，3，4，7的类似于斐波那契数列的东西。另外补充一点，第2n项/第n项一定是整数，所以整道题就可以用矩阵快速幂求，自己新建一个斐波那契数列，第一项为1，第二项为3. 到现在为止，左边完成，考虑小于1的那项，当n为奇数时，加上一个小于1的数不会影响结果，所以不用管，当n为偶数时，减去一个小于1的数会使结果减1.所以最后分类讨论一下就可以了。
代码
#include
<bits
/stdc
++.h
>
using namespace std
;
typedef long long ll
;
const int
N = 1e5+50;
const double
S=2.236067;
ll p
;
struct mat
{
ll a
[2][2];
};
mat
mat_mul(mat x
,mat y
)
{
mat res
;
memset(res
.a
,0,sizeof(res
.a
));
for(int i
=0; i
<2; i
++)
for(int j
=0; j
<2; j
++)
for(int k
=0; k
<2; k
++)
res
.a
[i
][j
]=(res
.a
[i
][j
]+x
.a
[i
][k
]*y
.a
[k
][j
])%p
;
return res
;
}
ll
mat_pow(ll n
)
{
mat c
,res
;
c
.a
[0][0]=c
.a
[0][1]=c
.a
[1][0]=1;
c
.a
[1][1]=0;
memset(res
.a
,0,sizeof(res
.a
));
res
.a
[0][0]=3;
res
.a
[0][1]=1;
while(n
)
{
if(n
&1)
res
=mat_mul(res
,c
);
c
=mat_mul(c
,c
);
n
=n
>>1;
}
return res
.a
[0][0];
}
int
main()
{
ll n
;
cin
>>n
>>p
;
if(p
==1)
{
printf("0\n");
}
else if(n
==0)
{
printf("1\n");
}
else if(n
==1)
{
printf("%d\n",1);
}
else
{
ll ans
=mat_pow(n
-2);
if(n
%2==0)
{
ans
--;
}
printf("%lld\n",ans
%p
);
}
}
