hdoj 4704 Sum

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4704

解题思路：容易求得 S(1)+S(2)+···+S(N)=2^N-1 , 则 (S(1)+S(2)+···+S(N))%1000000007=2^N-1%1000000007.

记 Mod=1000000007, 由 Euler-Fermat 定理有：2^Mod-1≡1 (mod Mod), 从而有 2^N-1≡2^{(N-1) mod (Mod-1)} (mod Mod).

 1 ///////////////////////////////////////////////////////////////////////////
 2 //problem_id: hdoj 4704
 3 //user_id: SCNU20102200088
 4 ///////////////////////////////////////////////////////////////////////////
 5 
 6 #include <algorithm>
 7 #include <iostream>
 8 #include <iterator>
 9 #include <iomanip>
10 #include <cstring>
11 #include <cstdlib>
12 #include <string>
13 #include <vector>
14 #include <cstdio>
15 #include <cctype>
16 #include <cmath>
17 #include <queue>
18 #include <stack>
19 #include <list>
20 #include <set>
21 #include <map>
22 using namespace std;
23 
24 ///////////////////////////////////////////////////////////////////////////
25 typedef long long LL;
26 const double PI=acos(-1.0);
27 
28 const int x4[]={-1,0,1,0};
29 const int y4[]={0,1,0,-1};
30 const int x8[]={-1,-1,0,1,1,1,0,-1};
31 const int y8[]={0,1,1,1,0,-1,-1,-1};
32 
33 typedef int T;
34 T max(T a,T b){ return a>b? a:b; }
35 T min(T a,T b){ return a<b? a:b; }
36 ///////////////////////////////////////////////////////////////////////////
37 
38 ///////////////////////////////////////////////////////////////////////////
39 //Add Code:
40 const LL Mod=1000000007;
41 ///////////////////////////////////////////////////////////////////////////
42 
43 int main(){
44     ///////////////////////////////////////////////////////////////////////
45     //Add code:
46     char c;
47     while((c=getchar())!=EOF){
48         LL ans=1,a=2,n=c-'0';
49         while((c=getchar())!='
') n=(n*10+c-'0')%(Mod-1);
50         if(n==0) n=Mod-1;
51         n--;
52         while(n){
53             if(n&1) ans=ans*a%Mod;
54             a=a*a%Mod;
55             n>>=1;
56         }
57         printf("%I64d
",ans);
58     }
59     ///////////////////////////////////////////////////////////////////////
60     return 0;
61 }
62 
63 ///////////////////////////////////////////////////////////////////////////
64 /*
65 Testcase:
66 Input:
67 2
68 Output:
69 2
70 */
71 ///////////////////////////////////////////////////////////////////////////