[动态规划] SEUOJ103 排列组合

作者: kinoud | 来源:发表于2019-07-02 18:11 被阅读0次

初始有一张n个结点没有边的空图,有m次加边或减边的操作,对于每一次操作完成后,求出选择k(k=1,2,...,n/2)条无公共端点的边的方案数(对于两点间的重边,计为不同的方案).
n<=10 m<=3e5
题目链接: https://oj.seucpc.club/problem/103

解法

首先分析一下加减边的影响.设f_k(G)表示在G这张图里选取k条边的方案数.那么有 $f_k(G+(u,v))=f_k(G)+f_k(G-u-v)$ G+(u,v)是图G加上边(u,v),G-u-v是图G去掉点u和点v.此外还有 $f_k(G-(u,v))=f_k(G)-f_k(G-u-v)$
我们看到无论是加边还是减边,关键一项都是f_k(G-u-v).
接下来设计动态规划方法.
设 $dp(S)= \left\{\begin{align} 所选边覆盖S集中所有点的方案数& &|S|为偶 \\ 0& &|S|为奇 \end{align}\right.$
设ans[k]为对于当前图,选择k条边的方案数.
则有
$ans(k)=\sum_{|S_i|/2=k}{dp(S_i)}$
状态转移为
$\begin{align} &加边(u,v)&new\_dp(S+u+v)=dp(S+u+v)+dp(S) \\ &减边(u,v)&new\_dp(S+u+v)=dp(S+u+v)-dp(S) \end{align}$
上面这些方程通过分类讨论"方案中是否含有边(u,v)"即可得到.
每次加减边操作后,都按照状态转移方程更新一遍dp数组,并同时计算f_k(G-u-v),方法为
$f_k(G-u-v)=\sum_{|S_i|/2=k}{dp(S_i)}$