SAC#1 - 组合数

题目背景

本题由世界上最蒟蒻最辣鸡最撒比的 SOL 提供。

寂月城网站是完美信息教室的官网。地址：http://191.101.11.174/mgzd 。

题目描述

辣鸡蒟蒻 SOL 是一个傻逼，他居然觉得数很萌！

今天他萌上了组合数，现在他很想知道 $\sum \rm{C}$${n}^{i}$ 是多少。其中 $\rm{C}$ 是组合数（即 $\rm{C}$${n}^{i}$ 表示 $n$ 个物品无顺序选取 $i$ 个的方案数），$i$ 取从 $0$ 到 $n$ 的所有偶数。

由于答案可能很大，请输出答案对 $6662333$ 的余数。

输入格式

输入仅包含一个整数 $n$。

输出格式

输出一个整数，即为答案。

样例 #1

样例输入 #1

3

样例输出 #1

4

提示

对于 $20%$ 的数据，$n \le 20$；

对于 $50%$ 的数据，$n \le 10^{3}$；

对于 $100%$ 的数据，$n \le 10^{18}$。

数论就要有数论的做法嘛

首先我们都知道组合数是与杨辉三角息息相关的，那么……

先看看杨辉三角吧：


其实第 $n$ 行的第 $m$ 个数就是 $C(n-1,m-1)$ 的值

那么我们还知道杨辉三角第 $n$ 行的值是 $2^{n-1}$

我们还可以证明得当 $n\geqslant2$ 时每一行奇数项的和与偶数项的和是相等的

于是……

其实偶数项的和就是每一行的和的一半，也就是 $2^{n-2}$

所以代码就很好写咯 [一个简单的快速幂就可以啦]

#include <cmath>
#include <cstdio>
#include <iostream>
#define ll long long
using namespace std;
ll c, ans = 1;
inline int quick_pow(ll b, ll k) {
    ll a = b;
    while (k > 0) {
        if (k & 1) {
            ans *= a;
            ans
        }
        a *= a;
        a
        k = k >> 1;
    }
    ans
    return ans;
}
int main() {
    ll a, b;
    scanf("
    c = 6662333;
    quick_pow(2, a - 1);
    printf("
    return 0;
}