AFAIK

Valar Morghulis

前几个月的 UyHiP 连题解都没看……

Problem

定义一个括号序列的值为:所有括号对的深度的积。例如 ((())()) 的值为 3*2*2*1 = 12

求所有 \(n\) 个括号的括号序列的权值和。要求给出一个 closed-form 。

Solution

下个月再发?

其实非常简单啦。

答案非常简单,但是求一个简单的解释。

我是直接分析 dp 。首先这个题有个非常简单的 dp : \(f_{i, j}\) 表示 \(i\) 个字符深度为 \(j\) 的积的总和。打出来后发现是有规律的……于是数学归纳法就好。

Brand 给了一个特别漂亮的解释。对于一个合法的串 S ,假设是 (()()) 吧,我们在其左边插入一个 ( ,再在其它任意一个位置插入 ) ,可以得到

  • ()(()())
  • (()()())
  • ((())())
  • ((()()))
  • ((()()))
  • ((()()))

注意每个串可以由很多种方式得到,而方案数恰好就是这个序列的权值。每次的 ) 插入方案数为 \(2n + 1\) ,所以总方案数 \(\prod_{i=0}^{n-1} (2i + 1)\)

某盾曰:这肯定是出题人在算 Catalan 的时候算错了然后发现是这么个东西再出出来的!

nonsense

考试后谈论分数什么的毫无意义吧。

他要考得好我就不开心,我要考得好他就不开心。总会有人不开心,何必戳破这层纸呢。

别了长沙的烟花,不知不觉来北京也有两个多月了,似乎一切还是刚来的样子。

跟风选了抽代,然后就发现我在作死了。作业答案就那么一行一句话,但是想却想了很久还不一定想得出来。 下学期的大物英电原感觉压力很大。

虽然和某人发生了奇怪的不太友好的事导致心情不好吧,但是还是有人会在我旁边的(这里得@大肉盾陪我走过不开心的时光)。我很开心有那么多的高中同学还记得我,这么信任我。

人际关系在慢慢建立中,虽然很多人都很少讲话。关系比较好的例如 hym、zhr ,当然也有关系紧张的。工作能力倒是有点低下,组长都当不好了。

参加了奇怪的赤足运动会,虽然没有拿奖,但是感觉尽力了。和@lz的两人三足,以及后来的10 * 60接力。虽然最后没分,可是也只能说尽力了。

不得不感慨THU的活动就是多。twb来宣讲,叉院各种活动,足球赛,辩论赛,虽然我没参加把,但是还是可以感觉到会占用很多时间。

阳光长跑已经开始了。三千米虽然不多,但是我也只能勉强及格的样子。每次拉着某盾去跑步,虽然速度被拖了下来但是也感觉不错。这就是所谓的存在感吧,我觉得我的存在能给别人带来一些好的改变,一些正能量,我才感受到我的存在感。(所以一开学时跟别人说找不到存在感他就不了解我对存在感的理解吧)

高中同学也组织骗几次聚餐,都感到很怀念。总能从高中同学那里找到安慰。不过那些还在所谓的怀念高中生活,说白了就是没适应大学生活吧。小伙伴们说没找到新的小伙伴,我情况也好不到哪里去。旧的不去新的不来,不要将我们忘了就好。

有人劝我不要太过于学雷锋。不过我有种心有余而力不足的感觉。看到别人不知所措,我也不知道该干些啥,只能口头上说几句安慰的话。

刷水多时间很多,自己都不知道怎么办。空间人人Feedly知乎日报主要就这几个不知道水了我多少时间。

寝室里的公共话题还是插不上嘴。大新闻什么的不喜欢造,访问量什么的不在意(那你写这篇文章的目的是啥233),奇怪的话题什么的我还未成年呢,哲学话题什么的脑子空空如也什么都编不出来。在茶园似乎奇怪的话题或者大新闻才是拉近距离的好方法,但是我都不喜欢……就这样吧。有人能相互绝对信任就好。(……包括愚人节?旧事莫提)

孤帆远影碧空尽,惟见长江天际流。

最近被各种 Deadline 虐成狗了。

既然 PE 的题解写不了了那就翻译一下吧。

PE-441

\[\sum_{n=1}^N \sum_{p=1}^n \sum_{q > p, (p, q) = 1, p + q >= n}^n \frac{1}{pq}\]

这里的 \(N = 10^7\)

PE-442

