P3414 SAC#1

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$$
①式 + ②式， 得③式： $$2sum_{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<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
#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
", Q_pow(2, p - 1));
	return 0;
	}