ACM 题 O: 大凤号装甲空母

大凤号装甲空母

第一次写博客，希望大家见谅

大凤号装甲空母
时间限制: 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));//for(int i=0; i<2; i++)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);}
}

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