ABC214G/S2OJ1504

ABC214G/S2OJ1504

又是我不会的/hanx

做了一天/ng

直接做显然是不行的，所以考虑转化题意，对于 \(\forall i\) ，连边 \((A_i,B_i)\) ，现在题意就变成给边染色了，这样统计的就是不合法的，考虑容斥，一个很 \(\text{naive}\) 的容斥是 总数-不合法，发现你根本做不了，所以很容易想到加强限制，让答案等于 \(\sum\limits_{i=0}^n (-1)^i\times f(i)\) ，其中 \(f(i)\) 表示钦定有 \(i\) 个位置不满足 \(C_i!=A_i,C_i!=B_i\) 的方案数，即断掉 \(i\) 条边，考虑怎么求这个东西

考虑一个环怎么做

假设不是环而是一条链，容易想到设 \(f_{i,j,0/1}\) 表示现在到了第 \(i\) 个点，断掉 \(j\) 条边，钦定第 \(i\) 条边颜色为 \(A_i/B_i\) ，转移就是：

\(f_{i,j,0}=\sum\limits_{k=1}^{i-2}f_{k,j-1,1}+\sum\limits_{k=1}^{i-1}f_{k,j-1,0}\)

\(f_{i,j,1}=\sum\limits_{k=1}^{i-1}f_{k,j-1,1}+\sum\limits_{k=1}^{i-1}f_{k,j-1,0}\)

这个可以前缀和优化成 \(O(n^2)\) 的

但是这个 \(dp\) 是不适用于环的，因为我环上的第一个点会影响到最后一个点，所以要分类讨论强制断环成链

当我第一条边染的色是 \(A_i\) 时：

初始化：\(f_{1,1,0}=1\)

对答案贡献：\(\sum\limits_{i=1}^{n}f_{i,j,0}+\sum\limits_{i=1}^{n-1}f_{i,j,1}\)

当我第一条边染的色是 \(B_i\) 时：

初始化：\(f_{1,1,1}=1\)

对答案贡献：\(\sum\limits_{i=1}^{n}f_{i,j,0}+\sum\limits_{i=1}^{n}f_{i,j,1}\)

当我第一条边断掉时：

初始化：\(\forall i ,\ f_{i,1,0}=f_{i,1,1}=[i!=1]\)

对答案贡献：\(\sum\limits_{i=1}^{n}f_{i,j,0}+\sum\limits_{i=1}^{n}f_{i,j,1}\)

这三个方程中间的转移发现和上面的链的方程的转移是一样的

然后最后写一个背包合并把所有的环合并起来就好了/hanx

因为背包合并的复杂度是 两背包大小和乘上小的那个背包大小，所以时间复杂度是正确的/hanx

code

其中 dp 部分参考了洛谷的第二篇题解（但是好像现在没有公开