hdu 4704 Sum 【费马小定理】

题目

hdu 4704  Sum 【费马小定理】

题意:将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;
}
上一篇:Delphi XE5 for Android (三)


下一篇:【原】SDWebImage源码阅读(五)