Posts by hostmaster

题目 题解 定义 $N$ 的 Fibonacci 表示 $a_i$： $$N = \sum a_if_i$$ 其中 $f_i$ 为 Fibonacci 数，$f_1 = f_2 = 1$。注意 Fibonacci 表示可能不唯一。 有两个性质：所有操作可撤销 和 所有操作不改变 Fibonacci 表示下的和（$\sum a_if_i$）…

题意 给定长度为 $N$ 的两个排列 $p$ 和 $q$，求长度为 $N$ 的排列 $r$ 的个数，使得 $r_i \neq p_i$ 且 $r_i \neq q_i$，对于任意的 $1 \leq i \leq N$ 都成立。 $1 \leq N \leq 3000$ 题解 设 $f_i$ 表示任意选 $i$ 个位置，对于这些位置都有 $r_i = p_i$…

概述 不同方法的收敛速度和迭代次数不同，我们会根据需要找到最适合的方法。 下文计划描述的算法有 GD，SGD，PAGE。 $\epsilon$-solution 我们需要找到一个方式来描述算法当前解的优劣。 最简单的方法就是用 $\left\Vert\nabla f\left(\hat x\right)\right\Vert_2$。 那我…

概述 梯度下降法用于求解多变量局部最小值点问题，常用于机器学习。 过程 如果一个函数 $F\left(\mathbf x\right)$ 在邻域内有定义且可导，那么 $F\left(\mathbf x\right)$ 在 $\mathbf a$ 点沿着在 $F$ 在 $a$ 点的负梯度（Gradient）方向 $-\nabla F\left(a\right)$…

概述 本文将讲述基础的机器学习理论。从零开始，推导一个机器学习模型。 目的 我们的目的很简单，做出一个能识别手写数字的模型。为了简单起见，本文只讨论如何让模型区分两个数字，即输入手写图片，让模型判断是 $3$ 还是 $7$。 表示方式 为了配合 MNIST 训练集，我们统一使用 $28 \times 28$ 大小的 8-bit 灰度图片，…

一维离散随机游走常返性 一个随机过程 $X = \left(X_n\right)_{n \in \mathbb N}$，$X_0 = 0$，$X_{n + 1}$ 在 $X_n$ 基础上等概率随机加 $1$ 或减 $1$。$X$ 是马尔可夫（Markov）链，分析原点的常返性（瞬时 / 常返 / 正常返 / 零常返）。 假设 $n$ 是正…

布尔（Boolean）函数的傅里叶分析 对比普通函数的傅里叶分析，我们试图将傅里叶分析的思想迁移到布尔函数上。傅里叶分析找到一组正交基（Orthogonal Basis）。我们在布尔函数上也能找到这样的基。具体来说，令 $$\chi_i\left(x\right) = \prod\limits_{j \in i}x_j$$ ，选系统 $\chi_i : i \subseteq \left[n\right]$…

Yandze 公式 概述 设 $$ D\left(h\right) = \left\{\left(x_1, \ldots, x_n\right) \mid x_i > 0, k_i > 0, \sum\limits_{i = 1}^n{x_i}^{k_i} < h\right\}, h > 0 $$ Yandze 公式用于求解 $D\left(h\right)$…

简述 单位根反演（unit-root-inversion），是一种将原式通过转换为一些带有单位根的式子，然后通过单位根的性质计算的方法。 公式 $$\left[d \mid n\right] = \frac1d\sum\limits_{i = 0}^{d - 1}\omega_d^{ni}$$ 证明 当 $d \mid n$ 时，上述式子…

题意 证明：若 $3^n - 1$ 是 12-smooth 数，则 $n \leq 5$ 题解 一个神奇的证明，来自 这里 如果我们可以证明，$2^a5^b7^c11^d$ 不能描述出所有 $3^n - 1$，对于 $n \geq 6$ 和 $a \geq 1$ 且 $b, c, d \geq 0$，那么原问题得证。 引理 1：$c = 0$…