ZOJ 3690 Choosing number（矩阵快速幂） - c++编程基础

TOP

ZOJ 3690 Choosing number（矩阵快速幂）

2015-07-20 17:36:03 来源: 作者: 【大中小】浏览:2次

题目地址：ZOJ 3690

假设F(n)表示前n个人第n个人选择的数大于k的个数，G(n)表示的是前n个人第n个人选择的数小于等于k的个数
那么F(n) = F(n-1)*(m-k)+G(n-1)*(m-k) , G(n) = F(n-1)*k+G(n-1)*(k-1) , 那么最后的结果就是F(n)+G(n);
那么我们可以构造出矩阵
| m-k m-k| | F(n-1) | | F(n) |
| k k-1| * | G(n-1) | => | G(n) |
那么初始值F(1) = m-k , G(1) = k

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; #define LL long long using namespace std; const LL mod=1e9+7; struct matrix { LL ma[3][3]; }init,res; matrix Mult(matrix x, matrix y) { matrix tmp; for(int i=0;i<2;i++) { for(int j=0;j<2;j++) { tmp.ma[i][j]=0; for(int 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, int 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 n, m, k, i, j; LL ans; while(scanf("%d%d%d",&n,&m,&k)!=EOF) { init.ma[0][0]=m-k; init.ma[0][1]=m-k; init.ma[1][0]=k; init.ma[1][1]=k-1; res=Pow(init,n-1); ans=((m-k)*res.ma[0][0]+k*res.ma[0][1]+(m-k)*res.ma[1][0]+k*res.ma[1][1])%mod; printf("%d\n",ans); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：C++ Singleton	下一篇：HDU - 5053 the Sum of Cube

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: