Categories/Note

随机渐进式光子映射（Stochastic Progressive Photon Mapping, SPPM）是光子映射系列算法的进阶算法，本文介绍如何实现 SPPM 以及如何将 SPPM 与路径追踪（Path Tracing, PT）结合。 …

本文主要介绍多重重要性采样（Multiple Importance Sampling）及其在光线追踪中的典型应用。 Multiple Importance Sampling Monte Carlo Path Tracing 在 Ray …

二分图 定义 如果一个图 G=(V,E)G=(V,E)G=(V,E) 中的结点可以被分为两个部分，且两个部分之内的点互相没有连边，则称这种图为二分图。如果每个结点的度数相等且都为 kkk，则称这种二分图为 kkk - 正则二分图。 判断 对 …

莫比乌斯反演可以用于优化一类式子的计算。 莫比乌斯函数 定义 莫比乌斯函数的定义如下： μ(n)={0∃ p2∣n∧p>1(−1)kn=∏i=1kpi \mu(n)= \begin{cases} 0 & \exists\ …

解各种同余方程是同余问题的一个重要部分，本文介绍各种同余方程的求解方法。 二元线性不定方程 形式 不定方程的范围很广泛，只要没有确定的解的方程都可以叫不定方程。本文主要讨论数论中的不定方程。 ax+by=c (a,b,c,x,y∈Z) …

Burnside 引理和 Pólya 定理主要用于解决计算本质不同方案数的计数问题。 群论 基本定义 群可以看成是一个由集合和某个二元运算组成的二元组 (S,⋅)(S,\cdot)(S,⋅)，这里的 ⋅\cdot⋅ 就代表一个二元运算，这个 …

欧拉函数 φ(n)\varphi(n)φ(n) 是一个重要的数论函数，它表示 [1,n][1, n][1,n] 中与 nnn 互质的数的个数。 欧拉函数性质 积性函数 积性函数的定义是：如果一个函数 f(n)f(n)f(n) 满足 …

拉格朗日插值是众多插值算法中的一种，插值是通过一些点来求出过这些点的多项式函数的过程。 算法思想 构造函数 给出 n+1n + 1n+1 个点 …

高斯消元主要用于求解线性方程组的解，同时可以解决某些有后效性的 DP 问题， 算法思想 增广矩阵 为了更方便地求解方程组，可以将系数和常数项放入矩阵，接下来就可以用一些矩阵的操作来消元了。 比如有一个方程组如下： …