【ACM】杭电OJ 4704 Sum （隔板原理+组合数求和公式+费马小定理+快速幂）

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

1.隔板原理

1~N有N个元素，每个元素代表一个1.分成K个数，即在(N-1)个空挡里放置（K-1）块隔板

即求组合数C(N-1,0)+C(N-1,1)+...+C(N-1，N-1)

2.组合数求和公式

C(n,0)+C(n,1)+C(n,2)+.+C(n,n)=2^n

3.费马小定理（降幂）

因为N很大，所以需要费马小定理来降幂

费马小定理是假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。

所以可以把（n-1）对(MOD-1)取余 设余数为K 因为2^（MOD-1）%MOD =1

题目即求2^K %MOD

4.快速幂求解

现在K<=MOD，快速幂的复杂度是O(log₂N)，直接套模板就行

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;
const ll mod = 1000000007;

ll quick_mod(ll a,ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b&1)
        {
            ans = (ans*a)%mod;
            --b;
        }
        a = (a*a)%mod;
        b >>= 1;
    }
    return ans;
}


int main ()
{
    char s[100050];
    while(scanf("%s",s)!=EOF)
    {
        if(s[0]=='\0')
            break;
        ll i,ans = 0;
        for(i=0;s[i];i++)
        {
            ans = (ans*10+s[i]-'0')%(mod-1);
        }
        printf("%lld\n",quick_mod(2,ans-1));
    }
    return 0;
}

同余定理的 简单 应用：LightOJ 1078，HDU 2674，HDU 1212，HDU 2817