题目链接

算法竞赛进阶指南-44.火车进出栈问题

一列火车 $ n $ 节车厢，依次编号为 $ 1,2,3,…,n $。

每节车厢有两种运动方式，进栈与出栈，问 $ n $ 节车厢出栈的可能排列方式有多少种。

输入格式

输入一个整数 $ n $，代表火车的车厢数。

输出格式

输出一个整数 $ s $ 表示 $ n $ 节车厢出栈的可能排列方式数量。

数据范围

$ 1 \le n \le 60000 $

输入样例：

3

输出样例：

5

Method : 位运算-二进制拆分

基础位运算，本题是快速幂的模板题。

注意两点:

1. 有取模运算时不要用自乘*=， 否则会影响计算顺序
2. return 时也要取模， 防止极端例子:n = 0且p = 1

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

LL a, b, p;

LL fast_pow(LL x, LL n) {
    LL res = 1LL;
    while (n) {
        if (n & 1) {
            res = res * x % p;
        }
        x = x * x % p;
        n = n >> 1;
    }
    return res % p;
}

int main() {
    cin >> a >> b >> p;
    cout << fast_pow(a, b) << endl;
    return 0;
}

复杂度分析

• 时间复杂度：${O(\log n)}$， 其中$\log n$为对n进行二进制拆分的时间复杂度。

• 空间复杂度：${O(1)}$。