Zihe JI

LeetCode 每日一题 2025/07/28 – 统计按位或能得到最大值的子集数目 问题描述给你一个整数数组 nums，找出所有非空子集（subset）的按位或（bitwise OR）能得到的最大值，并返回按位或能得到最大值的 不同非空子集 的 个数。 子集的定义：如果数组 a 可以由数组 b 删除若干元素（或不删除）得到，则 a 是 b 的一个子集。 如果选中的元素下标位置不一样，则认为两个子集不同。 子集的按位或：a[0] OR a[1] OR ... OR a[a.length - 1]。 解法一：动态规划数学描述设数组为 。定义状态函数 即从前 个元素中选取的子集，其按位或恰好为 的方案数。我们关心的目标按位或最大值为 最终答案即为. 初始条件 状态转移对于每个 ，考虑第 个元素 ，有两种选择： 不选 ，子集 OR 保持不变： 选 ，若之前 OR 值为 ，则新 OR 值为 ： 合并得转移方程： 最终结果遍历完所有 后，最大按位或为 ，答案为 代码12345678910111213class Solution: de...

问题描述一枚不均匀的硬币，投出正面概率1/3, 投出反面概率2/3。甲乙交替投掷，先正后反则正面者胜。甲先手，求后手乙的胜率。 方法一：状态转移矩阵求解复习马尔科夫链 定义马尔科夫链是一种随机过程，其核心特性是“无记忆性”——下一步的状态只依赖于当前状态，而与此前如何到达该状态的路径无关。换句话说，若 表示第 步所处的状态，则 转移矩阵如果状态空间有 种可能，记状态集合为 ，则可以用一个 的转移概率矩阵 来描述： 吸收态与瞬时态 吸收态（absorbing state）：一旦进入该状态，就不再离开。矩阵中对应行在自身列上为 1，其余为 0。 瞬时态（transient state）：有可能迁移到其他状态，也可能最终被吸收。 若将吸收态排在前面，矩阵 可分块表示为 其中： 是 单位矩阵，表示 个吸收态自我保持； 是剩余瞬时态间的转移子矩阵； 是从瞬时态到吸收态的转移子矩阵。 基本矩阵与吸收概率定义基本矩阵（fundamental matrix） 它的第 元素给出“从瞬时态 最终到达瞬时态 的期望访问次数”。进一步，通过 我们可...

线性基（又称 XOR 基、异或基）是用来高效处理一组数在线性空间（GF(2) 向量空间）上的“异或线性组合”问题的数据结构。它的核心思想是：把一组整数看成二进制向量，维护一组“基向量”，使得任意一个数都能表示成这些基向量的异或和，且基向量之间两两“独立”（无法互相通过异或得到）。 为什么需要线性基？ 求最大子集异或和 给定一组数，选一个子集，使得它们的异或和最大。 判断一个数能否表示 给定目标值 T，判断是否存在若干数异或后等于 T。 枚举所有可能的异或和 统计所有子集能产生的不同异或和数量。 核心原理 向量空间视角 把整数看作长度为 W （通常是 32 或 64）的二进制向量，异或运算对应于 GF(2) 上的向量加法。 基向量 维护一个长度为 W 的数组 basis[]，其中 basis[k] 是最高位为 k （从 0 到 W−1）的“基向量”。 插入新向量 对于待插入的数 x： 1234567for k = W-1 … 0: if 第 k 位的 x 为 1: if basis[k] == 0: basis[k] = ...