1
// 快速幂：计算 a^n mod MOD
2
// 迭代版（面试推荐，不易写错）
3
const int MOD = 1e9 + 7;
4

5
long long fastPow(long long a, long long n) {
6
    long long result = 1;
7
    a %= MOD;
8

9
    while (n > 0) {
10
        if (n & 1) {                // 当前位是 1：乘上这个 bit 对应的幂
11
            result = (result * a) % MOD;
12
        }
13
        a = (a * a) % MOD;          // 平方（对应下一位的幂）
14
        n >>= 1;                     // 右移一位
15
    }
16
    return result;
17
}

1
#include <vector>
2

3
using Matrix = std::vector<std::vector<long long>>;
4

5
Matrix matMul(const Matrix& A, const Matrix& B, int mod = 1e9 + 7) {
6
    int n = A.size();
7
    Matrix C(n, std::vector<long long>(n, 0));
8

9
    for (int i = 0; i < n; ++i) {
10
        for (int k = 0; k < n; ++k) {          // k 在中间（缓存优化）
11
            if (A[i][k] == 0) continue;
12
            for (int j = 0; j < n; ++j) {
13
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
14
            }
15
        }
16
    }
17
    return C;
18
}
19

20
Matrix matPow(Matrix A, long long n) {
21
    int size = A.size();
22
    Matrix result(size, std::vector<long long>(size, 0));
23
    for (int i = 0; i < size; ++i) result[i][i] = 1;  // 单位矩阵
24

25
    while (n > 0) {
26
        if (n & 1) result = matMul(result, A);
27
        A = matMul(A, A);
28
        n >>= 1;
29
    }
30
    return result;
31
}
32

33
// O(log n) 求斐波那契第 n 项
34
long long fib(long long n) {
35
    if (n <= 2) return 1;
36
    Matrix A = {{1, 1}, {1, 0}};
37
    Matrix An = matPow(A, n - 1);
38
    return An[0][0];  // F(n) = An[0][0] * F(1) + An[0][1] * F(0)
39
}

1
// 大数加法（字符串表示）
2
std::string addStrings(std::string num1, std::string num2) {
3
    std::string result;
4
    int i = num1.size() - 1, j = num2.size() - 1, carry = 0;
5

6
    while (i >= 0 || j >= 0 || carry) {
7
        int digit1 = (i >= 0) ? num1[i--] - '0' : 0;
8
        int digit2 = (j >= 0) ? num2[j--] - '0' : 0;
9
        int sum = digit1 + digit2 + carry;
10
        result.push_back('0' + sum % 10);
11
        carry = sum / 10;
12
    }
13
    std::reverse(result.begin(), result.end());
14
    return result;
15
}

1
// 辗转相除法
2
// gcd(a, b) = gcd(b, a % b)
3
// 复杂度 O(log min(a, b))
4
int gcd(int a, int b) {
5
    return b == 0 ? a : gcd(b, a % b);
6
}
7

8
// 迭代版（避免递归栈）
9
int gcd_iter(int a, int b) {
10
    while (b != 0) {
11
        int temp = b;
12
        b = a % b;
13
        a = temp;
14
    }
15
    return a;
16
}
17

18
// LCM: lcm(a, b) = a / gcd(a, b) * b  （先除后乘防溢出）
19
int lcm(int a, int b) {
20
    return a / gcd(a, b) * b;
21
}

1
// 扩展欧几里得：返回 gcd(a, b)，同时计算出 x, y
2
int exgcd(int a, int b, int& x, int& y) {
3
    if (b == 0) {
4
        x = 1;
5
        y = 0;
6
        return a;
7
    }
8
    int x1, y1;
9
    int d = exgcd(b, a % b, x1, y1);
10
    x = y1;
11
    y = x1 - (a / b) * y1;
12
    return d;
13
}
14

15
// 求 a 在模 m 下的逆元（即 a * x ≡ 1 (mod m)）
16
// 条件：gcd(a, m) == 1
17
int modInverse(int a, int m) {
18
    int x, y;
19
    int d = exgcd(a, m, x, y);
20
    if (d != 1) return -1;  // 逆元不存在
21
    return (x % m + m) % m;  // 保证正数
22
}

1
// 筛出 [2, n] 的所有质数
2
// O(n log log n)
3
std::vector<int> sieveOfEratosthenes(int n) {
4
    std::vector<bool> isPrime(n + 1, true);
5
    isPrime[0] = isPrime[1] = false;
6

7
    for (int i = 2; i * i <= n; ++i) {
8
        if (!isPrime[i]) continue;
9
        // 从 i*i 开始（更小的倍数已被之前的质数标记）
10
        for (int j = i * i; j <= n; j += i) {
11
            isPrime[j] = false;
12
        }
13
    }
14

15
    std::vector<int> primes;
16
    for (int i = 2; i <= n; ++i) {
17
        if (isPrime[i]) primes.push_back(i);
18
    }
19
    return primes;
20
}

