状压DP

今日继续垫底系列 T1题意理解错误暴力写挂 T2怒敲 $n \le 4$ 求根公式然后发现答案还得排序。。 $\text{score：0 + 10 + 0 = 10 rk：27/27}$ Problem A：游戏题目描述ysgh是一名Herthstone大师。现在他遇到了一个很严峻的问题： 场上总共有 $n+m$ 个随从，其中ysgh控制着 $n$ 个，对手控制着 $m$ 个。每个随从有自己的血量。 如果ysgh在这一回合成功解掉了对手的所有随从，则ysgh获胜。否则下一回合对手直接骑脸，ysgh就会输掉。 ysgh现在手里仅有一场牌，属性如下： 进行 $d$ 次，每一次等概率随机一个在场上的未死亡随从（包括自己和对手的）并且对其造成一点伤害。若不存在未死亡随从，则不进行此次攻击。一个随从未死亡当且仅当其血量严格大于 $0$。每一次攻击后，所有血量小于等于 $0$ 的随从立即死亡。 ysgh想要知道，他有多大概率可以取胜，也就是多大的概率使得在使用这张牌后，对手的随从全部死亡。 特别提醒：由于描述与实际游戏规则有出入，一切以实际题面描述为准。 数据范围对于所有测试数据，满足 $1 ...

后面发现这是某次考试的原题来着 怕是太久没打过状压然后连 $k \le 5$ 可能要状压这么明显的提示都给无视了然后就随便敲了个矩阵树骗了 $50$。。。 好所以这题是一道状压 令 $state$ 表示对于 $i$ 点（包括它本身）的前 $k$ 个点的连通状态，$e.g. \{1, 1, 2\}$ 表示 $\{1, 2\}, \{3\}$ 点分别连通 注意为了去重要用最小表示，于是即使当 $k = 5$ 时状态数也不过就 $52$ 个而已了 再令 $f_{i, j}$ 表示前 $i$ 个点且 $i$ 点连通状态为 $j$ 时的方案数，$g_{i, j}$ 表示状态 $i$ 转移到状态 $j$ 时的方案数，则有方程$$f_{i, j} = \sum_k f_{i - 1, k} * g_{k, j}$$可以发现这就是一个矩阵转移式，故直接矩阵乘法即可 那么至于计算 $g_{i, j}$ 则枚举 $i$，及当前点与前面点的连通状态 $state$（二进制表示），然后并查集维护一下，判断当前 $state$ 是否会与之前冲突（连边后无环且原状态中的最前点（即会被刷掉的点）与当前的 $k$ ...