注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-2875: [Noi2012]随机数生成器(矩阵快速幂)  

2014-01-25 19:28:00|  分类: oi,bzoj,矩阵乘法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2875

之前一直以为是神马数论的神题没敢下手,今天除草的时候才突然发现就一裸的矩阵乘法,然后用快速幂解决就没有啦。

对于该递推式,最终改写成一下矩阵形式,然后快速幂,还有个小细节,两个10^18乘起来会爆long long,所以改写成加法的形式,然后类快速幂优化即可。

BZOJ-2875: [Noi2012]随机数生成器(矩阵快速幂) - cjjlsdy - cjjlsdy的博客

代码:

  • #include <iostream>
  • #include <algorithm>
  • #include <cstring>
  •  
  • using namespace std ;
  •  
  • #define ll long long
  •  
  • ll m , a , c , n , g , x ;
  •  
  • ll multi( ll y , ll cnt ) {
  •             if ( ! cnt ) return 0 ;
  •             if ( cnt == 1 ) return y % m ;
  •             ll rec = multi( y , cnt / 2 ) ;
  •             rec = ( rec + rec ) % m ;
  •             if ( cnt % 2 ) rec = ( rec + y ) % m ;
  •             return rec ;
  • }
  •  
  • struct maxtrix {
  •             ll a[ 2 ][ 2 ] ;
  •             maxtrix(  ) {
  •                         memset( a , 0 , sizeof( a ) ) ;
  •             }
  •             void print(  ) {
  •                         for ( int i = 0 ; i < 2 ; i ++ ) {
  •                                      for ( int j = 0 ; j < 2 ; j ++ ) {
  •                                                  cout << a[ i ][ j ] << " " ;
  •                                      }
  •                                      cout << endl ;
  •                         }
  •             }
  • };
  •  
  • maxtrix Multi( maxtrix m1 , maxtrix m2 ) {
  •             maxtrix rec ;
  •             for ( int i = 0 ; i < 2 ; i ++ ) {
  •                         for ( int j = 0 ; j < 2 ; j ++ ) {
  •                                      for ( int k = 0 ; k < 2 ; k ++ ) {
  •                                                  rec.a[ i ][ j ] += multi( m1.a[ i ][ k ] , m2.a[ k ][ j ] ) ;
  •                                                  rec.a[ i ][ j ] %= m ;
  •                                      }
  •                         }
  •             }
  •             return rec ;
  • }
  •  
  • maxtrix Pow( maxtrix x , ll cnt ) {
  •             if ( cnt == 1 ) return x ;
  •             maxtrix rec = Pow( x , cnt / 2 ) ;
  •             rec = Multi( rec , rec ) ;
  •             if ( cnt % 2 ) rec = Multi( rec , x ) ;
  •             return rec ;
  • }
  •  
  • int main(  ) {
  •             cin >> m >> a >> c >> x >> n >> g ;
  •             maxtrix m1 , m2 ;
  •             m2.a[ 0 ][ 0 ] = a , m2.a[ 0 ][ 1 ] = 0 , m2.a[ 1 ][ 0 ] = c , m2.a[ 1 ][ 1 ] = 1 ;
  •             m1.a[ 0 ][ 0 ] = x , m1.a[ 0 ][ 1 ] = 1 ;
  •             maxtrix ans = Multi( m1 , Pow( m2 , n ) ) ;
  •             cout << ans.a[ 0 ][ 0 ] % g << endl ;
  •             return 0 ;
  • }



  评论这张
 
阅读(3)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018