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)\) .
题解
前置知识 - 子集反演
首先反演是啥大家都知道吧
正着的子集反演:
\]
证明(抄的 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 课件偷偷在第三步换了一下变量名,坏坏
(反向子集反演:
\]
可以看做正着反演的直接推论)
别的不说了,这里又不是「子集反演学习笔记」.
1. 朴素 dp
考虑状压 dp.
令 \(dp_{i, j, S}\) 表示 \(i\) 点表示 \(j\),已经表示了 \(S\) 状态的方案数 .
\(i,j\) 维度显然,\(S\) 是为了去重,因为 \(a\) 必须是排列 .
转移非常容易:
\]
会点计数原理(加法,乘法)就能推出来 .
时间复杂度 \(O(n^33^n)\) .
定睛一看:\(n\le 17\),寄!
2. 优化一下
看看状态,这个 \(S\) 看起来挺没用,于是直接丢掉!
没了 \(S\) 我们就不能去重了呐,所以 \(a\) 是排列这个东西就不太能保证了 .
在 \(a\) 不一定是排列的前提下,定义:
- \(f(S)\):\(a\) 恰好使用了 \(S\) 中的所有点的方案数
- \(g(S)\):\(a\) 至多使用了 \(S\) 中的所有点的方案数
我们要的答案就是 \(f(U)\)(\(U\) 是全集)
显然有
\]
妈呀这不是子集反演吗,于是
\]
于是我们只要求 \(g\) 即可!
\(g\) 咋求呐?考虑 dp,令 \(dp_{i, j}\) 表示 \(i\) 点表示 \(j\),在 \(g\) 的条件下的方案数 .
于是可以轻易转移(与朴素的类似)
\]
我草这不是和朴素的一模一样吗
于是
\]
\(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.
- 炫酷反演魔术 - vfleaking(PPT)
- 炫酷反演魔术 - command_block
- 题解 P3349 [ZJOI2016]小星星 - RenaMoe
- 题解 P3349 [ZJOI2016]小星星 - 辰星凌
- 题解 P3349 [ZJOI2016]小星星 - one_cell(AcWing)
最新文章
- 非关系型数据库来了,CRL快速开发框架升级到版本4
- 15个优秀的 Material Design(材料设计)案例
- PAT 解题报告 1049. Counting Ones (30)
- call函数心得
- SOCKET 编程TCP/IP、UDP
- MacOS下Rails+Nginx+SSL环境的搭建(下)
- vue 构建项目vue-cli
- 【Loadrunner】Loadrnner 参数化策略
- android逆向四则运算
- Java 11 - Java String类
- 从后台获取的数据渲染到页面中的dom操作
- webapi 设置不显示接口到swaggerUI
- 【前端开发】移动端适配方案js,rem单位转换,640设计稿20px=1rem
- Android之对TabActivity的见解,个人觉得不错
- 树莓派(raspberry pi)学习11: 将树莓派变成一个Web服务器(转)
- NYOJ 123 士兵杀敌(四) (线段树)
- C++ 判断目录是否存在并新建目录
- Element-ui树形控件el-tree获取父级节点的id
- 剑指offer-树的子结构17
- mysql Connector C++ 操作数据库 vs2012