_rqy's Blog

最近两天，有感而发，遂书“杂记（贰）”以记录脑海中 OI 之片段，抒发心中所想。

从不知道什么时候开始就没有写过游记，回忆什么的；来到 thu 预科，这两天也闲了起来，又受 LCA 建议（LCA 说要了解一下 OIer 们），于是决定写一篇杂记，记录一下我还能回想起来的一些东西，以及随便写点东西。

虽然这篇文章叫做 “ 杂记（壹）”，但我也不知道以后会不会有“（贰）”或者更往后的东西了——或许我会逐渐把以前 OI 时的想法忘掉，或者也可能会咕咕咕了。

也不知道该写什么，想到什么写些什么算了。感觉也组织不起目录结构，就当作文写吧。我甚至连一些事情发生的前后关系都不记得了，写这篇文章的时候还查了好几次日期。另外这篇文章中可能提到了一些之前不想说的东西~~，就当我公开出柜了吧~~。反正也不是什么秘密了，应该已经有很多人知道了吧。

Description

给定小写字母组成的字符串 $s$ 及正整数 $m$，求有多少小写字母组成的字符串 $t$ 满足 $t$ 的无穷重复中存在一个和 $s$ 长度相同但比 $s$ 字典序小的子串。

$|s|,m\leq2000$。

在 OI 中会用到很多生成函数运算…比如求逆（本文中均指乘法逆，而非复合逆）、$\exp$、$\ln$、牛顿迭代、微积分、拉格朗日反演等。

那么就会有很多问题，比如：

1. 求逆（指乘法逆），$\ln,\exp$ 等生成函数运算在什么时候有定义？
2. 这些运算为什么满足我们所期待的性质，如 $\ln\exp A=A,\exp(A+B)=\exp A\cdot\exp B$？
3. 如果你了解过一些（分析意义上的）级数，你可能还会疑惑为什么会存在 $\sum_n n!x^n$ 这种东西（因为它只在 $x=0$ 时收敛）…

归根结底，我们所疑惑的关键在于：为什么可以对这些东西做这些运算？

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$。