脚本宝典收集整理的这篇文章主要介绍了2021.12.11 互测，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
北校哥哥们出的互测题。
又是写完暴力就不知道干些什么了。
人老了，已经不会写这么精致的 DP 了。
首先将 (a) 排列固定为 (1,2,dots n)，DP (b) 排列的方案数，最后乘 (n!)。
发现每填一个数，代价取决于较大数，也就是从前往后放，数字 (i) 往 (1dots i) 位置放时计算一下代价；而前面哪些位置能放，只关心合法位置的数量。
DP 设 (f(i,j,k)) 表示前 (i) 个数中有 (j) 个数已经确定了位置，代价和为 (k)。枚举数字 (i+1) 是不动、往前放、往后放，再枚举位置 (i+1) 是小数填、大数填，分 5 种情况转移。
复杂度 (mathcal O(n^2m))。
先建 kruskal 重构树，每次询问二分答案，再在树上倍增算出覆盖点数，(mathcal O(qlog^2 n))。
哦还可以整体二分，用可撤销的并查集。复杂度不变，但是并查集那个 (log) 要小得多。
zx 怎么搬 Ynoi 啊。
看起来是个找性质题，等会儿补。
学傻了，这点性质都看不出来。
所有数肯定是先 (bmod 2)。尝试枚举行集合，如果这些行异或起来全为 (0)，那么不能存在合法的列集合；否则 (2^m) 种列集合方案中有一半的集合是合法的。
那么要求行异或起来不为 (0) 的方案数。反过来求行异或起来为 (0) 的方案数，考虑先建立线性基，线性基外任何一个集合的异或和，都可以被线性基的一个子集表示。设线性基大小 (c)，那么方案数就是 (2^n-2^{n-c})。
需要用 (texttt{std::bitset<>}) 优化一下，复杂度 (mathcal Oleft(frac{nm^2}{omega}right))。
以上是脚本宝典为你收集整理的2021.12.11 互测全部内容，希望文章能够帮你解决2021.12.11 互测所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。