codeforces 185A. Plant（规律）

codeforces 185A. Plant（规律）

codeforces 185A. Plant

​​#include using namespace std;typedef long long LL;const LL mod=1e9+7;struct matrix{ LL m[2][2];};matrix I={1,0,0,1};matrix A={3,1,1,3};matrix multi(matrix a,matrix b){ matrix c; for(int i=0;i<2;i++){ for(int j=0;j<2;j++){ c.m[i][j]=0; for(int k=0;k<2;k++){ c.m[i][j]=c.m[i][j]+a.m[i][k]*b.m[k][j]%mod; } c.m[i][j]%=mod; } } return c;}matrix power(LL p){ matrix ans=I,temp=A; while(p){ if(p&1) ans=multi(ans,temp); temp=multi(temp,temp); p>>=1; } return ans;}int main(){ LL n; while(cin>>n){ matrix ans=power(n); printf("%I64d\n",ans.m[0][0]); } return 0;}

第二种解法：斜着右上方查看每一列的上三角形的数量变化。嘿嘿，规律出现了。

#include #include using namespace std;typedef long long LL;const LL mod=1e9+7;LL power(LL p){ LL ans=1,temp=2; while(p){ if(p&1) ans=ans*temp%mod; temp=temp*temp%mod; p>>=1; } return ans;}int main(){ LL n; while(cin>>n){ if(n==0){ puts("1"); continue; } printf("%I64d\n",(power(2*n-1)+power(n-1))%mod); } return 0;}

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