一个数 \(x\) 被称为 11-free 数,当且仅当 \(x\) 的任意一个子串都不是除 1 以外 11 的幂。例如 2404 和 13431 是 11-free, 而 911 和 4121331 不是的。

求第 \(10^{18}\) 个 11-free 数。

Read more »

\(\newcommand{\D}[0]{\mathrm{d}}\) 卡着第 50 名过……

谁来教教我如何用微积分算期望啊,我算着简直要疯了。。

Solution

其实只要算出这两个随机变量的 pdf 就好了。但是我觉得算起来特别恶心……主要是对这货不熟吧,时不时就卡住了。

首先算第一个的 pdf 。我们枚举累加器是在第 \(n\) 次累加时超过 1 ,我们计算出 \(n\) 个变量的和为 \(t\) 的 pdf \(f(x) = \frac{t^{n - 1}}{(n - 1)!}\) ,则第一个值的密度分布函数为 \[ \begin{aligned} P(x) & = \sum_{n = 1}^\infty \int_{1 - x}^{1} f(t) \D{t} \\ & = \sum_{n = 1}^\infty \int_{1 - x}^{1} \frac{t^{n - 1}}{(n - 1)!} \D{t} \\ & = \sum_{n = 1}^\infty \frac{1 - (1 - x)^n}{n!} \\ & = \sum_{n = 1}^\infty \frac{1}{n!} - \sum_{n = 1}^\infty \frac{(1 - x)^n}{n!} \\ & = (e - 1) - (e^{1 - x} - 1) \\ & = e - e^{1 - x} \\ \end{aligned} \]

第二个值的 pdf 就比较恶心了。还是同样的思想,我们令 \(g_n(x)\) 表示 \(n\) 个 0 到 1 的变量的和为 \(1 + x\) 的 pdf ,可以得到 \(g_1(x) = 0\) 。可以求出 \(g_n (x)\) 递推式:

\[ \begin{aligned} g_{n+1}(x) & = \int_{0}^x g_n(t) \D{t} + \int_{x}^1 f(t) \D{t} \\ & = \int_{0}^x g_n(t) \D{t} + \frac{1 - x^n}{n!} \\ \end{aligned} \]

求出 \(g_n(x)\) 通项似乎是比较困难的,但是注意,第二个值的 pdf 我们只关心 \(\sum_{n=1}^\infty g_n(x)\)

对于递推式 \(v_{n+1}(x) = \int_0^x v_n(t) \D{t}, v_{0}(x) = 1\) ,我们可以得到 \(v_n(x) = \frac{x^n}{n!}\) ,则 \(\sum_{n=0}^\infty v_n(x) = e^x\)

我们考虑 \(g_{n+1}(x) = \int_0^x g_n(t) \D{t} + \frac{1 - x^n}{n!}\) 里面的 \(\frac{1}{n!}\) 。这个数会被连续积分无数次,最后对 \(\sum_{n = 1}^\infty g_n (x)\) 的贡献是 \(\frac{e^x}{n!}\)\(\frac{x^n}{n!}\) 也会被积分无数次,注意到对于 \(k\) 来说,所有 \(x \leq k\)\(\frac{x^n}{n!}\) 积分时都会得到过一个 \(\frac{x^k}{k!}\) ,所以这部分对于和的贡献是 \(\sum_{k = 1}^\infty k \frac{x^k}{k!} = x e^x\) 。所以我们有: \[\sum_{n = 1}^\infty g_n(x) = \sum_{n = 1}^\infty \frac{e^x}{n!} - x e^x = e^x (e - 1 - x)\]

现在要开始求第二个值的 pdf 了。令 pdf 为 \(Q(x)\) ,则有 : \[Q(x) = \int_{1-x}^1 e^x(e-1-x)\D{x}\]

知道了 \(P(x)\)\(Q(x)\) ,答案就是:

\[ans = \int_{0}^1 Q(x) \int_0^x P(y) \D{y} \D{x}\]

\(Q(x)\)\(ans\) 的具体表达式我用的 sage 暴力算的,就没写出来了。

nonsense

看着 forum 里面各种高大上的积分感觉被虐傻了。

@dyh 求你的做法。

又在军训的时候想出一道题……

Problem

\(2n\) 个人,编号 1 到 \(2n\) ,每个人头上有一顶帽子,帽子要么是黑色的要么是白色的。现在这 \(2n\) 个人需要同时说出自己帽子的颜色,如果不少于 \(n\) 个人说对了自己帽子的颜色,则这局游戏获胜,否则失败。求是否存在必胜策略。

Read more »
0%