2019年第二阶段我要变强个人训练赛第十八场 O 大凤号装甲空母

题目描述
大凤号航空母舰很喜欢算术。
它，是旧日本海军中最为先进的航空母舰。
它，是旧日本海军中最为短命的航空母舰。
同时，她还是最平的航空母舰（龙骧：你说啥？）
如此多第一 ……
一生二，二生三，三生万物 ……
这也许就是大凤喜欢算术的原因吧。
有一天，她看到了这样一道题：
令
电探发现了来自远处的鱼雷，时间不多了。

输入
一行由空格隔开的两个非负整数，分别是n和p。

输出
一行表示答案。

sample input
5 97
sample output
11

分析：
本来想暴力来着，但是浮点数有点伤，没办法快速幂，但是打一个表会发现一些规律

是不是有点像斐波那契数列，那么这样的话不就可以去考虑矩阵快速幂了（不知道为啥的可以看看这）
但是这不适合之间套矩阵快速幂，需要构造一个构造出类似斐波那契数列通向的数列，大家看 1 2 3 4 6 11……这个不是在奇数位置开始加1 的吗，那么就在2这个偶数位置再+1，那么这个序列不就是
1 3 4 7 11……这样就满足f[n]=f[n-1]+f[n-2]这个性质的数列了
是不是在最后答案的时候看看是不是偶数，如果是偶数就将快速幂得到的答案减一

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef long long ll;
using namespace std;
ll mod,n;
struct node{ll m[10][10];int row,col;
};
node muti_mat(node A,node B,int r1,int r2,int c2){node c;
//    int r1=A.row,r2=B.row,c2=B.col;for(int i=1;i<=r1;i++)for(int j=1;j<=c2;j++)c.m[i][j]=0;for(int i=1;i<=r1;i++){for(int j=1;j<=c2;j++){for(int k=1;k<=r2;k++){c.m[i][j]=(c.m[i][j]+A.m[i][k]*B.m[k][j])%mod;}}}return c;
}
node e,base,ans;
void epow_mat(ll n){for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)if(i==2 && j==2)e.m[i][j]=0;elsee.m[i][j]=1;e.row=e.col=2;ans.row=ans.col=2;ans.m[1][1]=ans.m[2][2]=1;while(n){if(n&1)ans=muti_mat(ans,e,2,2,2);n/=2;e=muti_mat(e,e,2,2,2);}base.row=2;base.col=1;base.m[1][1]=3;base.m[2][1]=1;ans.row=ans.col=2;ans=muti_mat(ans,base,2,2,1);
}
int main()
{#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endif // ONLINE_JUDGEscanf("%lld%lld",&n,&mod);if(n==0){printf("%lld\n",(ll)1%mod);return 0;}if(n<=2){if(n==1)printf("%lld\n",(ll)1%mod);elseprintf("%lld\n",(ll)2%mod);return 0;}epow_mat(n-2);if(n%2==0)ans.m[1][1]=(ans.m[1][1]-1)%mod;printf("%lld\n",ans.m[1][1]);return 0;
}

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