SAC#1 - 组合数

【题目描述】
辣鸡蒟蒻SOL是一个傻逼，他居然觉得数很萌！
今天他萌上了组合数。现在他很想知道simga(C(n,i))是多少；其中C是组合数（即C(n,i)表示n个物品无顺序选取i个的方案数），i取从0到n所有偶数。
由于答案可能很大，请输出答案对6662333的余数。
【输入格式】
输入仅包含一个整数n。
【输出格式】
输出一个整数，即为答案。
【样例输入】
3
【样例输出】
4
【数据范围】
n<=10^18
【分析】
首先由二项式定理我们可以知道C(n,0)+C(n,1)+C(n,2)+…+C(n,n)=2^n，然后i只能取偶数，所以答案是2^(n-1)。接下来快速幂不解释。

var
  a,b,n:int64;
function f(a,b,n:int64):int64;
var
  t,y:int64;
begin
  t:=1; y:=a;
  while b<>0 do begin
    if(b and 1)=1 then t:=t*y mod n;
    y:=y*y mod n;
    b:=b shr 1;
  end;
  exit(t);
end;
begin
  read(b);
    a:=2;
    b:=b-1;
    n:=6662333;
  write(f(a,b,n));
end.

SAC#1 - 组合数

推荐阅读