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

· · 题解

这道题的答案是2^{n-1}\ mod\ 6662333，各大题解中的证明都用到了二项式定理，但是即使不会二项式定理，这道题也是可以做的。下面我将用其他方法证明其正确性。

引理：C_n^m = C_{n-1}^m + C_{n-1}^{m-1}

显然，要从N个元素中选取M个，第N个元素可以选或不选，如果选择了第N个元素，方案数为C_{n-1}^{m-1}，如果没有选择第N个元素，方案数为C_{n-1}^m，加起来就是我们要求的C_n^m 。

1. C_n^0-C_n^1+C_n^2+...+(-1)^nC_n^n=0

以n为奇数作为例子，偶数类似。下同。

显然C_n^0=C_n^n=1，原式可以写作：

1-(C_{n-1}^0+C_{n-1}^1)+(C_{n-1}^1+C_{n-1}^2)+...+(C_{n-1}^{n-2}+C_{n-1}^{n-1})-1

重组括号，裂项相消，代入C_n-1^0=C_{n-1}^{n-1}=1，即可得证。

2. C_n^0+C_n^1+C_n^2+...+C_n^n=2^n

显然，等式左边的意思就是从n个元素里选取任意多个元素，那么每个元素都有选或不选两种选择，总方案数当然是2^n。

将以上两个式子相加并约分，得到下式：

C_n^0+C_n^2+...+C_n^{n-1}=2^{n-1}

这就是我们要求的答案。

#include <bits/stdc++.h>
#define p 6662333
using namespace std;

long long x,ans=1,a=2;

int main()
{
    scanf("%lld",&x); x--;
    while (x)
    {
        if (x&1) ans=ans*a%p;
        a=a*a%p; x>>=1;
    }printf("%lld",ans);
}