Shu Yu Mo's blog

之后应该会按照算法分类，后面有一些题目没有补完…

第一天的题都是好题啊 QAQ!!

正睿十连测 Round 8 补题记录。 菜到去世……

结束了「学习总结」整数模 n 乘法群 之后，发现数论还有很多东西妹学。 (T__T). 一直没有发表

对于 任意 一个正整数 \(n\) ，\(1 \sim n\) 中与 \(n\) 互质的 \(\varphi(n)\) 个数字组成的集合记作 \(\mathbb{Z}^*_n\)。

事实上，由 \(\mathbb{Z}_n^*\) 和模 \(n\) 意义下的乘法组成的代数系统 \((\mathbb{Z}^*_n, \times )\) 是一个群。

从这一点出发理解原根和阶往往有很多奇妙的感受…

小 D 最近在网上发现了一款小游戏。游戏的规则如下：

wzy哥哥的一些有趣计数题~

容斥原理 用于解决一类，在已知任意 \(m\) 个集合交集大小的情况下，多个集合求并集大小的问题。

给出一个长度为 \(n\) 的数列 \(A_i\) ，求有多少个长度 \(k\) 的子序列 \(A'\) (\(k\ge 2\))满足： \[ \prod_{i=1}^{k-1}\dbinom{A'_i}{A'_{i+1}} > 0 \pmod{2} \] \(n \le 211985, A_i \le 233333\)。原题保证 \(A_i\) 互不相同，但是不重要。

构造题都是好题

给出长度为 \(n\) 的序列 \(a_i\) ，需要构造一个序列 \(b_i\) ，使得 \(\forall i, \exists x,y \in [1, n],s.t.b_x + b_y = a_i\) 要求输出序列 \(b_i\) 和方案（\(a_i\) 由哪两个 \(b_j\) 构成） 。无解输出 \(-1\). d3A

\(n \le 30\)

Mex 构造题 (P6852 )

给出一些限制，需要还原一个排列，限制形如：\([L, R]\) \(v\) ，表示排列 \([L, R]\) 的Mex 为 \(v\)。 给出任意一种构造方案. \(|P|\le 10^5\)

猜数游戏

给出一个长度为 \(n\) 的序列和一个正整数 \(p\)。

设 \(n\) 中的元素组成一个集合 \(A\)。

二人交互：

• 一人选出一个 \(A\) 的一个非空子集 \(S\) ，
• 另一人选出一个极小的集合 \(S' \subseteq S\)，满足：\(\forall\ x \in S, \exists \ y \in S', s.t. x=y^m \pmod{p}\),代价为 \(|S'|\).

求代价的期望 \(\times 2^{n}-1 \mod 998244353\)。

给定一个常数 \(C\) ，维护一个集合 \(S\) ，支持 \(n\) 次操作：

• 插入 \(x\)，保证之前不存在 \(x\)。
• 删除 \(x\) ，保证之前存在 \(x\)。

每次操作后输出 \(\max_{i, j\in S, i \not = j}\limits{(i + j) \mod C}\)。是指 \(\mod C\) 意义下的最大值。

强制在线。

卡特兰数的证明能够扩展到处理一类括号序列的问题上。不仅仅只是为了应付 sb 初赛。

壹月 贰月 叁月 里逛 U 群/水犇犇学到的一些有趣的知识。

后缀数组的一次复习和整理，大部分精简自oi-wiki。

一道 dp + 图论 + 状压好题

给出两个正整数 \(n, k\) 。

求出有多少个长度为 \(n\) 的括号序列，满足最长合法括号子序列长度恰好为 \(2k\) 。

倒是扩展了 FWT 的一种思路吧。