好久没做题了似乎，最近被抽代虐的有点发慌。

Problem

令 \(a_n\) 为 \(x^3 - 2^n x^2 + n = 0\) 最大的一个实数根，求 \[\sum_{i=1}^{30} \lfloor {a_i^{987654321}} \rfloor\]

开学了～

Problem

求 \([1, 10^8]\) 内满足存在一个原根 \(g\) 且 \(1 + g \equiv g^2 \mod{p}\) 的素数 \(p\) 的和。

\(\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\) 个人说对了自己帽子的颜色，则这局游戏获胜，否则失败。求是否存在必胜策略。

居然能在站军姿的时候 YY 出一道题……

Problem

有 \(n\) 个人，对于任意一个非空子集 \(S\) ，都存在一个人使得他在 \(S\) 中有偶数个朋友。求证 \(n\) 是偶数。

智商亟需拯救。 \(\newcommand{\D}[0]{\mathrm{d}}\)

Problem

@fotile 问的一个题，我将题目改了下描述：

\(n\) 个变量 \(x_1, x_2, \dots, x_n\) ，满足 \(0 \leq x_i\) 且 \(\sum x_i = 1\) 。求 \(x_i\) 中第 \(k\) 小值的期望。

听天由命的节奏？

Problem

Mathematics (60 pts + 10 bonus pts)

1 (5 pts)

一个人、一只狼、一头羊、一卷白菜要过河。如果人不在，狼会吃羊，羊会吃白菜。求过河方案。

2 (10 pts)

两个 \(8 \times 8\) 的棋盘，第一个棋盘 \((i, j)\) 为黑当且仅当 \(\frac{i}{2} \equiv \frac{j}{2} \mod{2}\) ，第二个棋盘 \((i, j)\) 为黑当且仅当 \(i \equiv j \mod{2}\) 。现在要求将第一个棋盘剪成若干块，然后重新组成第二个棋盘，问至少要剪成多少块，并证明最优性。

3 (10 pts)

求 \([1, 10^6]\) 内所有数字的数位和。

4 (10 pts)

\(n\) 个人，每个人有一个秘密，现在任意两个可以通过电话交流，每次交流后两人都知道了对方知道的所有的秘密。问至少要经过多少次交流才能使得每个人都知道所有秘密。

5 (15 pts)

A B 两点相距 1 个单位，现在你可以从 A 走 \(n\) 步到 B 去，每步必须走直线，且你到 B 的距离一定要减小。求你走的最长距离。

6 (10 pts + 10 bonus pts)

A B 两人玩游戏，A 被蒙上了眼睛。一个圆桌子上有 \(n\) 个硬币，每个硬币要么正面朝上要么反面朝上。两人轮流进行操作，每次操作如下：

1. A 选择若干个位置
2. B 旋转桌子
3. 翻转 A 选择位置上的若干个硬币

如果所有的硬币都是朝上的那就是 A 赢。否则 B 赢。

问题有三个：

1. (5 pts) 给出一个 \(n = 4\) 的必胜策略。所谓必胜策略是指无论初始状况怎么样，A 总是可以赢的策略。
2. (5 pts) 证明 \(n\) 是奇数时 A 不存在必胜策略。
3. (bonus 10 pts) 证明存在必胜策略，当且仅当 \(n\) 是 2 的整数次幂。

Physics (40 pts)

1 (5 pts)

画两个图的电场线。第一个图为一个金属空心球体内有一个正的点电荷，第二个图为外有一个正的点电荷。

2 (5 pts)

一个均匀绳子，长度为 \(L\) ，质量为 \(m\) ，下端刚好接触一个天平。现在开始自由下落。当天平上绳子的长度恰好为 \(x\) 时，求天平的超级罗瞬间读数。

3 (10 pts)

一个无穷网格，每条线段的电阻为 1 欧，求相邻两点之间的等效电阻的大小。

4 (10 pts)

将一个硬币抛起来，如果立起来的可能性为 \(\frac{1}{3}\) ，求硬币半径与厚度的关系。

5 (10 pts)

1. (5 pts) 一个质量为 \(M\) 的球上放一个质量为 \(m\) 的小球。将两个球从 1m 出自由落体，已知 \(M\) 远远大于 \(m\) ，求小球能弹多高。
2. (5 pts) 由第一问画出航天器借助行星来进行加速的原理。

所有碰撞均为完全弹性碰撞。

虽然是第五场了，可是这只是我做的第二场。前几场是 xlk 和 jzp 两人做的，他俩太可怕了。

Solutions

1001

没看题。

1002

暴力 BWT 逆变换后直接上后缀自动机就好了。

1003

代码题。

拆点，如果一个点是白色的，那么就在这个点的白点和它父亲的白点间连条边，否则就在这个点的黑点和他父亲的黑点间连条边。查询一个连通块的最大值相当于查询一个点所在子树内的最大值。用 LCT 维护一个点的祖先中，和他连续相同最近的点在哪里，剩下的就用路径来维护就好了。

