CF1466H

首先题目说了合法分配是唯一的，所以我们考虑怎么找这个合法分配。

先将 (i) 喜欢 (j) 当作一条 (i o j) 的连边。

显然在仅考虑最优的连边时，这张图将构成基环内向树，根据非法分配的规则，我们发现此时所有的环是必须被选择的。否则这个子集必然是非法的。

此时考虑所有节点连向这些点的边均可以被删除，断开之后图将构成若干棵树，我们提取每棵树的根节点，并将次优的边连上，然后删除新的环，并断开节点与被删除的点的边。

重复此流程，显然我们可以得到唯一的一种最优分配方案。

考虑给定的序列 (A)，我们其实将边先连出来，将得到若干个环。

考虑之前的算法流程，我们删环的过程之间存在顺序关系，不妨以此来分层，我们假定将所有环按某个顺序删除，并钦定每个点与前一个点是处于同一层还是高一层，然后以此为基础计算答案，设环数为 (cnt)，可以得到一个 (mathcal O(cnt!cdot 2^{cnt})) 的做法。

考虑优化，首先同一层/高一层这个状态可以删除，不难观察到我们只需要知道上一层的环的大小之和即可。

其次，我们可以将 (mathcal O(cnt!)) 的部分省略，考虑计算答案的过程，我们只需要知道当前层被选了多少个元素（除掉这个的阶乘），上一层的权值和，以及总体的权值和即可计算当前点的贡献。（同时在转移到下一层的时候需要利用当前层的权值和，所以这个也要维护），同时钦定的顺序关系可以使用状压 dp 来替代，我们得到了一个 (mathcal O(2^{cnt}cdot n^5)) 的算法，一个观察是，当前被选择的元素确定了当前的权值和，可以优化到 (mathcal O(2^{cnt}cdot n^4))

接下来的观察是，相同大小的环不可区分，于是我们更换状态为确定每种大小的环在当前状态被选择了多少次，这样只需要将答案乘以每种大小的环的数量的阶乘即可。

借官方数据测了测，似乎状态数的最大值是 (1440)，所以复杂度可以当作是 (mathcal O(1440cdot n^4))？不过非常跑不满就对了，最慢的点(这个 (1440))似乎只跑了 300ms

有效的状态数是以下问题的最大值：

确定 (n) 个元素的取值 (c_i)，使得 (sum icdot c_i=n)，最大化 (prod (c_i+1))，借了个 dp 算了算，这个数列大概是 ({2,3,4,6,8,10,12,16,20,24...1440})（ http://oeis.org/A088881 ），即使到了 (n=100)，有效的状态数也只有 (201600)