HDU 4704 Sum (隔板原理 + 费马小定理)

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

Sample Output

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[100005];
long long sum;
const int mod=1e9+7;

long long work(int k)
{
    long long res=1;
    long long a=2;
    while(k)
    {
        if (k&1) res=(res*a)%mod;
        a=a*a%mod;
        k>>=1;
    }
    return res%mod;
}
int main()
{
    while(~scanf("%s",&ch))
    {
        int l=strlen(ch);
        sum=0;
        for(int i=0;i<l;i++)
        {
            sum=sum*10+ch[i]-'0';
            sum=sum%(mod-1);
        }
        printf("%lld
",work(sum-1));
    }
    return 0;
}