1004

看了不会。

1005

贪心。每个点的权值为原来的权值加上所有和它相邻的边的权值的一半的和，从大往小贪心即可。

1006

记录个前缀和后直接做。

1007

水题。注意到位与位是独立的就好了。

1008

这个题原来是用来出 CF 的，但是被枪毙了。

考虑最优路径，要么是经过环要么不经过环。如果不经过环的话 \(f_{i, j, k}\) 表示从 \(i\) 到 \(j\) 走 \(k\) 步的最优解。枚举就好了。

经过环的话， \(g_{i, j, k}\) 表示从 \(i\) 到 \(j\) 走 \(2^k\) 最大路径平均值是多少。这个可以倍增处理出来。然后用 \(g_{i, j, T}\) ( \(t\) 是一个比较大的数) 来更新所有能从 \(j\) 到的 \(k\) 的 \(i\) 到 \(k\) 的答案。

1009

整数拆分。

wiki 中有个 五边形数定理 。

用五边形数定理暴力做就好了。

1010

这个题还是比较好玩的。

第一问，可以直接使用 CTSC 2008 D1T1 歌唱王国的结论，答案就是 \(\frac{m^n - 1}{m - 1}\) 对于 \(m - 1\) 需要特判。

第二问，令 \(f_i\) 表示现在已经得到了最后 \(i\) 个元素是不同的了，问期望还要加入有多少个元素才能使最后 \(n\) 个元素不同。

显然 \(f_n = 0\) 。另外还可以得到 \(f\) 的递推式： \[f_i = \frac{1}{m} \sum_{1 \leq j \leq i} f_j + \frac{m-i}{m} f_{i+1} + 1\]

考虑 \(f_i - f_{i+1}\) 。代入上面的式子后可以得到 \(\frac{m}{m-i}(f_{i - 1} - f_{i}) = f_i - f_{i+1}\) 。由于 \(f_0 - f_1 = 1\) 可以直接得到 \(f\) 的表达式。剩下的就是解一个一元一次方程了。

1011

HIT 给题解的人什么心态！！！

其实如果你曾经逛过这里的话会发现这就是道 原题 。

当然如果你逛过 xiaodao 博客的话会发现还有 更简单的做法 。

所以给题解的人是什么心态！！！

1012

其实这还是道原题，详情请见 论文 。

每次求一遍全局最小割，如果全局最小割不小于 \(k\) ，则这个点集就是 \(k\) 边连通的，否则把最小割里面的边全部删去，分成的两个连通块递归做下去即可。

当初做的时候加了一堆常数优化写的我好恶心。

ending

四处都是老二。

罚时太多没办法。

（其实我一直在等 Second Blood ?）

在看到之前你会以为这是啥 = =？

wiki 在 这里

其实就是一个公式罢了。刚刚才发现的，实在是太漂亮了： \[\int_0^1 \frac{1}{x^x} \mathrm{d} x = \sum_{n=1} \frac{1}{n^n}\]

从一个积分到一个求和，连续到离散，真是不错。

证明的话， wiki 上有吧，摘抄如下。

首先变形： \(x^{-x} = e^{-x \log x}\) 。展开有： \[x^{-x} =\sum_{n=0} \frac{(-x \log x)^n}{n!}\]

代入并提前 \(\sum\) ： \[\int_0^1 \frac{1}{x^x} \mathrm{d} x = \int_0^1 \sum_{n=0} \frac{(-x \log x)^n}{n!} \mathrm{d} x = \sum_{n=0} \frac{1}{n!} \int_0^1 (-x \log x)^n \mathrm{d}x\]

换元，令 \(x = e^{-\frac{t}{n+1}}, \mathrm{d} x = -\frac{e^{-\frac{t}{n+1}}}{n+1}\mathrm{d}t\) ， \(0 < t < \infty\) ： \[ \begin{array}{rcl} \int_0^1 (-x \log x)^n \mathrm{d}x & = & \int_0^\infty(e^{-\frac{t}{n+1}} \frac{t}{n+1})^n \frac{-e^{-\frac{t}{n+1}}}{n+1}\mathrm{d}t \\ & = & \frac{1}{(n+1)^{n+1}} \int_\infty^0 -e^{-t} t^n \mathrm{d} t \\ & = & \frac{n!}{(n+1)^{n+1}} \\ \end{array} \]

再次代入： \[ \begin{array}{rcl} \int_0^1 \frac{1}{x^x} \mathrm{d} x & = & \sum_{n=0} \frac{1}{n!} \int_0^1 (-x \log x)^n \mathrm{d}x \\ & = & \sum_{n=0} \frac{1}{n!} \frac{n!}{(n+1)^{n+1}} \\ & = & \sum_{n=1} \frac{1}{n^n} \\ \end{array} \]