1
// 每个合数只被其最小质因数筛掉一次 → O(n)
2
std::vector<int> linearSieve(int n) {
3
    std::vector<int> primes;
4
    std::vector<bool> isComposite(n + 1, false);
5

6
    for (int i = 2; i <= n; ++i) {
7
        if (!isComposite[i]) {
8
            primes.push_back(i);
9
        }
10
        // 用 i 去筛掉后面的合数
11
        for (int p : primes) {
12
            if ((long long)i * p > n) break;
13
            isComposite[i * p] = true;
14
            if (i % p == 0) break;  // ⚠️ 关键！保证每个合数被最小质因数筛
15
        }
16
    }
17
    return primes;
18
}

1
// O(√n) 质因数分解
2
std::vector<std::pair<int, int>> factorize(int n) {
3
    std::vector<std::pair<int, int>> factors;  // {质因数, 次数}
4

5
    for (int i = 2; i * i <= n; ++i) {
6
        if (n % i == 0) {
7
            int count = 0;
8
            while (n % i == 0) {
9
                n /= i;
10
                ++count;
11
            }
12
            factors.push_back({i, count});
13
        }
14
    }
15
    if (n > 1) factors.push_back({n, 1});  // 剩余的大质数
16
    return factors;
17
}

1
// 杨辉三角法求 C(n, k)
2
// 递推：C(n, k) = C(n-1, k-1) + C(n-1, k)
3
// 优点：可以一次算出一整行，且自动取模
4
std::vector<std::vector<long long>> pascal(int maxN, int mod = 1e9 + 7) {
5
    std::vector<std::vector<long long>> C(maxN + 1,
6
        std::vector<long long>(maxN + 1, 0));
7

8
    for (int i = 0; i <= maxN; ++i) {
9
        C[i][0] = C[i][i] = 1;
10
        for (int j = 1; j < i; ++j) {
11
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
12
        }
13
    }
14
    return C;
15
}
16

17
// 公式法求单个组合数（需要预处理阶乘和逆元）
18
// C(n, k) = n! / (k! * (n-k)!)
19
long long comb(int n, int k, const std::vector<long long>& fact,
20
               const std::vector<long long>& invFact, int mod = 1e9 + 7) {
21
    if (k < 0 || k > n) return 0;
22
    return fact[n] * invFact[k] % mod * invFact[n - k] % mod;
23
}

1
// 从未知大小的数据流中随机取 k 个样本
2
// 保证每个元素被选中的概率相等（= k / n）
3
std::vector<int> reservoirSample(const std::vector<int>& stream, int k) {
4
    std::vector<int> reservoir(k);
5
    int n = stream.size();
6

7
    // 前 k 个直接放入
8
    for (int i = 0; i < k; ++i) {
9
        reservoir[i] = stream[i];
10
    }
11

12
    // 后续元素以 k / (i+1) 的概率替换
13
    for (int i = k; i < n; ++i) {
14
        int j = rand() % (i + 1);
15
        if (j < k) {
16
            reservoir[j] = stream[i];
17
        }
18
    }
19
    return reservoir;
20
}

1
// 进阶：最小化 rand7() 的调用次数
2
int rand10_optimized() {
3
    while (true) {
4
        int a = rand7(), b = rand7();
5
        int num = (a - 1) * 7 + b;   // [1, 49]
6
        if (num <= 40) return (num - 1) % 10 + 1;
7

8
        // 利用被拒绝的 [41, 49] → 映射到 [1, 63] 再试
9
        a = num - 40;                  // a ∈ [1, 9]
10
        b = rand7();
11
        num = (a - 1) * 7 + b;        // [1, 63]
12
        if (num <= 60) return (num - 1) % 10 + 1;
13

14
        // 再利用 [61, 63] → 映射到 [1, 21] 再试
15
        a = num - 60;                  // a ∈ [1, 3]
16
        b = rand7();
17
        num = (a - 1) * 7 + b;        // [1, 21]
18
        if (num <= 20) return (num - 1) % 10 + 1;
19
    }
20
}

