HDU - 4704(费马小定理和快速幂)
程序员文章站
2022-06-08 11:19:26
...
Input
2Output
2
Hint
1. For N = 2, S(1) = S(2) = 1.2. The input file consists of multiple test cases. 2Sample Output
2
代码 :
其实我看不懂是题目是搜索博客的这道题就是x1+x2+x3+···+xn=N,求有几种组合方法。
利用数学方法中的“隔板法”,不难知道结果就是C(n-1)^0+C(n-1)^1+C(n-1)^2+···+C(n-1)^r+···+C(n-1)^(n-1).这是二项式定理的展开式。 根据二项式定理不难得出,结果就是2^(n-1)。所以,这道题就转换为求解2^(n-1)mod(1e9+7)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
char str[100005];
const LL mod=1e9+7;
//快速幂
LL FastPow(LL a,LL b)
{
LL ans=1;
while(b)
{
if(b&1)
ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
//费马小定理
LL FeiMaXiao(char *str)
{
LL ans=0;
for(int i=0;str[i]!='\0';i++)
ans=(ans*10+str[i]-'0')%(mod-1);
return ans;
}
int main()
{
while(scanf("%s",str)!=EOF)
{
LL n = FeiMaXiao(str);
printf("%lld\n",FastPow(2,n-1));
}
return 0;
}