CodeForces Round #118 (185A) - Plant

CodeForces Round #118 (185A) - Plant

这次比赛的时间是23:30开始...囧...写了一道A题就回去睡觉了..这场比赛有三道题A的人很多..本题就是一个很典型的找递推式..用矩阵乘法求解...

另  N [ k ] [ 0 ] 表示第 k 时间向上三角形个数... N [ k ] [ 1 ] 表示 k 时间向下三角形个数...那么易得:

N [ k ] [ 0 ] = N [ k-1 ] [ 0 ] * 3 + N [ k - 1 ] [ 1 ]

N [ k ] [ 1 ] = N [ k-1 ] [ 1 ] * 3 + N [ k - 1 ] [ 0 ]

由于k很大..只能用矩阵乘法求解..构造矩阵:

h=   [     3        1

1        3     ]

初始值为  A={ 1 , 0 }

那么要求第k天的情况:   A*h^k  即可....

Program:

#include#include#include#include#include#include#define oo 2000000000#define ll long longusing namespace std; struct node{ ll s[2][2];}_2jie[70],temp;ll n;node matrix_mul(node a,node b){ int k,i,j; memset(temp.s,0,sizeof(temp.s)); for (k=0;k<2;k++) for (i=0;i<2;i++) for (j=0;j<2;j++) temp.s[i][j]=(temp.s[i][j]+a.s[i][k]*b.s[k][j])%1000000007; return temp;}node getanswer(node h,ll l){ ll k,i; node ans; _2jie[1]=h; k=2; for (i=2;i<63;i++) { _2jie[i]=matrix_mul(_2jie[i-1],_2jie[i-1]); k*=2; } ans.s[0][0]=1; ans.s[0][1]=0; ans.s[1][0]=0; ans.s[1][1]=1; while (l) { while (k>l) { i--; k/=2; } ans=matrix_mul(ans,_2jie[i]); l-=k; } return ans;}int main(){ scanf("%I64d",&n); node h; h.s[0][0]=3; h.s[0][1]=1; h.s[1][0]=1; h.s[1][1]=3; h=getanswer(h,n); printf("%I64d\n",h.s[0][0]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。