<h1>2019.11.05 模拟赛总结</h1>

<h2>赛时</h2>

开场看了 T1，发现实质上是对完全图求 $n-1$ 完备匹配，求完后就删掉。发现自己只会暴力（其实是构造题想不出来），就去看了 T2
T2 一开始感觉和树堆那个题差不多...?但是发现其实这个性质是不独立的 ，写了写代码发现了不独立之后，就只有链的分了。
由于肝 T2 花费了大量时间，没好好看 T3，写了个大众暴力
最后 30+40+30 = 100，三题暴力光荣省三

<h2>题解</h2>

<h3>A. 小 D 与原题</h3>

一开始肯定都想过 $\frac{n}{2}$ 的构造，大概是将左边的转一圈。
然后我们考虑这种操作，本质上可以看成是一些数旋转后按照某一个中心点做对称，对称的就匹配起来。
如果 $4|n$ ，这显然是对的，但是如果不满足的话，就会出现一个点自己匹配到自己，我们将这个点和最后一个点删除，就变成了 $4|n$ 的子问题，直接构造就可以了。
代码

<h3>B. 小 D 与随机</h3>

感觉是全场最难的题了...每一个 Subtask 都是有启发意义的

<h4>Subtask1</h4>

这里要求 $n \leq 20$。
没有给 $O(n!)$ 的分感觉很不爽，但是也只能这样了。
这里介绍一种 $O(3^n)$ 做法（虽然过不了不过复杂度不带阶乘了）
我们考虑先枚举哪些点是好点，然后我们可以按照点之间的权值大小关系建出一个有向图。我们考虑这个图实际上是一个外向树+一些内向边组成的。如果没有内向边，每个节点成立的概率就是 $\frac{1}{sz}$。（一个来自树堆的结论）。
我们考虑外向树容斥：容斥掉向上的边。这样我们枚举边集，一部分变成向下一部分直接扔掉算一下答案即可。
这种方法实际上是可以导出正解的（把这东西 dp 出来），可是蒟蒻太菜了不会，如果有大佬会可以评论区教我[可怜]

<h4>Subtask2</h4>

这里保证是一条链。
也就是点都独立，直接 $f_i = (\frac{k}{sz}+\frac{sz-1}{sz})f_{i+1}$ 就可以了。

<h4>Subtask3</h4>

也就是正解了...
考虑最终答案一定是形如 $\sum_{i=0}^n x_ik^i$ 的形式。发现直接 dp，我们转移的时候就必须要记录这个状态的好点个数。

我们考虑如何去掉：如果没有这个 $k$ 的话我们可以考虑用 $[\geq k]-[geq k+1] = [=k]$，但是现在有个底数了，我们考虑如何类似的去掉。

考虑某一项 $k^m$ 可以有 $k^m = \sum_{i=0}^m \binom m i (k-1)^i$。

考虑对于后面的每一项 $(k-1)^i$，它都会被算它的超集个数次。考虑原先 dp 直接转移错误在这两个状态合并后的点可能不是一样的（即，你不能快速算出有 k 个好点的个数），但是这样我们相当于将 k 减一之后就可以将 $>k$ 造成的方案变化算在这上面了。
之后的 dp..:
对于每一个方案，它的贡献是它的方案数乘上 $k^{|S|}$。一个经典套路是如果你转移到了使用这个点就全都乘上 $k$。
现在我们可以 dp 了：设$f_{v,i}$ 表示考虑 v 子树，最小的好点的排名是 $i$
为什么…?
因为我们可以看成每次考虑根节点加和不加（就可以考虑出所有情况），根节点如果加入，那么子树内所有好点都要比它大。
然后按照定义转移..
合并：
暴力：枚举原序列最小排名 $p$，新序列最小排名 $q$，我们钦定前者作为新的最小值，那么最小值的取值就是 $[p,p+q-1]$
考虑转移系数：我们让 $k$ 表示合并后的最小值，那么
$$f_{v,k} = \binom {k-1} {p-1} \binom {sz-k} {sz_x-p} f_{v,p} f_{to,q} $$
因为 $f$ 是需要有序的，所以转移时只需要考虑它们之间的相对位置关系，不需要考虑到底选择了哪些数（到根的时候所有点都被考虑了）。
优化：考虑枚举 $p,k$，可行的 $q \geq k-p+1$，可以后缀和优化
但是现在还有个小 bug：我们状态没有考虑转移时子树为空的情况，事实上任意一种情况都可以和这个情况合并，所以后缀和全体加上 $sz[y]!$
最后考虑加入当前的点，在 $f_{v,i}$ 加入时讨论一下：

1. 通过在 $f_{v,i-1}$ 中作为一个前面的白点得到，转移系数为 $(i-1)$（有 $i-1$ 个空）
2. 自己作第 $i$ 个黑点，转移系数为 $k$（看成单点和树合并，也需要后缀和）
3. 考虑空子树的插入：直接是 $k*(sz-1)!$

代码

<h3>C. 小 D 与游戏</h3>

首先特判掉全都相同的情况（答案是 1）和 $len \leq 3$ 的情况（爆搜）
然后考虑 $len \geq 4$ 时，把 abc 看成 012，他们的和 mod3 并没有发生改变。换一句话：我们需要记和为 x 的序列的数量。
可以设 $f_{i,j,k,0/1}$ 表示考虑到第 $i$ 位，和 mod3 为 $j$，这一位是 $k$，前面是否有相同的连续段，按照定义转移即可。
如果一开始两两都不相同要额外特判一下（因为我们这个 dp 只会记录有连续段的情况）
代码

<h2>总结</h2>

1. 自己太菜了，还要努力
2. T1 这种构造题没切掉，太菜了
3. T2 应该第一时间意识到不独立去搞别的题的。。。事实证明我尝试搞出最难的题，但是没啥用，那个让 $k$ 转化为 $k-1$ 然后求联通块贡献的方法挺强的，并且组合计数的时候也要找对到底要记什么，dp 的时候也要考虑加入新点/合并的时候的判断依据，不要记录无用状态/漏记有用状态
4. T3 这种题目感觉不是很难...但就是不能抓题目性质，如果能证明一种序列和一种性质充要的话，通常我们会考虑将这个性质放在状态里进行 dp
5. CSP2019.rp++

<h3>附：关于 T2 一类容斥的理解</h3>

一般情况下，我们是限制了 $[x=k]$ ，有时候我们只能快速求 $[x \geq k]$ 的方案数，那么我们就可以减一下就的出来正确的结果了。
所以当我们注意到最终答案一定是形如 $\sum_{i=0}^n x_ik^i$ 的时候（$x_i$ 表示恰好 $i$ 个好点的方案数），展开可以得到 $\sum_{i=0}^n x_i \sum_{j=0}^i \binom i j (k-1)^j$ ，整理一下：
$$\sum_{i=0}^n (k-1)^i \sum_{j=i}^n x_j \binom j i$$
还是枚举了大于其的所有子集，那么考虑对这个进行 dp：我们合并的时候 考虑状态中 $(k-1)^i$ 前面的系数，其实是可以任意去合并的，不需要考虑个数（因为即使合并后会产生新点，这也会作为超集方案被算进去）
好难啊...
所以以后看到 $k^m$ 就可以直接枚举每种集合 求超集个数 乘 $(k-1)^m$ 了