题目

题意：将N拆分成1-n个数，问有多少种组成方法。

例如：N=4，将N拆分成1个数，结果就是4；将N拆分成2个数，结果就是3（即：1+3,2+2,3+1）……1+3和3+1这个算两个，则这个就是组合数问题。

根据隔板定理，把N分成一份的分法数为C(1,n-1)，

把N分成两份的分法数为C(2,n-1)，

把N分成三份的分法数为C(3,n-1)，.... ，

把N分成N份的分法数为C(n-1,n-1)。

即我们要求的结果为: 2^(n-1）% mod  但是 [  1<=n<1e5,  mod=1e9+7  ]

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long LL;

const LL mod = 1e9+7;

LL pow(LL a,LL b)

{

    LL res = 1,base = a;

    while(b!=0){

        if(b&1) res = res*base %mod;

        base = base * base%mod;

        b>>=1;

    }

    return res;

}

int main()

{

    LL num=0,ans;

    string str;

    while(cin>>str){

            num = 0;

        for(LL i=0;i<str.size();i++){

            num=(num*10 + str[i]-'0') % (mod-1);

        }

        ans = pow(2,num-1);

        cout<<ans%mod<<endl;

        str.clear();

    }

    return 0;

}