CSP2019 Solutions

CSP2019 题解 代码早晚会有的。 ...

2019 年 11 月 17 日

LOJ3123 [CTS2019] 重复

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

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 日

ZOJ4058-4070 Solutions for QingDao ACM 2018

目前 H 不会写,K 不想写… ...

2018 年 11 月 7 日

LOJ565 [LR10] mathematican 的二进制

Description 一个初始为 0 的二进制数,有 $m$ 次操作。 第 $i$ 次操作是将这个二进制数加上 $2^{a_i}$ 。这个操作以 $p_i$ 的概率执行。 如果某次操作执行了并且修改了二进制数的 $k$ 位,那么它会带来 $k$ 的代价。 问代价和的期望,答案对 $998244353$ 取模。 $n=\max a_i\leqslant10^5, m\leqslant2\times10^5$ ...