codeforces #185 A Plant（矩阵快速幂+递推） - c++编程基础

TOP

codeforces #185 A Plant（矩阵快速幂+递推）

2015-07-20 17:39:33 来源: 作者: 【大中小】浏览:3次

Tags：codeforces #185 Plant 矩阵快速递推

通过这个题终于找回了点找递推公式的信心。。TAT。。

不过真心感觉CF的题目质量都真不错。。。

首先，第n个图形的上方，左下方，右下方的三个大三角形是跟第n-1个是一模一样的，所以是3*f(n-1)。

然后只剩下中间一个倒着的大三角形了，这时可以注意到，其实也跟第n-1个一模一样，只不过上下颠倒过来了，那这里的正着的三角形数就相当于是原来的倒三角形数。

而原来的倒着的三角形数可以用总的减去f(n-1)。而总的是1+2+3+...+2*(n-1)==4^(n-1)。再设g(n)，让g(n)=4^(n-1).

那么就把问题转换成了构造一个矩阵A使得

f(n-1) f(n)

A * { } = { };

g(n-1) g(n)

这个矩阵A很容易构造出来。

2,1

0,4

然后用矩阵快速幂求出来即可。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              using namespace std; #define LL __int64 const int mod=1e9+7; struct matrix { LL ma[3][3]; }init, res; matrix Mult(matrix x, matrix y) { matrix tmp; int i, j, k; for(i=0;i<2;i++) { for(j=0;j<2;j++) { tmp.ma[i][j]=0; for(k=0;k<2;k++) { tmp.ma[i][j]=(tmp.ma[i][j]+x.ma[i][k]*y.ma[k][j])%mod; } } } return tmp; } matrix Pow(matrix x, LL k) { matrix tmp; int i, j; for(i=0;i<2;i++) for(j=0;j<2;j++) tmp.ma[i][j]=(i==j); while(k) { if(k&1) tmp=Mult(tmp,x); x=Mult(x,x); k>>=1; } return tmp; } int main() { int i, j; LL k; while(scanf(%I64d,&k)!=EOF) { init.ma[0][0]=2; init.ma[0][1]=1; init.ma[1][0]=0; init.ma[1][1]=4; res=Pow(init,k); LL ans=(res.ma[0][0]+res.ma[0][1])%mod; printf(%I64d ,ans); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：在栈中分配内存的方法 alloca 例子	下一篇：Utility Classes Are Evil

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: