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

Salty_Fish787 · 2019-08-20 19:39:44 · 题解

• 题意： 求 \sum_{i\in[0,n],2|i}C_n^i

  的值。答案对6662333取模，且n\leq 10^{18}。

• 前置芝士：二项式定理 (a+b)^n=\sum_{i=0}^n C_n^ia^ib^{n-i}

  将a=1,b=1代入：

  (1+1)^n=2^n=\sum_{i=0}^n C_n^i

  即

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

  将a=1,b=-1代入：

  (1-1)^n=0=\sum_{i=0}^n (-1)^iC_n^i

  即

  C_n^0-C_n^1+C_n^2+...+(-1)^nC_n^n=0(2)
• 分析：由(1)式+(2)式除以2得： C_n^0+C_n^2+C_n^4+...+C_n^{[\frac{n}{2}]\times 2}=\frac{2^n+0}{2}=2^{n-1}

  其中[x]表示x的整数部分。当x为奇数时，[\frac{x}{2}]\times 2=x-1；当x为偶数时，[\frac{x}{2}]\times 2=x。 即

  \sum_{i\in[0,n],2|i}C_n^i=2^{n-1}

  综上所述，直接输出2^{n-1}mod6662333的值即可。用快速幂维护。

• code: