P3414 SAC#1 - 组合数

求 \[\sum_{i = 0,2 | i}^{n}C_{n}^{i}\] 其中 n <= 1 000 000 000 000 000 000 (10^18)

Solution

这题评级有毒吧。。码量少可是包含知识点和推导方法不简单的呀

推导才是精华

复习一下 二项式定理 ：\[(a + b)^{n} = \sum_{k = 0}^{n}C_{n}^{k}a^{k}b^{n - k}\]

引理： \[\sum_{i = 0,2 | i}^{n}C_{n}^{i} = 2^{n - 1}\]

证明：

将 \(a = 1, b = 1\) 带入二项式定理， 得①式：\[2^{n} = \sum_{i = 0}^{n}C_{n}^{i}\]

将 \(a = -1, b = 1\) 带入二项式定理， 得②式： \[(1 - 1)^{n} = \sum_{i = 0, i \% 2 == 0}^{n}C_{n}^{i} - \sum_{i = 0, i \% 2 == 1}^{n}C_{n}^{i} = 0\]

①式 + ②式， 得③式： \[2\sum_{i = 0,2 | i}^{n}C_{n}^{i} = 2^{n} + 0 = 2^{n}\]

解得：\[\sum_{i = 0,2 | i}^{n}C_{n}^{i} = 2^{n - 1}\]

证毕。

快速幂解决问题

Code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define LL long long#define REP(i, x, y) for(LL i = (x);i <= (y);i++)using namespace std;LL RD(){ LL out = 0,flag = 1;char c = getchar(); while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();} while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();} return flag * out; }const LL M = 6662333;LL p;LL Q_pow(LL a, LL p){ LL ret = 1; while(p){ if(p & 1)ret = ret * a % M; a = a * a % M; p >>= 1; } return ret; }int main(){ p = RD(); printf("%lld\n", Q_pow(2, p - 1)); return 0; }