本文主要是介绍【HDU】4990 Reading comprehension 等比数列：两层快速幂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【HDU】4990 Reading comprehension
题目分析：首先根据题目意思可以很容易找到一个等比数列：
当n%2==1时，f(n) = 1 + 2^2 + 2^4 + ... + 2^(n-1)
当n%2==0时，f(n) = 2*f(n-1)。
接下来可以构造矩阵用矩阵快速幂求，也可以像我一样用两层快速幂求。（比赛的时候没想到用矩阵快速幂= =）
当n%2==1时
如果(n/2)%2==1：f(n) = ( 2 ^ ( n/2 + 1 ) + 1 ) * f( n/2 - 1 )
如果(n/2)%2==0：f(n) = 2^n + ( 2 ^ (n/2) + 1 ) * f( n/2 - 2 )
递归求解，边界条件是n==0时返回1
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;#define REP( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i )
#define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define REV( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )typedef long long LL ;int n , m ;LL pow ( int a , int b ) {LL res = 1 , tmp = a ;while ( b ) {if ( b & 1 ) res = res * tmp % m ;tmp = tmp * tmp % m ;b >>= 1 ;}return res ;
}LL pow2 ( int n ) {if ( n == 0 ) return 1 ;int nn = n / 2 ;if ( nn & 1 ) return ( pow ( 2 , nn + 1 ) + 1 ) * pow2 ( nn - 1 ) % m ;return ( pow ( 2 , n ) + ( pow ( 2 , nn ) + 1 ) * pow2 ( nn - 2 ) ) % m ;
}void solve () {int ans ;if ( n & 1 ) ans = pow2 ( n - 1 ) % m ;else ans = 2 * pow2 ( n - 2 ) % m ;printf ( "%d\n" , ans ) ;
}int main () {while ( ~scanf ( "%d%d" , &n , &m ) ) solve () ;return 0 ;
}这篇关于【HDU】4990 Reading comprehension 等比数列：两层快速幂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
