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

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4704

题意：

给定一个数n 将其分解，Si 表示将n拆成i个数的方案数

求sum( si ) 1<=i<=n;

分析：

隔板原理， n个木棍，n-1个缝，

分成1份则是C(n-1,0);

分成2份则是C(n-1,1);

分成3份则是C(n-1,2);

...

分成n份则是C(n-1,n-1);

ans = sum( C(n-1,i) ) (0<=i<=n-1)

=2^(n-1);

由于要取模 而且 2 与 mod 互质 ，因此可以用费马小定理来降幂

代码如下：

#include 
  
   
#include 
   
     #include 
    
      using namespace std; typedef long long LL; const int mod = 1e9+7; const int maxn = 1e5+10; char a[maxn]; LL quick_mod(LL a,LL b,LL m) { LL ans = 1; while(b){ if(b&1){ ans = ans * a % m; b--; } b>>=1; a = a * a % m; } return ans ; } LL change(char *s, LL m ) { LL ans = 0; int len = strlen(s); for(int i = 0; i < len; i++){ ans = (ans * 10 + a[i] - '0')%m; } return ans ; } int main() { while(~scanf("%s",a)){ int m = mod - 1; LL n = change(a,m); printf("%I64d\n",quick_mod(2,(n-1+m)%m,mod)); } return 0; }