Description

$\rm Link$

Solution

做完这道题感觉对树状数组偏序计数有了全新的认识...🚀

看了 $\sout{\rm{lsqs}}$ 的博客才知道自己容斥原理学的不够深
容斥大概是计数中非常重要的了。以前都是式子直接用，核心的层次大抵是没有接触到，证明的过程也很少看。所以总结一些比较基础的知识和证明过程。以后式子用起来希望能更有底气。🙏

原始公式

Description

给定一张 $n$ 个点 $m$ 条边的图，一条边 $(u,v)$ 有 $\frac{1}{3}$ 的概率消失，$\frac{1}{3}$ 的概率定向成 $u\rightarrow v$ ，$\frac{1}{3}$ 的概率定向成 $v\rightarrow u$ 。求最后的图是 $\rm{DAG}$ 的概率。

$n\leq 20,m\leq \frac{n(n-1)}{2}$

Solution

一个不会整数划分的 sb 的自救

考虑一个这样的问题：给定 $n,m$ ，求将 $m$ 划分成不超过 $n$ 个从 $1$ 开始值域连续的整数的和的方案数。

有一个很明显的做法：设 $f_{i,j,k}$ 表示用了 $i$ 个数，总和为 $j$ ，目前最大数为 $k$ 的方案数。转移比较明显：

Description

$\text{Link}$

Solution

西哥挖坟挖出来一道神仙题。

笛卡尔树是个神仙东西。
$\text{Daniel}$ 神仙出了两道相关的题目，两道题目都巧妙地运用了笛卡尔树的优异性质。
这里总结一下关键的内容。

Description

给定 $n, d_1, d_2$ ，请在 $2n\times 2n$ 的网格中找到 $n^2$ 个点，满足任意两点间的距离的平方既不为 $d_1$ 也不为 $d_2$ 。
注意网格的横纵坐标范围是 $[0,2n)$ 。
$1\leq n\leq 300,1\leq d_1,d_2\leq 2\times 10^5$

Description

$\text{Link}$

Solution

网络流解方程。

刚了一道题超级久...最后 solution 给的做法是 FWT 。觉得做法还挺妙的。
顺带讲讲对 FWT 的理解，怕自己又不记得了。

原理

Description

给定两个 $1\sim n$ 的排列 $p$ 和 $q$ ，其中有些位置未知，用 $0$ 表示。
定义两个排列之间的相似度是：每次从 $p$ 中选择两个元素交换，使其变成 $q$ 的最小次数。
现在要求不全这两个序列，求出对于 $i\in [0,n-1]$ ，补全后相似度为 $i$ 的方案数。