线段树

2019-11-08 02:34:10

字体：大中小

来源：转载

供稿：网友

#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <iomanip> #include <cmath> typedef long long ll; using namespace std; struct jz { ll node[2][2]; }ans,mid; ll n,t,mod; jz cheng(jz a,jz b) { jz temp; for(int i=0;i<2;i++) { for(int j=0;j<2;j++) { temp.node[i][j]=0; for(int k=0;k<2;k++) { temp.node[i][j]=(temp.node[i][j]+a.node[i][k]*b.node[k][j])%mod; } } } return temp; } void csh() { ans.node[0][0]=ans.node[1][1]=1; ans.node[0][1]=ans.node[1][0]=0; mid.node[0][0]=mid.node[0][1]=mid.node[1][0]=1; mid.node[1][1]=0; } inline ll pw(ll b) { csh(); while(b>0) { if(b&1)ans=cheng(ans,mid); mid=cheng(mid,mid); b>>=1; } return ans.node[0][1]; } int main() { scanf("%lld",&t); for(int i=1;i<=t;i++) { scanf("%lld %lld",&n,&mod); PRintf("%lld/n",pw(n)); } return 0; } /*inline void cot(int x,int y,bool z){ if(x){ fa[x]=y; } if(y){ son[y][z]=x; }}inline void rot(int x,bool z){ int xx=fa[x],xxx=fa[xx]; cot(son[x][z],xx,z^1); cot(x,xxx,son[xxx][1]==xx); cot(xx,x,z);}void splay(int x,int y){ int xx=fa[x],xxx=fa[xx]; while(xx!=y){ if(xxx==y){ rot(x,son[xx][0]==x); }else{ bool z=son[xxx][0]==xx; if(son[xx][z]==x){ rot(x,z^1); rot(x,z); }else{ rot(xx,z); rot(x,z); } } xx=fa[x],xxx=fa[xx]; } if(!y){ rt=x; }}*/

上一篇：Table和ViewPager混合使用小结

下一篇：PAT 1021 个位数统计