1
// 暴力 O(n²)：对每个点，统计其他点与它的斜率
2
int maxPoints(std::vector<std::vector<int>>& points) {
3
    int n = points.size();
4
    if (n <= 2) return n;
5

6
    int ans = 0;
7
    for (int i = 0; i < n; ++i) {
8
        std::unordered_map<std::string, int> slopeCount;
9
        int same = 1;  // 与 i 重合的点数
10

11
        for (int j = i + 1; j < n; ++j) {
12
            int dx = points[j][0] - points[i][0];
13
            int dy = points[j][1] - points[i][1];
14

15
            if (dx == 0 && dy == 0) {
16
                ++same;
17
                continue;
18
            }
19

20
            // 用 gcd 约分避免浮点精度问题
21
            int g = gcd(std::abs(dx), std::abs(dy));
22
            dx /= g;
23
            dy /= g;
24

25
            // 统一符号：让 dx 始终非负
26
            if (dx < 0) { dx = -dx; dy = -dy; }
27
            if (dx == 0) dy = 1;  // 垂直线统一表示
28

29
            std::string key = std::to_string(dx) + "/" + std::to_string(dy);
30
            ++slopeCount[key];
31
        }
32

33
        ans = std::max(ans, same);
34
        for (auto& [_, cnt] : slopeCount) {
35
            ans = std::max(ans, cnt + same);
36
        }
37
    }
38
    return ans;
39
}

1
// 模拟长除法，余数重复出现时开始循环节
2
std::string fractionToDecimal(int numerator, int denominator) {
3
    if (numerator == 0) return "0";
4

5
    std::string result;
6
    if ((numerator < 0) ^ (denominator < 0)) result += '-';
7

8
    long long n = std::llabs((long long)numerator);
9
    long long d = std::llabs((long long)denominator);
10

11
    // 整数部分
12
    result += std::to_string(n / d);
13
    long long remainder = n % d;
14
    if (remainder == 0) return result;
15

16
    result += '.';
17

18
    // 小数部分：用哈希表记录余数出现的位置
19
    std::unordered_map<long long, int> pos;
20
    while (remainder != 0) {
21
        if (pos.count(remainder)) {
22
            result.insert(pos[remainder], "(");
23
            result += ')';
24
            break;
25
        }
26
        pos[remainder] = result.size();
27
        remainder *= 10;
28
        result += std::to_string(remainder / d);
29
        remainder %= d;
30
    }
31
    return result;
32
}

1
// RPG 中常见的伤害衰减：每次攻击后伤害衰减为原来的 decay 倍
2
// 第 n 次攻击的伤害 = baseDamage * decay^(n-1)
3
// 总伤害（前 N 次攻击）= baseDamage * (1 - decay^N) / (1 - decay)
4
float totalDamage(float baseDamage, float decay, int attacks) {
5
    // 用快速幂思想计算 decay^attacks
6
    float decayN = 1.0f;
7
    float base = decay;
8
    int exp = attacks;
9
    while (exp > 0) {
10
        if (exp & 1) decayN *= base;
11
        base *= base;
12
        exp >>= 1;
13
    }
14
    return baseDamage * (1.0f - decayN) / (1.0f - decay);
15
}

1
#include <random>
2
#include <vector>
3

4
class Deck {
5
    std::vector<int> _cards;
6

7
public:
8
    Deck(int numCards) {
9
        _cards.resize(numCards);
10
        std::iota(_cards.begin(), _cards.end(), 0);
11
    }
12

13
    void shuffle() {
14
        std::random_device rd;
15
        std::mt19937 gen(rd());
16

17
        for (int i = _cards.size() - 1; i > 0; --i) {
18
            std::uniform_int_distribution<int> dist(0, i);
19
            std::swap(_cards[i], _cards[dist(gen)]);
20
        }
21
    }
22

23
    int draw() {
24
        if (_cards.empty()) shuffle();  // 抽完了重新洗牌
25
        int card = _cards.back();
26
        _cards.pop_back();
27
        return card;
28
    }
29
};

1
// 从在线玩家列表中随机选取一个对手，不遍历两遍
2
struct Player {
3
    int id;
4
    int rating;
5
};
6

7
Player findRandomOpponent(const std::vector<Player>& onlinePlayers,
8
                          int myRating, int maxDiff) {
9
    Player selected;
10
    int count = 0;
11

12
    for (const auto& player : onlinePlayers) {
13
        if (std::abs(player.rating - myRating) > maxDiff) continue;
14
        ++count;
15
        // 蓄水池抽样：以 1/count 的概率选中当前玩家
16
        if (rand() % count == 0) {
17
            selected = player;
18
        }
19
    }
20
    return selected;  // 如果没找到匹配对手，count = 0
21
}