zcmimi's blog

查看原题

点击跳转

题意:

\displaystyle \sum_{i\mod 2=0} {n\choose i}

题解

  1. {n\choose 0}+{n\choose 1}+{n\choose 2}+\dots+{n\choose n}=0
  2. {n\choose 0}-{n\choose 1}+{n\choose 2}-\dots+(-1)^n{n\choose n}=0
  3. {n\choose 0}+{n\choose 2}+{n\choose 4}+\dots={n\choose 1}+{n\choose 3}+{n\choose 5}+\dots=2^{n-1}

证明

二项式定理:

(a+b)^n={n\choose 0}a^n+{n\choose 1}a^{n-1}b+\dots+{n\choose i}a^{n-i}b^i+\dots+{n\choose n}b^n

a=b=1时,可证明1,

a=-1,b=1时,可证明2,

1式+2式可证明3

#include<bits/stdc++.h>
const int P=6662333;
int pw(int x,int b){
    int res=1;
    while(b){
        if(b&1)res=1ll*res*x%P;
        b>>=1;x=1ll*x*x%P;
    }
    return res;
}
int main(){
    long long n;
    scanf("%lld",&n);
    printf("%d\n",pw(2,(n-1)%(P-1)));
}
LG 3414 SAC#1 - 组合数
comment评论
Search
search