1. 问题形式化定义 1.1 题目原描述 将 $M$ 个相同的苹果放入 $N$ 个相同的盘子中，允许盘子为空，不区分盘子的顺序（如分拆 $[5,1,1]$ 与 $[1,5,1]$ 视为同一种），求不同的分法总数 $K$ 。 1.2 数学建模 该问题等价于组合数学中的整数无序分拆问题： 给定非负整数 $M$ （被分拆数）与正整数 $N$ （分拆的最大…

Kadane算法及其在一维与二维最大子段和问题中的应用 摘要 本文系统阐述Kadane算法的核心原理、数学证明及其在一维最大子数组和、二维最大子矩阵和问题中的应用。通过严谨的数学推导与代码实现，展示该算法从一维到二维的扩展逻辑，并补充证明一维场景下前缀和方法与Kadane算法的数学等价性，为算法复习与应用提供参考。 引言 最大子段和问题是算法设计中…

逆元的三种核心求解算法：原理、证明与实现 前置定义与核心定理 模乘法逆元的严格定义 设 $m$ 为正整数，对于整数 $a$ ，若存在整数 $x$ 满足同余式： $a \cdot x \equiv 1 \pmod{m}$ 则称 $x$ 为 $a$ 在模 $m$ 下的乘法逆元，记作 $\mathrm{inv}(a) \pmod{m}$ 。 逆元存在性充…

欧几里得算法与扩展欧几里得算法：原理、证明及实现 1 欧几里得算法 1.1 定义与基本符号 设 $a, b$ 为不全为0的正整数， $\gcd(a, b)$ 表示 $a$ 与 $b$ 的最大公约数。 对 $a, b$ 做带余除法： $a = q\cdot b + r,\quad 0\le r < b$ 其中 $q = \lfloor \fra…

快速幂全知识点 一、快速幂核心优化逻辑 核心：通过底数自乘复用中间结果，替代重复乘法运算，将时间复杂度从O(n)（暴力算法）降至O(logₖn)（快速幂）；二进制、三进制、十进制快速幂优化逻辑一致，差异仅在于指数拆分基底与底数自乘方式。 1. 暴力算法 计算 $a^{10}$ 需连续执行10次a的乘法运算，即 $a \times a \times …