好久没写东西了，都长草了。

上一个月也比较忙（借口），四处旅游中。

7.22 正式离校，走之前和谢老师吃了顿饭，然后给新高一小朋友讲十天的课吧收获 1k 。

然后去珠海参加西山居的比赛。不得不说西山居很良心，居然是考算法，TC 形式。没有看错题以及没有 FST 导致最后混了个 #2 还是不错的。收获 Surface PRO 128G 一台。最后送了老爸。

然后去西安旅游。去之前以为西安不好玩，一下子就可以玩完的，去了之后发现开始可以玩很多东西的，走的时候发现还有好多地方想去玩。

然后去郑州骗钱。骗完钱后就在郑州玩了就几天。说实话郑州不好玩，所以我的“郑州游记”非常搞笑：第一天手机上不了网，于是就不敢出去了；第二天原本准备去少林寺玩玩，结果这天要多校，前面坑了好多次的队友了，有点过意不去了，所以做多校去了 →→ ；第三天由于 wxd、gzp 在，最后 vani 也来了，还来了个专注搞笑的，本来以为会去各个地方玩玩的，但是最后上午聚齐的时候已经十二点了，就直接吃饭去了。下午就在 KTV 唱了两个小时的歌……然后我的郑州之旅到底到了几个地方 →→

现在在贵阳旅游，闲着无聊做了两个题 →_→

ProjectEuler-419

Problem

look and say 序列是这么个东西：第一个元素是 1 ；第二个元素是 11 ，表示上一个元素是 1 个 1 ；第三个元素是 21 ，表示上一个元素是 2 个 1；接下来几个分别是 1211, 111221, 312211, 13112221, 1113213211 。易知每个元素只包含 1、2、3 三个元素。求这个序列第 \(10^{12}\) 个元素中 1、2、3 的个数。答案取模。

Solution

以前只听说过这个序列，对它的性质一无所知……一开始往 DP 上面想，死活想不到状态。

但是我听说过一个常数叫做 Conway 常数，指的是这个序列的长度会不断递增，而且相邻两项的长度比会逼近一个常数，这个常数就是 Conway 常数。

这其实就是个提示。考虑一个序列，相邻两项比逼近一个常数，第一想法就是线性齐次递推式。然后就开始找关于 Conway 常数的资料。发现 Conway 常数是某个 71 次方程的唯一正实数解，那应该就是一个线性齐次递推式了。而且可以找到这个方程，但是对于求每个数字出现的次数感觉没啥帮助 →_→

继续找 Conway constant 的资料，然后就找到了一个神奇的定理： Cosmological Theorem 。这个定理讲的是 look and say 序列从第 8 项开始，每个元素就可以分成若干份，使得每一份都是某 92 份中的一个。相关资料： Wolfram 和 一个奇怪的网站

……我想你大概懂了。预处理出所有的 92 个基本子串，求出每个子串一次变换后会产生哪些子串。这就是一个矩阵乘法。求出每个子串出现的次数后一切就没了。

……不给我 Google 这题能做？

……不给我 Google 这题能做？

……不给我 Google 这题能做？

ProjectEuler-421

Problem

定义 \(s(n, m)\) 表示 \(n^{15}+1\) 的所有不同的小于 \(m\) 的质因子的和。例如 \(2^{15} + 1 = 3^2 \times 11 \times 331, s(2, 10) = 3, s(2, 1000) = 345\) 。

求 \[\sum_{n \leq 10^{11}} s(n, 10^8)\]

Solution

这个题被 dyh 拿来做 ZJOI 讲课用，但是当时给我看课件的时候我还不会 2333

对于一个素数 \(p\) ，我们的目标是求出有多少个 \(n\) 满足 \(p | (n^{15}+1)\) 。这相当于要求 \(n^{15} \equiv -1 \mod{p}\) 。令 \(g\) 为 \(p\) 的原根，可得 \(g^{\frac{p-1}{2}} \equiv -1 \mod{p}\) ，所以如果 \(n \equiv g^x \mod{p}\) ，有 \(15x \equiv \frac{p-1}{2} \mod{p-1}\) 。这是一个很简单的同余方程，解的个数为 \(gcd(15, \frac{p-1}{2})\) 。求出所有解后可以算出有多少个 \(n\) 满足要求。

似乎很简单的样子可我为啥当初就不会呢。

nonsense

Bootstrap3 发布了。这个模板里面有很多不兼容，哪天改改（flag 立的飞起）。

谁来证明下这个式子： \[\sqrt{1+2 \sqrt{1+3 \sqrt{1 + 4 \sqrt{1+ \dots}}}} = 3\]

我想了下，觉得比较显然，可就是 YY 不出一个严谨的证明。