归档
2026 年 04 月
2026-04-14
2023 摄于泰安龙泽胡
2026-04-06
bitset 就像一个极其紧凑的 bool 数组，但它最大的杀手锏是支持所有位运算，并且在底层是以 32 位或 64 位整数为一个基本单元进行并行计算的。这意味着对 bitset 的整体操作（如与、或、异或、左移、右移）的耗时只有普通数组的 \frac{1}{64}。 一、 基础语法与声明 首先需要
2026 年 03 月
2026-03-24
背包问题九讲 2.0 beta1.2 本文题为《背包问题九讲》，从属于《动态规划的思考艺术》系列。 2011 年 9 月，本系列文章由原作者用 LaTeX 重新制作并全面修订，您现在看到的是 2.0 beta1.2 版本，修订历史及最新版本请访问 https://github.com/tianyic
2026-03-24
重构线性代数 (一)：基石与视界 —— 向量与线性空间 在传统的大学课堂上，线性代数往往被教成了一门“算术课”——如何计算矩阵相乘、如何用高斯消元法解方程、如何套公式求逆矩阵。但如果只停留在数字的机械运算上，当你面对计算机图形学、机器学习或高级算法时，你会感到寸步难行。 本系列旨在为你建立线性代数的
2026-03-24
环形 DP 的数学本质：状态转移图与矩阵的迹 —— 洛谷 P1357 花园 背后的线性代数原理 在解决《花园》这道题时，我们使用到了“状态压缩”和“矩阵快速幂”。但如果不从纯数学的角度去理解它，这就只是一套死记硬背的代码模板。 本文将剥开代码的外衣，从图论 (Graph Theory) 和 线性代数
2026-03-24
组合数学与 DP 优化：硬币购物 (容斥原理经典模型) —— 洛谷 P1450 [HAOI2008] 深度解析 题目简述：共有 4 种硬币，面值分别为 c_1, c_2, c_3, c_4。进行 T 次询问，每次询问给出这 4 种硬币的数量限制 d_1, d_2, d_3, d_4，问凑出总价值 s
2026-03-24
矩阵快速幂与环形状压 DP：洛谷 P1357 花园 详解 题目简述：有一个周长为 N 的环形花园，每个位置可以种 'C' 或 'P' 两种花。要求任意连续的 M 个位置中，'C' 的数量不能超过 K 个。求合法的种植方案数，对 10^9 + 7 取模。 数据范围：4 \leq N \leq 10^{
2026-03-24
轮廓线 DP (Broken Profile DP)：网格图上的状态压缩艺术 在处理棋盘、网格图的覆盖问题时（例如骨牌铺满问题、哈密顿路径计数），我们经常会想到状态压缩 DP。传统的状压 DP 通常是“逐行转移”的：用一个二进制数表示第 $i$ 行的状态，推导第 $i+1$ 行。但逐行转移的痛点在于
2026-03-23
围棋：极简规则与状态空间的数学推导 围棋（Go / Weiqi）是世界上最古老且最复杂的棋类游戏。它的规则极其简单，但由于棋盘广阔、落子自由，其演化出的变化数量超越了可观测宇宙中的原子总数。本文将系统梳理围棋的核心规则，并从计算机科学的角度，详细推导围棋“合法棋面数量（状态空间）”的计算方法与震撼结
2026-03-23
数论核心：乘法逆元 (Modular Multiplicative Inverse) 详解与算法实现 在算法竞赛和密码学中，我们经常会遇到要求将最终结果对某个大质数（如 10^9+7 或 998244353）取模的情况。 对于加、减、乘法，模运算都满足分配律，我们可以一边计算一边取模。但是，除法是不