「CF388D」Fox and Perfect Sets
题意定义一个集合 $S$ 是好的，当且仅当： 1. $\forall x\in S,y \in S $ 有 $x \oplus y \in S$，这里 $\oplus$ 是异或操作。 2. 集合最大值 $\leq n$求这样的集合的个数，模 $10 ^9+7$题解这是个好题（至少我觉得我是想不出来） 首先一个观察是这样的集合一定是由一组线性基生成出来的，我们只需要搞出一个让线性基和集合的一一...
题意定义一个集合 $S$ 是好的，当且仅当： 1. $\forall x\in S,y \in S $ 有 $x \oplus y \in S$，这里 $\oplus$ 是异或操作。 2. 集合最大值 $\leq n$求这样的集合的个数，模 $10 ^9+7$题解这是个好题（至少我觉得我是想不出来） 首先一个观察是这样的集合一定是由一组线性基生成出来的，我们只需要搞出一个让线性基和集合的一一...
题目大意给你一个长度为 $n$ 的序列，问你有多少种置换，使得置换后的序列相邻两项的乘积都不是平方数。题解这个题目好像比较厉害的样子。。首先把这些数按照是否能组成平方数分组，同一组里都是两两相乘能凑成平方数的，可以证明存在这样的分配方案。 然后我们可以设 $f_{i,j}$ 表示插入了前 $i$ 个组，有 $j$ 个不满足的相邻关系的方案数。 我们令 $tot$ 表示已经填完的个数，$sz$...
轮廓线 dp 也是一种状压，适用于一维特别大而另一维特别小的情况。 我们来从一道经典例题入手：求 $1 \times 2$ 的骨牌填满 $n \times m $ 的矩形的方案数。 如果 $n,m \leq 11$ 那么当然可以轻松状压了，但是如果 $n = 10^5$ ，我们就要考虑使用轮廓线 dp 了。 设 $f_{i,S}$ 表示我们填到第 $i$ 行，我们在状压的状态中记录下图红线上...
题目大意把 $n$ 个数分成 $k$ 个区间，每个区间的价值为区间内不同数字的个数，问价值和最大为多少。题解简单 dp：设 $f_{i,j}$ 表示前 $i$ 个数 分了 $j$ 段的价值和最大是多少。我们记 $cnt_{l,r}$ 表示 $[l,r]$ 的不同的数的数量，那么有转移朴素的转移是 $O(n^3)$ 的，我们观察这个式子，如果固定 $j$ ，我们用线段树维护 $f_k+cn...
DDP（动态 dp），是通过将状态改写成矩阵，然后定义具有结合律的与转移等价的运算，用数据结构快速维护的一种方法。在 NOIP2018 时作为 Day2 T3 出现。 NOIP2018 Day2T3 - 保卫王国 考场上根本不会...那个时候我是连暴力 dp 都不会的菜鸡，现在回来学一学。 我们来找一道简单的题目入手：给定一棵树，点有点权，每次可以修改一个点的权值，每次修改后求这棵树的最大独...