杂记(贰)—— 回忆片段

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

2019 年 9 月 13 日

杂记(壹)—— OI 生涯回忆

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

2019 年 9 月 6 日

LOJ3123 [CTS2019] 重复

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

浅谈 OI 中常用的一些生成函数运算的合法与正确性

在 OI 中会用到很多生成函数运算…比如求逆(本文中均指乘法逆,而非复合逆)、$\exp$、$\ln$、牛顿迭代、微积分、拉格朗日反演等。 那么就会有很多问题,比如: ...

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

2018 年 12 月 26 日

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

2018 年 12 月 26 日

BZOJ1369 [Baltic2003] Gem

Description 给出一棵 $n$ 个结点的树,要求给每个点一个正整数权值,使得相邻的结点的权值不相等,且最小化权值和。 $n\leqslant10^4$。 ...

2018 年 12 月 26 日