题解 P3414 【SAC#1 - 组合数】

组合数知识就不多讲了，因为作者是初一萌新，对组合数也很懵懂。

这题是快速幂求2的n-1次方，因为i取0到n所有偶数（组合数知识），试问谁不知道用快速幂（好吧在经历血的教训前（看下面）窝也不知道）。

血的教训

快速幂使O(n)的复杂度变为O(log n)，快了很多。

快速幂的思想：

以求2^4为例，2^4=2^2*2^2,以此类推，逐步分解。

但有人要问了，指数是奇数的时候怎么办办呢？

例如2^5,我们可以把它分解为2*2^4,从而将其转化为刚才的求2^4。

以此类推。

本蒟蒻用了递归实现快速幂，如果您看了作者详（xuan）细（xue）的讲解后还是不懂，可以看这里，代码中有详细注释。

代码

#include <cstdio> 
long long ans=2,n;
const int M=6662333;
typedef long long ll;//懒人用
ll FP(ll m)//FP:fast power（快速幂）
{
    if(m == 0) return 1;//任何数的0次方都是1
    if(m%2 == 1) return 2*FP(m-1)%M;//指数是奇数的情况
        //指数是偶数的情况
    ll num=FP(m/2)%M;//使代码更简洁
    return (num%M)*(num%M)%M;
}
int main()
{
    //读入输出不再多说
    scanf("%lld",&n);
    printf("%lld",FP(n-1)%M);
    return 0;
}

作者NOI online爆0了，求安慰（赞），管理员大大就让他过了吧！