【省选模拟】20/06/08

本文主要是介绍【省选模拟】20/06/08，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$A$

• 考虑容斥，1表示钦定选，0 的位置表示 0/1 均合法，这样的好处是可以只考虑 1 的限制
  并且最后我们只需对超集容斥就可以得到答案
  发现钦定一些 1 选的意义就是在原图上选若干条不相交的链，复杂度和拆分数有关
  预处理一个集合有多少条链，那么就是一个子集卷积
  并且发现只用求出最后一项，所以可以 $O(2^n)$ 暴力容斥回去
  复杂度 $O(n^2{2}^n+p(n)2^n)$，$p(n)$ 为拆分数，$Code$

$B$

• 考虑在 $S_{l,r}$ 的前后加字符，求的就是本质不同的方案数
  在前面的方案数对应的就是子树中后缀结点的 $le{n}_u-le{n}_{lin{k}_u}$
  下面要求出在后面加字符的方案数，用后缀数组求出本质不同的个数，启发式合并
  $Code$

$C$

• 显然转移可以写成如下形式
  $$\frac{f_i}{i}=\sum _{j=1}^i{f}_{j-1}{f}_{i-j}{x}^{\min (j,i-j+1)}$$
  发现项数是 750 左右，可以将其视为 $O(n)$，复杂度 $O(n^3)$
  $Code$

这篇关于【省选模拟】20/06/08的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---