本文介绍_rqy的OI中的代码规范。其来源主要为_rqy的长期积累及参考Google代码规范、Menci的规范。
LOJ3123 [CTS2019] 重复
Description
给定小写字母组成的字符串 \(s\) 及正整数 \(m\)，求有多少小写字母组成的字符串 \(t\) 满足 \(t\) 的无穷重复中存在一个和 \(s\) 长度相同但比 \(s\) 字典序小的子串。
\(|s|,m\leq2000\)。
浅谈 OI 中常用的一些生成函数运算的合法与正确性
在 OI 中会用到很多生成函数运算…比如求逆（本文中均指乘法逆，而非复合逆）、\(\exp\)、\(\ln\)、牛顿迭代、微积分、拉格朗日反演等。
那么就会有很多问题，比如：
- 求逆（指乘法逆），\(\ln,\exp\) 等生成函数运算在什么时候有定义？
- 这些运算为什么满足我们所期待的性质，如 \(\ln\exp A=A,\exp(A+B)=\exp A\cdot\exp B\)？
- 如果你了解过一些（分析意义上的）级数，你可能还会疑惑为什么会存在 \(\sum_n n!x^n\) 这种东西（因为它只在 \(x=0\) 时收敛）…
归根结底，我们所疑惑的关键在于：为什么可以对这些东西做这些运算？
BZOJ5475 [WC2019] 数树
Description
对于两棵树 \(T_1, T_2\)，定义它们的交 \(T_1\cap T_2\) 是它们的边集的交形成的森林，\(k(T_1\cap T_2)\) 表示这个森林的连通块个数，求下列三种问题之一：
- 给定 \(T_1, T_2\)，求 \(y^{k(T_1\cap T_2)}\)；
- 给定 \(T_1\)，求 \(\sum_{T_2}y^{k(T_1\cap T_2)}\)；
- 给定 \(n\)，求 \(\sum_{T_1}\sum_{T_2}y^{k(T_1\cap T_2)}\)
其中 \(n\leqslant 10^5\)，上面的 \(\sum\) 都是对所有可能的 \(n^{n-2}\) 种树求和。
答案对 \(998244353\) 取模。
BZOJ4820 [SDOI2017] 硬币游戏
Description
给定 \(n\) 个长为 \(m\) 的由 H 和 T 组成的串（表示硬币的正反面）。
不停地丢一枚均匀的硬币直到硬币序列的最后 \(m\) 位是 \(n\) 个字符串之一为止。
对每个串求最后以它结尾的概率。\(n,m\leqslant300\)。
BZOJ4734 [清华集训2016] 如何优雅地求和
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\)。
BZOJ4833 [Lydsy1704月赛] 最小公倍佩尔数
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\)。
BZOJ3712 [PA2014] Filoki
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\)。