ZJOI2016 小星星 题解
我一生之敌是状压
本文发表于
- 洛谷博客：https://www.luogu.com.cn/blog/LoveMC/solution-p3349
- Cnblogs：https://www.cnblogs.com/CDOI-24374/p/15814569.html（可能阅读体验会差一点）
题面
给一个 \(n\) 点 \(m\) 边无向图 \(G=(V,E)\) 和一棵树，问有多少个排列 \(\{a_i\}\) 使得对于树上每一条边 \((u,v)\) 都有 \((a_u, a_v)\in E\) .
\(n\le 17\)，\(m\le \dfrac 12n(n-1)\) .
题解
首先反演是啥大家都知道吧 
正着的子集反演：
\[\boxed{f(S)=\sum_{T\subseteq S}g(T)\quad \Longleftrightarrow\quad g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T)}
\]
证明（抄的 vfleaking 神仙的）：
Lemma.
\[\sum_{T\subseteq S}(-1)^{|T|}=|S=\varnothing|
\]和二项式反演形式相似吧
好，回到原命题 .
\[\large\begin{aligned}g(S)&=\sum_{T\subseteq S} [S-T=\varnothing]g(T)\\&=\sum_{T\subseteq S}\sum_{R\subseteq S-T}(-1)^{|R|}g(T)\\&=\sum_{T\subseteq S}(-1)^{|T|}\sum_{R\subseteq S-T}g(R)\\&=\sum_{T\subseteq S}(-1)^{|T|}f(T-S)\\&=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T)\end{aligned}
\]和原式长得一模一样，证毕 .
似乎 vfk 的课件里 \(p,q\) 是二进制表示的集合吧，希望我没理解错QwQ
vfk 课件偷偷在第三步换了一下变量名，坏坏
（反向子集反演：
\[f(S)=\sum_{S\subseteq T}g(T)\quad \Longleftrightarrow\quad g(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}f(T)
\]
可以看做正着反演的直接推论）
别的不说了，这里又不是「子集反演学习笔记」.
考虑状压 dp.
令 \(dp_{i, j, S}\) 表示 \(i\) 点表示 \(j\)，已经表示了 \(S\) 状态的方案数 .
\(i,j\) 维度显然，\(S\) 是为了去重，因为 \(a\) 必须是排列 .
转移非常容易：
\[\large dp_{i, j, S}=\prod_{v\in\operatorname{son}(i)}\sum_{q\subseteq S, (j,p)\in E}dp_{v, p, q}
\]
会点计数原理（加法，乘法）就能推出来 .
时间复杂度 \(O(n^33^n)\) .
定睛一看：\(n\le 17\)，寄！
看看状态，这个 \(S\) 看起来挺没用，于是直接丢掉！
没了 \(S\) 我们就不能去重了呐，所以 \(a\) 是排列这个东西就不太能保证了 .
在 \(a\) 不一定是排列的前提下，定义：
- \(f(S)\)：\(a\) 恰好使用了 \(S\) 中的所有点的方案数
- \(g(S)\)：\(a\) 至多使用了 \(S\) 中的所有点的方案数
我们要的答案就是 \(f(U)\)（\(U\) 是全集）
显然有
\[g(S)=\sum_{T\subseteq S}f(S)
\]
妈呀这不是子集反演吗，于是
\[f(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}g(T)
\]
于是我们只要求 \(g\) 即可！
\(g\) 咋求呐？考虑 dp，令 \(dp_{i, j}\) 表示 \(i\) 点表示 \(j\)，在 \(g\) 的条件下的方案数 .
于是可以轻易转移（与朴素的类似）
\[\large dp_{i, j}=\prod_{v\in\operatorname{son}(i)}\sum_{p\in S, (j,p)\in E}dp_{v, p}
\]
我草这不是和朴素的一模一样吗
于是
\[\large g(S)=\sum_{k\in S}dp_{root, k}
\]
\(root\) 是树的根，你随便钦定一个就好了 .
单次 dp \(O(n^22^n)\)，总时间复杂度 \(O(n^32^n)\)，大体能过
答案不大于 \(n!\le 355687428096000\)，long long 完全能行 .
然而 \(g(S)\le n^n\le 827240261886336764177\)，unsigned long long 都不行 .
我们自然可以用 __int128，但是，其实我们随便选一个幸运数字 \(M>n!\)，然后答案对 \(M\) 取模就行了！
方便点，unsigned long long 自然溢出就完啦！是不是很简单
有符号整形溢出是 UB，但是我懒的改了，我代码里是有符号的 .
提交记录 https://uoj.ac/submission/528128 .
吸个氧跑得飞快，不吸就会 TLE（或许是用 vector 太多了？）
自以为可读性好！
Ref.
手机扫一扫
移动阅读更方便
你可能感兴趣的文章