题目描述：
给定一个整数N，有一个函数S(x)，S(x)表示把整数N分成x份有多少个方法。
求S(1)+S(2)+......+S(N)的和。
分析：可以把N看出N个小球（把N看出N个1的和），放入x个洞里面，有多少种方法。由插板法可以得到S(x)=C(x-1,n-1)。（x-1在上，N-1在下）。
那么和就是sum=S(1)+S(2)+......+S(N)=C(0,N-1)+C(1,N-1)+......+C(N-1,N-1)=2^(N-1)。答案就是求2^(N-1)。
因为N很大，只能用字符串存起来。首先把字符串代表的数减一，直接把最后的数减1即可。如果遇到最后的数为0，那么就要把这个数变为9，把前面的数减一。比如（10-1变成09）。
我的想法就是把字符串拆成一位一位的。比如求2^(22)可以拆成2^(20) * 2^(2)。2^(2)很简单，把他的基数2平方即可。那2^(20)呢，同样，把基数变成2^(10)，再把基数平方即可。这样每一位的基数，是他前一位的10次方，每次保留基数，就可以一步一步求。再用快速幂运算即可。
代码：
#include <iostream> #include <algorithm> #include <cstdio> #include <string.h> using namespace std; typedef long long ll; const ll mod=1000000007; ll pow(ll x,int n) { if(n==0) return 1; if(n==1) return x%mod; ll res=1; while(n) { if(n&1) res=res*x%mod; x=x*x%mod; n>>=1; } return res; } int main() { char N[2000006]; while(scanf("%s",N)!=EOF) { int len=strlen(N); ll base=2; ll ans=1; int tail=len-1; while(N[tail]==‘0‘) { N[tail]=‘9‘; tail--; } N[tail]--; for(int i=len-1;i>=0;i--) { int num=N[i]-‘0‘; ans=ans*pow(base,num)%mod; base=pow(base,10); } printf("%lld\n",ans%mod); } return 0; }
原文：https://www.cnblogs.com/studyshare777/p/12245229.html