Solutions

[省选联考 2020 A 卷] 组合数问题 题目描述 给定整数 $n$ , $x$ , $p$ ，一个 $m$ 次多项式 $f(k) = a_0 + a_1k + a_2k^2 + \cdots + a_mk^m$ ，计算 $$\left(\sum_{k=0}^{n}f(k)\times x^k\times \binom{n}{k}\right)\bmod p $$ $1\le n, …

Jayun 发布于 2024-02-23 10:25:17

00

题意 给定一棵树，在树上选 3 个点，要求两两距离相等，求方案数。 $n\leq5000$ 。 题解 枚举中间点，设 $f_i,g_i,h_i$ 分别表示深度 $i$ 时扫过的子树中选 1、2 个点的方案数和当前子树选一个点的方案数。 代码 const int N = 5010; inline ll Read() { ll x = 0, f = 1; char c = getcha …

Jayun 发布于 2024-02-22 21:38:27

00

[ARC114F] Permutation Division 题面 给定一个 $1\sim n$ 的排列。 Alice 要把它分成 $k$ 段，Bob 要把这 $k$ 段重排使得字典序最大。 问 Alice 的所有划分方式中最终得到的字典序最小的排列是什么。 $k\le n\le 2\times10^5$ 。 题解 让原排列和新排列 LCS 尽量长。二分之，在 $[1,x]$ 内 …

Jayun 发布于 2024-02-22 20:31:15

00

[ICPC2018 WF] Gem Island 题面 有 $n$ 个人，最开始每个人手中有 $1$ 颗绿宝石，每天晚上，会随机选一个绿宝石分裂为两个。 求 $d$ 个晚上后绿宝石数量最多的 $r$ 个人的绿宝石数和的期望值。 $1 \le n,d \le 500$ ， $1 \le r\le n$ 。 题解 设最终第 $i$ 个人有 $a_i$ 个宝石，可知其概率 $$ …

Jayun 发布于 2024-02-22 11:56:42

00

题目大意 给定一棵树和两组 01 权值，求对这棵树重标号后，第一组权值和第二组权值最小不同数。 $n\leq700$ 。 题解 真是一场酣畅淋漓的写题啊！ 处理无根树的方式与 P4895 独钓寒江雪 一样，重心作根，两个重心就新开个点向两中心连边；哈希也与之相同。 有根后设 $f_{x,y}$ 表示在子树 $x,y$ 同构的条件下，二者权值最小不同数。考虑转移， $x,y$ 同构而它们 …

Jayun 发布于 2024-02-21 21:06:56

00

[BalkanOI2018] Election 题目描述 有一个长度为 $N$ 的字符串 $S[1\dots N]$ ，它仅由 C 和 T 两种字母组成。 现在有 $Q$ 个查询，每个查询包含两个整数 $L$ 和 $R$ ，表示：设新字符串 $S'=S[L\dots R]$ ，至少在 $S'$ 中要删除多少个字符，才能保证：对于 $S'$ 的每一个前缀和后缀，其 C 的数 …

Jayun 发布于 2024-02-21 15:04:24

00

题面 定义一个好的 $01$ 串 $\mathcal{S}$ 满足以下条件： $\mathcal{S}$ 非空。 $\mathcal{S}$ 的任意一个前缀 $\mathcal {S}[1\dots p](p\in [1,|$ $\mathcal S$ $|])$ 中， $0$ 的数量都不多于 $1$ 的数量。 $\mathcal{S}$ 的任意一个后 …

Jayun 发布于 2024-02-21 14:59:30

00

独钓寒江雪 题目描述 给定一棵无根树，求其中本质不同的独立集的个数对 $10^9+7$ 取模的结果。 $n \leq 5\times 10^5$ 。 题解 若有根，明显 DP， $f_{u,0/1}$ 表点 $u$ 选否个数。无根，寻重心以为根，有二则添点向之连边。以哈希判同构，是以组合。 得 beginend 哈希法： for (int i = 1; i <= tot; i++ …

Jayun 发布于 2024-02-20 21:59:20

00

题目 给定两个整数序列 $A$ 和 $B$ ，长度分别为 $n$ 和 $m$ ，且满足 $1\leq A_i,B_i\leq k$ 。现在你希望求出一个满足 $1\leq C_i\leq k$ 的整数序列 $C$ ，它既不是 $A$ 的子序列，也不是 $B$ 的子序列。求 $C$ 的最小长度。 题解 设 $f_{i,j}$ 表示扫完 $A_i,B_j$ 时 …

Jayun 发布于 2024-02-20 14:44:49

00

Pairwise Modulo 题面 给定一个由不同数组成的序列 $a$ ，定义 $p_k$ 为： $$p_k = \sum_{i=1}^k \sum_{j=1}^k a_i \bmod a_j $$ 其中 $a_i \bmod a_j$ 表示 $a_i$ 除以 $a_j$ 的余数。对于每个 $i \in [1,n]$ ，求出 $p_i$ 。 $2\le n \le 2 \ …

Jayun 发布于 2024-02-20 09:25:03

00