Universal OJ#450. 「集训队作业2018」复读机 – 题解

主要思路

首先对于 \(d = 1\),答案就是 \(k^n\)。

对于 \(d = 2\),其实发现可以用生成函数来直接乘:\( A(x) = \sum_{i = 0}^\infty \frac{1}{i!} x^i [2 | i] \),那么答案就是 \( A^k(x)[x^n] \)。发现可以变通奇偶性,所以 \(A(x) = \frac{e^x + e^{-x}}{2}\),然后试着二项式展开:

继续阅读Universal OJ#450. 「集训队作业2018」复读机 – 题解

「LibreOJ NOI Round #2」不等关系 – 题解

主要思路

这题好神仙啊。

首先介绍一个暴力的套路(虽然跟正解没关系,但我觉得碰上很多比赛的时候会用上):我们设置 \(f[i][j]\) 当前为前 \(i\) 个数中第 \(j\) 小的贡献,那么有

\[ f[i][j] = \begin{cases} \sum_{k = 1}^{i – 1} f[i – 1][k] (s_{i – 1} = <) \\ \sum_{k = i}^{j} f[i – 1][k] (s_{i – 1} = >) \end{cases} \]

继续阅读「LibreOJ NOI Round #2」不等关系 – 题解

Yali 模拟赛 #1 – 解题报告

A – 神奇的位运算

想了半天,最后一看是离线来维护,直接吐血。

首先大概能想到用本质不同的异或和与区间异或和进行异或得到答案。因为这样可以把出现次数为奇数次的给过滤掉并得到最终的答案。考虑如何得到本质不同的区间异或和,一种方式是使用主席树进行维护,另一种方式是进行离线维护。我们可以在树状数组中维护本质不同的前缀异或:我们把每个数往尽可能近的地方塞,这个时候就需要用 map 来判断要不要移动。

继续阅读Yali 模拟赛 #1 – 解题报告