0103abc 的网站

来复读一下第一篇题解。 直接枚举所有排列显然你是不可行的，因此考虑枚举哪些边紧密相连。钦定若干条边相邻是简单的，因此考虑子集反演，给每条边染成黑 / 白 / 灰三种颜色，其中黑边要求强制相邻并保留在最终的连通块中，白边要求强制相邻且不保留到最终连通块中（贡献为...

从这里开始 写下你的想法。右侧是博客实际的排版，手机上可以切换到预览。

https://www.luogu.com.cn/record/307512191 https://codeforces.com/contest/2122/submission/397015963 https://codeforces.co...

~~题目名居然过审了，好神奇~~ Fibonacci 数列有经典结论 $\gcd(fa,fb)=f{\gcd(a,b)}$，因此考虑 gcd-lcm 反演，$\operatorname{lcm}(f{a1},f{a2},\ldots,f{a...

首先问题可以被转化为计数长度为 $n$ 的整数序列 $a$ 满足下面两个条件： $1\le ai\le bi$（$b_i$ 是所有对序列限制的上界） 序列恰好有 $k-1$ 个位置 $i$ 满足 $ai>a{i+1}$。 考虑 dp。设 $f{i,j}$ 表示当前考虑了前 $i$ 个位置，被切成了...

Official Solution. sol 1 sol: Lemansky Time：2024/05 首先看到 XOR 构造容易想到一个经典的套路：$2k\oplus(2k+1)=1$（partner），不妨把这样的组合称为 P。 先考虑无解的情况，显然 $x$ 的最高位不能超过...

Official Solution. 同样考虑 dp。设 $f{i,j}$ 表示因为其祖先结点不断失败，导致结点 $i$ 总共需要被重新通关 $j$ 次时，完成 $i$ 为根子树这一部分所需要的最小期望代价是多少。考虑如果 $i$ 需要成功 $j$ 次，因为单次成功的概率是 $\frac...

Official Solution. 因为 $n$ 个数最多有 $2^n$ 种选取方法，而需要覆盖的数的数量也是 $2^n$，这就告诉我们构造的序列 $a,b$ 需要满足所有的子集的异或均两两不同。 最小值 构造 $a_i=2^{i-1}$ 即可。很显然不能得到和更小的序列。 最大值 构造序列...

Official Solution. 设 $f_{i,0/1}$ 表示当前处理完了以 $i$ 为根的子树，且 $i$ 号结点通关，当前不在 / 在 $i$ 号点放存档，最小期望通关代价是多少。 显然对于通关概率为 $\frac1{pi}$ 的 $i$ 结点而言，期望需要花费 $pi$...

有向图博弈问题考虑从外侧不断删除必败状态。设 $W$ 为当前没有确定为必败的状态组成的集合。则考虑对每个点 $u$ 如果其属于 $A$ 集合那么只要存在一条出边通往 $W$ 集合即可；如果其属于 $B$ 集合必须保证其所有出边都能通往 $W$ 集合。设满足这个条件的充电站组成的集合为 $P$（即...