题目传送：http://acm.hdu.edu.cn/showproblem.php?pid=4704
Problem Description
Sample Input
2
Sample Output
2
Hint
1. For N = 2, S(1) = S(2) = 1.
2. The input file consists of multiple test cases.
题意是输入一个N,求N被分成1个数的结果+被分成2个数的结果+...+被分成N个数的结果，N很大
1.隔板原理
1~N有N个元素，每个元素代表一个1.分成K个数，即在(N-1)个空挡里放置（K-1）块隔板
即求组合数C(N-1,0)+C(N-1,1)+...+C(N-1，N-1)
2.组合数求和公式
C(n,0)+C(n,1)+C(n,2)+.+C(n,n)=2^n
证明如下：
利用二项式定理（a+b)^n=C(n,0)a^n+C(n,1)a^(n-1)b+C(n,2)a^(n-2)b^2 +.+C(n,n)b^n
令a=b=1左边就是2^n
令a=b=1左边就是2^n
所以题目即求2^（n-1）%（1e9+7）
设MOD为1e9+7
3.费马小定理（降幂）
因为N很大，所以需要费马小定理来降幂
费马小定理是假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。
所以可以把（n-1）对(MOD-1)取余 设余数为K 因为2^（MOD-1）%MOD =1
题目即求2^K %MOD
4.快速幂求解
现在K<=MOD，快速幂的复杂度是O(log₂N)，直接套模板就行
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string.h>
using namespace std; #define MOD 1000000007 long long quick_mod(long long a,long long b,long long m)//快速幂，复杂度log2n
{
long long ans=;
while(b)
{
if(b&)
{
ans=(ans*a)%m;
b--;
}
b/=;
a=a*a%m;
}
return ans;
} int main()
{ char str[];
long long sum;
int len,i;
long long M=MOD-;
while(scanf("%s",str)!=EOF)
{
len=strlen(str);
sum=;
for(i=;i<len;i++)
{
sum=sum*+(str[i]-'');
sum=sum%M;//费马小定理
}
printf("%lld\n",quick_mod(,(sum-),MOD));//快速幂
}
return ;
}