![[LOJ#2540][PKUWC2018]随机算法(概率DP)](/uploads/reation/bcimg7.png)
[LOJ#2540][PKUWC2018]随机算法(概率DP)
场上数据很水，比较暴力的做法都可以过90分以上，下面说几个做法。1. 暴力枚举所有最大独立集，对每个独立集分别DP。复杂度玄学，但是由于最大独立集并不多，所以可以拿90.2. dp[S][k]表示考虑到排列的第k位，当前独立集为S的方案数，枚举第k+1位，根据是否与S相连转移到dp[S][k+1]或dp[S | a[k+1]][k+1]。$O(n^22^n)$3. dp[S]...
