首页 > 代码库 > AC日记——3的幂的和 51nod 1013
AC日记——3的幂的和 51nod 1013
3的幂的和
思路;
矩阵快速幂;
sn-1 3 1 sn
* =
1 0 1 1
来,上代码:
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define mod 1000000007struct NodeType { long long a[3][3];};struct NodeType ans;long long n;struct NodeType mul(NodeType pos){ NodeType res; res.a[1][1]=0,res.a[1][2]=0; res.a[2][1]=0,res.a[2][2]=0; for(int i=1;i<=2;i++) { for(int j=1;j<=2;j++) { for(int v=1;v<=2;v++) { res.a[i][j]=(res.a[i][j]+(pos.a[i][v]*pos.a[v][j])%mod)%mod; } } } return res;}void poww(int mi){ NodeType pos; pos.a[1][1]=3,pos.a[1][2]=1; pos.a[2][1]=0,pos.a[2][2]=1; while(mi>0) { struct NodeType res; res.a[1][1]=0,res.a[1][2]=0; res.a[2][1]=0,res.a[2][2]=0; if(mi&1) { for(int i=1;i<=2;i++) { for(int j=1;j<=2;j++) { for(int v=1;v<=2;v++) { res.a[i][j]=(res.a[i][j]+(ans.a[i][v]*pos.a[v][j])%mod)%mod; } } } ans=res; } pos=mul(pos),mi=mi>>1; }}int main(){ scanf("%lld",&n);n--; ans.a[1][1]=3,ans.a[1][2]=1; ans.a[2][1]=0,ans.a[2][2]=1; poww(n); cout<<(ans.a[1][1]+ans.a[1][2])%mod; return 0;}
AC日记——3的幂的和 51nod 1013
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。