[背包回退+二进制状压DP+NTT]2022牛客暑期多校训练营1 H【Fly】题解
题目概述Fly解题报告首先想到DP：$f_{i,j,0/1/2}$ 表示前 $i$ 个二进制位（从低位到高位），到 $i$ 这位时背包大小为 $j$ ，并且状态为 $0$ 小于 $1$ 相等 $...
2020 CCPC 长春站 部分题解
F. Strange Memory呜呜呜，想了半天怎么快速处理这个 $i\ \mathbb{xor}\ j$ ，之后发现其实根本没有好的处理方法，只能拆位计算贡献。考虑第 $B$ 位的贡献，那么...
[状压DP+复杂度优化]BZOJ4197(Noi2015)【寿司晚宴】题解
题目概述把 $[2,n]$ 分成两半（不需要全部选），求两边不存在不互质的数的方案数。解题报告如果素数个数少的话可以直接状压 $f_{s,t}$ 表示第一组的素数集合为 $s$ ，第二组的素数集...
[状压DP]NOIP2017Day2【宝藏】题解
解题报告吃我一记万年神坑。去年考场上做这题的时候一直在想二进制状压，现在回头看看那时候的自己真是蠢爆了。很明显可以三进制状压 $f_{i,s}$ 表示深度为 $i$ 时，每个点的状态 $0/1/...
[贪心+虚树+状压DP]51Nod1673【树有几多愁】题解
题目概述有一棵树，现在要给这棵树重编号，叶子节点的权值为到根路径的最小值，现在求叶子节点权值的积的最大值，保证叶子节点的个数不超过 $20$ 。解题报告可以想到这样的贪心：一个点的新编号肯定是子...
[状压DP]BZOJ2734(HNOI2012)【集合选数】题解
题目概述如果选了 $x$ 就不能选 $2x$ 和 $3x$ ，求 $1..n$ 满足条件的子集个数。解题报告这种神题完全做不来，一波转化日神仙： x 3x 9x ...
2x 6x 18x...
[状压DP+组合]LOJ2540(PKUWC 2018)【随机算法】题解
题目概述我们知道，求任意图的最大独立集是一类NP完全问题，目前还没有准确的多项式算法，但是有许多多项式复杂度的近似算法。例如，小C常用的一种算法是：对于一个 $n$ 个点的无向图，先等概率随机一...
