【hdu4704】 Sum——费马小定理+快速幂取模

题目的大意就是要求把一个数划分为m（1<=m<=n）个数相加之和的方案数（答案取模1e9+7）。

容易想到答案就是sum（C（n-1,i）（0<=i<=n-1）），也就是2^（n-1）（组合数第n行的所有数的和为2^（n-1）)。

既然答案是2^n-1，第一反应应该是快速幂取模。很可惜，这里的n巨大无比，这种做法显然是不现实的。于是我们就需要用到费马小定理啦。

我们知道 a^p-1%p=1，那么我们令n=t*(p-1)+k，即n-1=t*(p-1)+(k-1)。那么2^n-1=2^t*(p-1)* 2^k-1，重点来了！根据同余的性质，2^t*(p-1)%p=1。也就是说我们只需要求出2^k-1%p的值，这个值就是最后的答案，变形到这里，求出k的值就可以用快速幂了。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 const int mod=1e9+7;
 5 typedef long long LL;
 6 using namespace std;
 7 char ch[1000005];
 8 int len;
 9 LL kuai(int aa,LL b)
10 {
11     LL res=1;LL a=aa;
12     while(b){
13         if(b&1)res=res*a%mod;
14         a=a*a%mod;
15         b>>=1;
16     }
17     return res;
18 }
19 LL fei(int p)
20 {
21     LL ans=0;
22     for(int i=1;i<=len;i++)
23         ans=(ans*10+ch[i]-48)%p;
24     return ans;
25 }
26 int main()
27 {
28     while(~scanf("%s",ch+1)){
29         len=strlen(ch+1);
30         LL k=fei(mod-1);
31         LL an=kuai(2,k-1);
32         printf("%lld
",an);
33     }
34     return 0;
35 }

hdu4704