ICPC 小故事
转眼间 PhD 都快结束了,本科期间的 ICPC 经历我都记不太清楚了,这里就讲讲 PhD 期间打 ICPC 的一些故事吧。不过没准啥时候会填一下本科期间的坑呢……
转眼间 PhD 都快结束了,本科期间的 ICPC 经历我都记不太清楚了,这里就讲讲 PhD 期间打 ICPC 的一些故事吧。不过没准啥时候会填一下本科期间的坑呢……
五人十天小旅游,San Diego,Las Vegas,Grand Canyon。
最近一直在写 Rust 代码,发现里面有好些写起来不舒服,不 ergonomic 的地方……大概我需要一些语法糖……
由于一些突发情况,我又需要去一趟墨西哥。
由于某些机缘巧合,我碰巧去了一趟墨西哥的 Monterrey,名字听起来和加州的 Monterey 很像……似乎这个城市看起来还行吧,有着墨西哥、南美最高楼。再加上 SIGYAO30'21 在 San Diego 举办,这样去墨西哥也很方便。
作为一个码农,我天天都在用终端,自然需要一个看着舒服用着顺手的终端。这次我就来介绍一下我用过的那些花里胡哨的东西……
\(\newcommand{\d}{\mathrm{d}}\)说到解析方法数质数,由于精度原因,如果要计算 \(\pi(10^{18})\) 的话,64 位浮点数已经不能满足要求了,所以我不得不实现自己的高精度。当然可以选用现成的库,例如著名的 MPFR,但是我觉得这样 overhead 太大了,毕竟我只需要 100 bit 就行了。
既然要实现浮点数,自然得实现一堆函数,其中有四个函数尤为重要:\(\exp, \log, \sin, \cos\)。当然,在实现之前,我们需要参考下别人的实现,例如 libm 。我们这里就拿 \(\exp\) 来举例,并假设我们现在已经支持基本的加减乘除了。
\(\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}\)这里我讲讲如何用 Dirichlet series 求一些算术函数的前缀和。这个算法我是在 Project Euler 的论坛里看到的,Lucy_Hedgehog 的帖子。但是他(她?)写的比较粗略,我就稍微写详细一点吧……
\(\newcommand{\eps}{\epsilon} \newcommand{\tO}{\widetilde O} \newcommand{\d}{\mathrm d} \newcommand{\hphi}{\widehat \phi} \newcommand{\hPhi}{\widehat \Phi} \newcommand{\sinc}{\text{sinc}}\)上次我们讲了 [LO],[Galway] 和 [Platt] 的大致思路,似乎一切都已经明了,只剩下最后一个难点了:\(\zeta\) 函数怎么求?这里我们就来介绍一下我 survey 到的几种求 \(\zeta(s)\) 的方法。