💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🍥 本次小米有两套卷，算法和其他岗位是不同的卷子，本套给大家带来小米 算法 的卷

1️⃣ 组合数推公式，本质是一个 卡特兰数，推不出来的小伙伴可能就 gg 了

2️⃣ 本质是最大子段和问题，能看出这个的基本这题也就会啦

🎲 01.括号匹配大师

问题描述

LYA 是一名程序员，她最近在研究括号匹配问题。在编程语言中，常见的括号包括圆括号 、方括号 、花括号 等。LYA 发现，一个合法的括号串需要满足以下三个条件之一：

1. 该括号串是空串。
2. 该括号串形如 ，其中 和 是一对匹配的括号（即 为左括号， 为右括号），而 是一个合法的括号串。
3. 该括号串形如 ，其中 和 都是合法的括号串。

例如：

• 是合法的括号串（满足条件 2，其中 为空串）。
• 是合法的括号串（满足条件 2，其中 为空串）。
• 是合法的括号串（满足条件 3，其中 ）。

现在，LYA 想知道：给定可使用的括号种类数 和括号串长度 ，有多少种不同的合法括号串可以组成？由于答案可能很大，LYA 只需要知道答案对 取模的结果。

输入格式

输入一行，包含两个正整数 和 ，分别表示括号串的长度和允许使用的括号种类数。

输出格式

输出一个整数，表示长度为 的合法括号串的数量对 取模的结果。

样例输入

6 2

样例输出

40

数据范围

• 
• 
• 输入保证 为偶数

题解

组合数学问题，可以通过卡特兰数（Catalan Number）来解决。

需要理解卡特兰数的性质。卡特兰数 表示长度为 的合法括号序列的数量（只考虑一种括号的情况）。卡特兰数的通项公式为：

对于当前问题，需要考虑 种不同的括号。对于长度为 的括号串，实际上是在选择 对括号。每一对括号有 种选择，所以最终的结果应该是：

参考代码

• Python

def solve(n, k):
    mod = 998244353
    
    def inv(x):
        return pow(x, mod - 2, mod)
    
    cat = 1  # 初始化卡特兰数为 C_0 = 1
    for i in range(n // 2):
        cat = cat * (4 * i + 2) * inv(i + 2) % mod
    
    result = cat * pow(k, n // 2, mod) % mod
    return result

# 读取输入
n, k = map(int, input().split())

# 计算并输出结果
print(solve(n, k))

• Java

import java.util.Scanner;

public class Main {
    static final int MOD = 998244353;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        System.out.println(solve(n, k));
    }

    static long solve(int n, int k) {
        long cat = 1;  // 初始化卡特兰数为 C_0 = 1
        for (int i = 0; i < n / 2; i++) {
            cat = cat * (4L * i + 2) % MOD;
            cat = cat * inv(i + 2) % MOD;
        }
        
        long result = cat * pow(k, n / 2) % MOD;
        return result;
    }

    static long inv(long x) {
        return pow(x, MOD - 2);
    }

    static long pow(long base, long exp) {
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = result * base % MOD;
            }
            base = base * base % MOD;
            exp >>= 1;
        }
        return result;
    }
}

• Cpp

#include <iostream>
using namespace std;

const int MOD = 998244353;

// 快速幂函数
long long pow(long long base, int exp) {
    long long result = 1;
    while (exp > 0) {
        if (exp & 1) result = result * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

// 计算逆元
long long inv(int x) {
    return pow(x, MOD - 2);
}

// 主要解题函数
long long solve(int n, int k) {
    long long cat = 1;  // 初始化卡特兰数为 C_0 = 1
    for (int i = 0; i < n / 2; i++) {