51Nod - 

求：3^0 + 3^1 +...+ 3^(N) mod 1000000007

 

Input

输入一个数N(0 <= N <= 10^9)

Output

输出：计算结果

Input示例

3

Output示例

40

 

题解：

　　这道题的解体方法很多。

　　有公式法，直接利用等比数列求和公式（用long long类型保存才行。） 

　　有快速迭代幂算法。本题解就是采用较笨的方法。 

 

 

 

#include 
     
       #include 
      
        using namespace std;const int MOD = 1e9 + 7; vector
       
        
          > multiple(const vector
         
          
            >& a, const vector
           
            
              >& b){ vector
             
              
                > ans(a.size(), vector
               
                (b[0].size(), 0) ); for(int i=0; i
                
                  > Pow(vector
                 
                  
                    > M, int p){ vector
                   
                    
                      > ans = M; p--; while(p > 0){ if(p%2 == 1){ ans = multiple(ans, M); } M = multiple(M, M); p = p/2; } return ans; }int main(){// freopen("in.txt", "r", stdin); int N, ans; vector
                     
                      
                        > t(2, vector
                       
                        (2, 0)); t[0][0] = 3; t[0][1] = 1; t[1][0] = 0; t[1][1] = 1; while(scanf("%d", &N) != EOF){ if(N <= 0){ ans = 1; }else{ vector
                        
                         
                           > tg = Pow(t, N); ans = int((tg[0][0]*1 + tg[0][1]*1) % MOD); } printf("%d\n", ans ); } return 0; }