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

Description

对于两棵树 \(T_1, T_2\)，定义它们的交 \(T_1\cap T_2\) 是它们的边集的交形成的森林，\(k(T_1\cap T_2)\) 表示这个森林的连通块个数，求下列三种问题之一：

1. 给定 \(T_1, T_2\)，求 \(y^{k(T_1\cap T_2)}\)；
2. 给定 \(T_1\)，求 \(\sum_{T_2}y^{k(T_1\cap T_2)}\)；
3. 给定 \(n\)，求 \(\sum_{T_1}\sum_{T_2}y^{k(T_1\cap T_2)}\)

其中 \(n\leqslant 10^5\)，上面的 \(\sum\) 都是对所有可能的 \(n^{n-2}\) 种树求和。

答案对 \(998244353\) 取模。

Description

给定 \(n\) 个长为 \(m\) 的由 H 和 T 组成的串（表示硬币的正反面）。

不停地丢一枚均匀的硬币直到硬币序列的最后 \(m\) 位是 \(n\) 个字符串之一为止。

对每个串求最后以它结尾的概率。\(n,m\leqslant300\)。

Description

已知 \(m\) 次多项式函数 \(f\) 在 \(0,1\dots,m\) 处的取值 \(f(0),f(1),\dots,f(m)\)，给定 \(n,x\)，求

\[\left(\sum_{k=0}^n\binom nkf(k)x^k(1-x)^{n-k}\right)\bmod998244353\]

\(n\leqslant10^9,m\leqslant2\times10^4\)。

Description

令 \((1+\sqrt2)^n=e_n+f_n\sqrt2\)，其中 \(e_n, f_n\) 都是整数。

再令 \(g_n=\mathop{\rm lcm}_{i=1}^n f_i\)。

给定 \(n, p\)，求 \(\left(\sum_{i=1}^n ig_i\right)\bmod p\)。

数据组数 \(T\leqslant210,n\leqslant10^6,2\leqslant p\leqslant10^9+7\)，\(p\) 是质数，\(f_1\dots f_n\) 在 \(\bmod p\) 意义下不为 \(0\)。

Description

有若干药瓶，第 \(i\) 号药瓶里装着 \(g_i\) 克 \(i\) 号物质。

有 \(m\) 次操作，第 \(i\) 次会把 \(a_i\) 号瓶子全部倒入 \(b_i\) 号瓶子，之后 \(a_i\) 号瓶子不会再用到。

一共 \(k\) 对物质之间会反应生成沉淀（沉淀不再参与反应），1 克 \(c_i\) 物质和 1 克 \(d_i\) 物质反应生成 2 克沉淀。

当有若干反应都可以进行的时候优先进行编号小的反应。求整个过程中一共生成了多少沉淀。

\(m<n\leqslant2\times10^5,k\leqslant5\times10^5\)。

Description

给出一棵 \(n\) 个结点的树，要求给每个点一个正整数权值，使得相邻的结点的权值不相等，且最小化权值和。

\(n\leqslant10^4\)。

目前 H 不会写，K 不想写…

Description

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

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

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

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

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

生成函数

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