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;
}