最速输入问题(上)

Aster CODE➤GEASS, 理宅异闻录 Leave a Comment

屏幕上有一个字符, 如果只用全选复制粘贴, 要达到$n$个字符最少要多少次按键?

要想达到$N$个字符

  • 如果$N$是个素数,玩完了

只能一个一个复制了, ACVVVVVVVVVV...

也就是 N+2 次.

  • 如果N可以分解

那么我们找出他的一个因子 $\mathrm{i}$ ,另一个因子记为$ \mathrm{ j=N/i}$

也就是达到 $\mathrm{dp[i]}$ 之后粘贴 $j+1$ 次

要不就达到 $\mathrm{dp[j]}$ 之后粘贴$ i+1$ 次

$$\mathtt{dp[i] =Min[dp[j] + i/j + 2, dp[i/j] + j + 2]}$$

我们比较三种路径那个更小就行了.

当然所有路线一起比是一样的...

Read More

【π史话】BBP类公式

Aster CODE➤GEASS, 理宅异闻录 Leave a Comment

BBP公式全称为 贝利-波尔温-普劳夫公式 (Bailey–Borwein–Plouffe formula),该公式发现于1995年,以三位发表者的名字命名.

最初的一个BBP公式是:

\[\pi  = \sum\limits_{k = 0}^\infty  {\frac{1}{{{{16}^k}}}\left( {\frac{4}{{8k + 1}} - \frac{2}{{8k + 4}} - \frac{1}{{8k + 5}} - \frac{1}{{8k + 6}}} \right)} \]

证明不算太难,可以作为一道高数习题.一个思路是交换积分求和次序来将式子转化为有理分式积分.

\[\begin{aligned}
\int_0^{1/\sqrt 2 } {\frac{{{x^{p - 1}}}}{{1 - {x^8}}}{\text{d}}x} &= \int_0^{1/\sqrt 2 } {\sum\limits_{k = 0}^\infty {{x^{p - 1 + 8k}}} {\text{d}}x} \\
&= \sum\limits_{k = 0}^\infty {\int_0^{1/\sqrt 2 } {{x^{p - 1 + 8k}}{\text{d}}x} } \\
&= \sum\limits_{k = 0}^\infty {\frac{{{2^{ - 4k - \frac{p}{2}}}}}{{8k + p}}} \\
&= \frac{1}{{{2^{p/2}}}}\sum\limits_{k = 0}^\infty {\frac{1}{{{{16}^k}}}\frac{1}{{8k + p}}} \\
\end{aligned} \]

Read More

竞技场挑战

Aster CODE➤GEASS, GameのDay, 理宅异闻录 Leave a Comment

很多游戏中都有竞技场的设定,缴纳一定的入场费,然后匹配与你水平差不多的玩家,一定场数后有奖励,输满一定的局数就出局.

当然有个上限局数,赢满的话能得到十分丰厚的奖励.

我们以炉石传说为例代入数据看下:

这是一个玩的还算不错的普通玩家,他的胜率高达60%.但是他完成挑战的概率也仅仅4%不到.

Read More

模法导论(番外)

Aster CODE➤GEASS, 理宅异闻录 Leave a Comment

说说两个有趣的关于求模的算法.

第一个是阶乘求模.这个么,其实规模小的时候$\left( {a!\bmod n\quad a < n < {{10}^6}} \right)$也没什么优化可用.硬刚吧.

  1. 先朴素的把这个数算出来然后求模0.23s,good.
  2. 自己造个轮子把数算出来然后求模,0.70s,233,说了不要自己造轮子.
  3. 用Fold折叠列表,边乘边模,0.12s,Excellent! 如果是Haskell的话应该会更快吧,第一有惰性计算,第二乘法计算速度真的丧心病狂,当初刷OJ直接写a*b过了大数乘法,而且还是第一.......
  4. 所以我们想能不能从两边一起折叠这个列表,Sorry,MMA没有这种的,然后想到要是对折这个列表岂不是可以有${\log _2}n$的算法了?想得美,0.82s.
  5. 好吧对折太慢了,应该一次折叠100重,0.23s.Well,看来多出来的那么多次乘法和取模不管怎样反而消耗了更多的资源呐.
  6. 所以我们来用循环吧!1.02s,666,说了MMA里能不用循环就不要用循环,特别是不编译直接正面刚,而且用了编译还不如全部用C#写然后Link进来.我用C#写了个naïve的循环确实是0.1s左右.
  7. 想到个折中的办法,Nest尾递归一个二元组就不用维护列表了.0.16s,唔,不是很懂怎么搞的,会比Fold慢好玄学啊.

Read More

模法导论(下)

Aster CODE➤GEASS, 理宅异闻录 Leave a Comment

高阶模法

  • 幂塔求模

下面是本模导书的重点所在了.所谓幂塔就是形如${a^{{b^c}}}$的存在,基本上c稍微大一点就是算不出来的了.大丈夫,我们不是有上面的欧拉幂模定理大法吗?

例:求4^5^6的最后两位.

$$\begin{aligned}
&\quad \ {4^{{5^6}}}\bmod 100\\
&= {4^{{5^6}\bmod \varphi (100)}}\bmod 100\\
&= {4^{15625\bmod 40}}\bmod 100\\
&= {4^{25}}\bmod 100 \\
&= 4{({4^{12}}\bmod 100)^2}\bmod 100\\
&= 4{\left( {{{\left( {4096\bmod 100} \right)}^2}\bmod 100} \right)^2}\bmod 100\\
&= \cdots = 24\quad\textbf{Wrong process!}
\end{aligned}$$

Read More

模法导论(上)

Aster CODE➤GEASS, 理宅异闻录 Leave a Comment

今年双十一我们来研究些模法.

所谓模法就是对一个数求模.

$$\begin{aligned}
a &= nq + r\quad q \in \mathbb{Z},\left| r \right| < \left| n \right| \\
r &= a\bmod q\;or\;\bmod (a,q)
\end{aligned}$$

在两数都是正数的情况下就是一个数除以另一个数的余数.也就是说正数的时候等价于求余,负数的时候就和求余相反了.

用初等函数写出来就是:

$$r = a - n\left\lfloor {\frac{a}{n}} \right\rfloor  = \frac{n}{2} - \frac{n}{\pi }\sum\limits_{k = 1}^\infty  {\frac{{\sin (2\pi k\frac{a}{n})}}{k}} $$

本模导书收录了以下模法:

  • 模法理论:归零原理,恒等原理,交换原理,分配原理
  • 初阶模法:加法求模,乘法求模,除法求模
  • 中阶模法:快速幂求模,矩阵幂求模,幂同余,欧拉幂模
  • 高阶模法:幂塔求模以及迭代幂次模
  • 无等阶模法:阶乘模和二项模

Read More

语言黑洞

Aster CODE➤GEASS, 理宅异闻录 Leave a Comment

我今天又写了个德语,然后准备弃坑了,做到这份上感觉没啥意思了...

第一我发现Mathematica 10 开始的翻译功能就能翻译日文和罗马音了...亏我昨天写了半天的映射转换.

还有一个让我奔溃的就是MMA有API的来着,我咋没想到呢???Wolfram Alpha,Microsoft,Google都能用啊...

我干嘛要自己造轮子啊我勒个去...又浪费了一个礼拜的大好时光...弃坑弃坑...

Read More