Skip to content

Category Archives: 程序园

《背包问题九讲》2.0 beta1

下载地址在 http://love-oriented.com/pack/pack2beta1.pdf 全文各章语言均有更新,更新最大的章节是 3.4,提供了多重背包可行性问题的一种简明的O(VN)解法。 本文IOIFORUM首发,欢迎转载,但请保留出处。

LLVM笔记(0):在一切开始之前

(本文是 http://llvm.org/releases/2.9/docs/GettingStarted.html 的阅读笔记。) LLVM的安装包分为三部分,LLVM工具包,LLVM-GCC,测试集。 自己编译LLVM三者都需要,但在主流平台上都有编译好的binary。 讲了LLVM的安装,没发现什么特别需要注意的。 LLVM的目录结构 llvm/examples: 很多有用的代码示例 llvm/include llvm/include/llvm LLVM头文件 llvm/include/llvm/Support 支持LLVM工具的头文件,但不和LLVM的功能密切相关 llvm/include/llvm/Config configure脚本生成的头文件,主要是Unix/C中标准头文件的包装。 llvm/lib 大部分的源代码都在这里,LLVM中几乎所有的代码都以库的形式存在 llvm/lib/VMCore/ llvm/lib/AsmParser/ llvm/lib/BitCode/ llvm/lib/Analysis/ llvm/lib/Transforms/ llvm/lib/Target/ llvm/lib/CodeGen/ llvm/lib/Debugger/ llvm/lib/ExecutionEngine/ llvm/lib/Support/ llvm/lib/System/ llvm/projects 并非LLVM一部分,但与LLVM共同发布的项目 llvm/runtime 需要LLVM-GCC编译 llvm/test llvm/tools 各种使用LLVM命令行工具 llvm/utils 帮助开发LLVM的命令行工具

《寻寻觅觅 道阻且长》诚征试读者

《寻寻觅觅 道阻且长》是《动态规划的思考艺术》的一部分,《背包问题九讲》的续作,讲解了动态规划中的寻路(path-finding)问题。 目前的完成状态如上图所示(只完成了目录的框架的一部分),现诚征我每写完一节即可第一时间看到的试读者。需要的人数非常少,且要求比较高,请谨慎申请。要求如下: 和我以前就认识。也就是说,在你申请之前我就听说过你的名字或网名,和我在三次元中见过面更佳。 能为我的文章提出建设性批评意见。这一条不好考核,目前的考察方法是:请针对《背包问题九讲》alpha1版本尽最大努力提出您的建设性意见,我会根据意见的有价值程度进行评估。 能尽保密义务。我会每天一次将最新草稿发送给试读者,但试读者必须保证不发送给任何其它人。

《背包问题九讲》2.0 alpha1

四年前,我曾经有过一个写一系列DP相关文章的宏伟计划,但当时这个计划仅完成了第一部《背包问题九讲》就因为我感到个人能力不足的原因中止了。 现在,我打算将这个暂命名为“动态规划的思考艺术”的文章系列重新启动。其第一步便是用LaTeX重新修订那部广为传播并被做成过各种格式各种版本的“背包九讲”。 现在我已经完成了用LyX将九讲的原始文本输入并略加修饰的第一步,于是发布一个 alpha1 版本。下载地址在: http://love-oriented.com/pack/pack2alpha1.pdf 欢迎阅读并帮忙指正错漏之处,捉到的bugs较多或较大的同学有机会提前预览本系列将来的文章。

《简明数论》的简明笔记(下)

x²≡d (mod p)的问题。 ax²+bx+c≡0 (mod p)可通过配方转化。 (2ax+b)²≡b²-4ac(mod p) d是p的二次剩余当且仅当方程有解,否则为二次非剩余。 既约剩余系中恰有(p-1)/2个二次剩余和(p-1)/2二次非剩余。 d是二次剩余当且仅当d(p-1)/2≡1 (mod p),否则模为-1。 于是两二次剩余或两二次非剩余的积为二次剩余,二次剩余与非剩余的积为二次非剩余。 Legendre符号当d是p的二次剩余、非剩余及p|d时分别取值1、-1、0。 Gauss二次互反律的主要应用似乎是用来简化及计算Legendre符号的值,以求解二次同余方程。 但在编程中可直接利用来计算,复杂度是相同的。 Jacobi符号具有与Legendre符号相同的互反律,但似乎就与二次同余方程没什么关系了,目前还没看到应用。 关于同余方程的Lagrange定理的内容是同余方程的解数不超过它的次数。 可用归纳法证明,很优雅。 n次同余方程有n个解,当且仅当f(x)的次数小于等于p,且f(x)除xp-x所得的余式模p恒等于0。 对于次数大于p的高次同余方程,总存在一个次数不大于p、首项系数为1的等价同余方程,即是xp-x除f(x)所得的余式(再将首项系数化为1)。 例外是余式模p恒等于0,不妨认为此时的等价同余方程就是xp-x。 事实上,简化高次同余方程也可避免做多项式除法,可用Fermat小定理xp≡x (mod p)直接降低次数。 模为素数幂的同余方程的解法看上去很强大,但是前提是需要先解出模为素数的同余方程啊!难道除了直接验证没什么通用的解法?26节先放下。