Sum
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 131072/131072K (Java/Other)
Total Submission(s) : 78 Accepted Submission(s) : 30
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
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.
Source
2013 Multi-University Training Contest 10
题解：
S(k)表示把N分成k个整数和的分法数，此题要求解的是(S(1)+S(2)+...+S(N))mod(10^9+7)的值。
题目分析：
根据隔板定理，把N分成一份的分法数为C(1,n-1)，
把N分成两份的分法数为C(2,n-1)，
把N分成三份的分法数为C(3,n-1)，.... ，
把N分成N份的分法数为C(n-1,n-1)。
设sum=S(1)+S(2)+...+S(N)，根据组合数求和公式，sum=2^(n-1)。所以，原式可化为(2^(N-1))mod(10^9+7)
由于N的值比较大，第一步想到的就是要用字符数组来对其进行处理，且由于N比较大，且2和MOD互素，所以要借助于费马小定理求解，2^(MOD-1)modMOD==1，即要看(N-1)中有有多少个(MOD-1)，则(N-1)%(MOD-1)的值再对MOD进行快速幂求解即可。
错误点：10^100000直接以为这个数字只有100000，其实是有100000位的数字，这道题还有需要n-1，这个在之前就剪掉或是最后减掉，答案不变。
//#include <iostream>
#include<bits/stdc++.h>
using namespace std; char ch[];
long long sum;
const int mod=1e9+; long long work(int k)
{
long long res=;
long long a=;
while(k)
{
if (k&) res=(res*a)%mod;
a=a*a%mod;
k>>=;
}
return res%mod;
}
int main()
{
while(~scanf("%s",&ch))
{
int l=strlen(ch);
sum=;
for(int i=;i<l;i++)
{
sum=sum*+ch[i]-'';
sum=sum%(mod-);
}
printf("%lld\n",work(sum-));
}
return ;
}