For N = 2, S(1) = S(2) = 1.
The input file consists of multiple test cases.
2013 Multi-University Training Contest 10
题意：把一个数n拆分为1数的方法是S[1]，拆分为2个数的方法s[2]，拆分为n个数的方法s[n],求sum（s[1],s[2],…,s[n]）;其实就相当于把n个数拆分为n个1，中间有n-1个空位，然在这些空位中放隔板，放0,1,2,3,…,n个隔板的情况就是c（n-1，1）+c（n-1，1）+c（n-1，2）+c（n-1，3），由组合数的公式就可以算出该组合数的和sum=2^n-1（这里应该是高中的知识，不懂得去看二项式定理）; 例如：n=4； s[1] 1 1 1 1 s[2] 2 2 1 3 3 1 s[3] 1 2 1 1 1 2 2 1 1 s[4] 4 由于在这里n特别大，不能直接读入，所以要用字符串，mod和2都是素数，他们互质，所以可以用费马小定理降幂（也可以说是欧拉降幂） #include <iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<vector> #include<queue> #include<string> #define mod 1000000007 using namespace std; typedef long long ll; const int maxn=1000005; const int inf=0x3f3f3f3f; ll quick_pow(ll n,ll k){ ll as=1; while(k){ if(1&k) as=as*n%mod; n=n*n%mod; k>>=1; } return as; } int main() { char s[maxn]; while(~scanf("%s",s)){ int len=strlen(s); ll ans=0; for(int i=0;i<len;i++){ ans=ans*10+s[i]-'0'; ans%=mod-1; } printf("%lld\n",quick_pow(2,ans-1)); } return 0; }