本文介绍_rqy的OI中的代码规范。其来源主要为_rqy的长期积累及参考Google代码规范、Menci的规范。

Description

一个初始为 0 的二进制数，有 \(m\) 次操作。

第 \(i\) 次操作是将这个二进制数加上 \(2^{a_i}\) 。这个操作以 \(p_i\) 的概率执行。

如果某次操作执行了并且修改了二进制数的 \(k\) 位，那么它会带来 \(k\) 的代价。

问代价和的期望，答案对 \(998244353\) 取模。

\(n=\max a_i\leqslant10^5, m\leqslant2\times10^5\)

生成函数

生成函数(generating function)又称母函数，是处理组合数学问题的一大利器。

Description

一棵 \(n\) 个结点的树。初始时 \(a\) 和 \(b\) 是黑的，其他点是白的。

每次可以把某个黑点染成红的并把与它相邻的白点染成黑的。

问把结点染红的顺序有多少种。

\(1\leqslant a,b\leqslant n\leqslant234567\)

答案对 \(998244353\) 取模，时限 10s 。

由于此游记咕了一星期，不保证其内容完全正确

Description

有一列数 \(a_i\) ，有 \(Q\) 个操作：

1. 对于某个 \(i\) ，以 \(p\) 的概率使 \(a_i\) 减一（若 \(a_i=0\) 则忽略）；
2. 指定某些 \(a_i\) ，从这些 \(a_i\) 中的所有大于零的位置随机选一个，对于每个 \(a_i\) 你需要求出选到它的概率。

你还要求出每个 \(a_i\) 执行完所有操作后的期望。

令 \(C\) 为 2 操作的数量：

\(n\leqslant200,Q\leqslant2\times10^5,C\leqslant10^3;\) 初始时 \(a_i\leqslant100\) 。

时限 6s 。

Description

令 d(i) 表示 \(i\) 的约数个数。

求 \(\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk)\) 。

\(A,B,C\leqslant10^5\) 。

Description

平面上有一个直线导轨，和 \(n\) 个挡板（线段）。现在你可以在直线导轨上的某个位置放置一个长度为 \(L\) 的激光发射器；它会以垂直于导轨的方向（向两边）发射激光。激光打到挡板上时会被吸收。

挡板间不相交，挡板和导轨不相交；挡板所在直线和导轨夹角不超过 \(85^\circ\) 。

最大化吸收到激光的挡板总长。（只计算被激光照到的部分；计算这部分的挡板长度而不是激光宽度）

\(n\leqslant10^4, L\leqslant2\times10^9\) ，所有坐标绝对值 \(\leqslant10^9\) 。

多组数据，数据组数 \(T\leqslant100\) ，时限 10s 。

Description

一个 \(n\) 个点 \(m\) 条边的无向连通图，\(q\) 次询问。每次询问给出一个集合 \(S\) ，问有多少结点 \(x\) 满足：

1. \(x\not\in S\);
2. 删除结点 \(x\) 及与其相连的所有边之后， \(S\) 中的点不连通。

\(n,q\leqslant10^5;m,\sum|S|\leqslant2\times10^5\) 。

多组数据，数组组数 \(T\leqslant10\) ；时限 \(10s\) 。

Description

有一个非负整数 \(x\) 。你要执行 \(m\) 次操作，每次操作是 x = randint(0, x) （ = 表示赋值， randint(0, x) 均匀随机地在 \([0, x]\) 中取一个整数）。

现在已知初始的 \(x\) 会随机在 \([0, n]\) 取值，且取 \(i\) 的概率是 \(p_i\) ，求最后取到 \([0, n]\) 每个数的概率。

\[n\leqslant10^5, m\leqslant10^8\] 。