题解 P3414 SAC#1 - 组合数

· · 个人记录

更好的阅读体验

一道有趣轻松的组合数的题目，其实如果熟悉组合数的话可以简单的解决，这里主要是给出几种不同的思路以及这道题在做法上的优化。

一、基本yy法

本法适用于找规律能力好但是证明无力的初级选手，同时也是考场上的必备技能。

首先我们对于每一个输入的n，都让答案为ans[n]，可以对于较小的n找到这样的对应关系:

ans[1]=1 \ ,\ ans[2] = \ 2,\ ans[3] = \ 4,\ ans[4] = \ 8,\ ans[5] = \ 16

不难看出来本题的规律是:

ans = 2^{n-1}

二、杨辉三角法

圈圈圈出来的就是 C(n,i) 的偶数项。我们知道杨辉三角每行之和都等于 2^{n} 。

所以对于n为奇数的情况，因为杨辉三角的对称性我们可以轻松的发现偶数项之和为该行的一半，即 ans = 2^{n-1} 。

那么n为偶数怎么办呢？我们发现每一个非1偶数项都对应上一行的两个数，左右两个1则对应上一行的左右两个1，用图表示更加直接:

所以对于n为偶数的情况，可以发现 ans = 上一行所有元素之和 = 2^{n-1}

合并一下，同样得到了一方法的结论，这也是我用的证明方法，虽然不怎么方便，但是作为思考还是不错的。 并不

三、二项式定理

简单介绍一下:

通过展开 (1+1)^{n} 和 (1-1)^{n} ,不难发现:

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

两式相加有

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

故证明 C(n,i) 的所有偶数 i 项之和等于 2^{n-1}

接下来是代码 Time ：

#include  <cstdio>
#include <iostream>
#define ll long long
using namespace std;
char s[10000];
ll p=6662333;
inline ll process(){
    int n=0;
    for(int i=1;s[i];++i){
        n*=10;n+=s[i]-'0';n%=(p-1);
    }
    return n;
}
inline ll fpow(ll a,ll k){
    ll ans=1;
    while(k){
        if(k&1) ans*=a,ans%=p;
        k>>=1;a*=a;a%=p;
    }
    return ans;
}
int main(){
    scanf("%s",s+1);
    ll k=(process()+p-2)%(p-1);
    printf("%lld",fpow(2,k));
    return 0;
}

这里我用了欧拉定理来进行优化，因为6662333是个质数，所以φ( 6662333 ) = 6662332 ,得到:

2^{6662332} \ mod \ 6662333 = 1

所以输入的时候可以直接模6662332，这样对于更大的n，也可以瞬间出答案哟。