yaohaoyou

题目传送器

更爽的阅读体验

感觉我的转化比较神秘，但是和官方题解应该本质一样。

手玩可以发现当 $a_x=2^x+2^y,a_y=2^y+2^z,a_z=2^x+2^z$ 时是无法钦定出操作顺序的，而此时这个数据又形成了类似于环状的结果，所以考虑将 $a$ 和操作顺序的 DAG 一一对应，下面令 $a_i\to a_j$ 表示 $a_i$ 的操作在 $a_j$ 之后。注意是状态作为图上的点而不是编号，比如说当 $a_1=a_2=a_3=7$ 时，$a_1,a_2,a_3$ 三个小点本质上相同，若连成完全图显然会有环，由于是同时操作，所以直接合并成一个大点即可。因此两个大点 $u,v$ 之间可以有 $2^{siz_u}$ 种连边方法，分别对应了 $v$ 的 $siz_v$ 个小点的 $2^{siz_u}$ 种 $a$。

不难发现 $a_i$ 一定是所有 $i\ni a_x$ 中最晚操作的，所以将 $a_i$ 连向所有的 $x,i\ni a_x$，会发现 $siz_x=1$ 的 $x$ 还需要确定是 $a_x=0$ 还是 $a_x=2^x$，这两种情况在 DAG 上都是孤立点，其他情况都已经完成了一一对应。接下来一步就比较神秘，可以将所有 $a_x=2^x$ 的点最后再确定，在 DAG 上的孤立点都钦定为 $a_x=0$。（这一步没看懂可以现继续往下看，最后就明白了）

dp 求 DAG 的过程本质就是将相同状态的小点合并成大点，然后对大点做 DAG 有标号计数。令 $f_i$ 表示有 $i$ 个小点的方案数，则转移枚举原来的小点数量 $j$ 和新形成的大点数量 $k$：

$f_i=\sum_{j=0}^{i-1}\sum_{k=1}^{i-j}(-1)^{k-1}f_j\binom{i}{j}{i-j \brace k}2^{jk}$

因为上面说过要特殊处理，所以当前的 dp 中是假设所有的 $siz_x=1$ 孤立点都是 $a_x=0$，为了计数 $a_x=2^x$ 的情况，答案并不是 $f_n$，而是 $\sum_{i=\color{red}0}^n\binom nif_i$，表示选出的 $i$ 个做 DAG 的 dp，剩余的 $n-i$ 个点都是 $a_x=2^x$。时间复杂度为 $\mathcal O(n^2)$。