「GDOI2020模拟赛day1」Permutation
「GDOI2020模拟赛day1」Permutation
为了便于叙述，设原题中的 \(n\) 为 \(N\)
题目分析
要求一个 \(1-n\) 的环排列，看成是一个环遍历
发现每条边的权值限制了遍历过程中穿过这条边的次数
取 \(1\) 为根，强制从 \(1\) 开始遍历，考虑以一个个自由段（即未确定前后连接关系的子段）的形式维护 \(u\) 子树中的序列段
那么，只需要满足 \(u\) 子树中自由段的个数为 \(\frac{w(u,fa_u)}{2}\) （每一个自由段的两端均对应一次跨越）即可
分析即可发现 \(w(u,fa_u)\) 显然是 \(O(size_u)\) 级别的，因此考虑树形背包
那么我们就需要支持合并两组自由段
\[ \ \]
\(O(N^3-N^2\log N)\)
设当前 \(1\ldots n\) 个自由端，合并上 \(m\) 个自由段(从子树合并上来是恰好 \(m\) 个)
注意这些自由段之间是无序的
先考虑一个简单的模型：
把 \(n\) 个无序自由段拼接成 \(m\) 个无序自由段，设方案数为 \(W(n,m)\) ，则考虑
先把 \(n\) 个自由段排列，然后选出 \(n-m\) 个间隔连接，然后除掉得到的 \(m\) 个段之间的排列
得到 \(\begin{aligned} W(n,m)=\frac{n!}{m!}\binom{n-1}{n-m} \end{aligned}\)
类似的，可以把 \(n+m\) 个自由段排成一排，合并成若干段
但是显然存在的问题就是：可能在两组自由段之间形成了连接，这样的连接是非法的
因此考虑容斥
\(\begin{aligned} dp'_{d}\longleftarrow\sum_{i=1}^ndp_{u,i}\sum_{j=1}^idp_v (-1)^{i-j}W(i,j) \sum_{k=1}^m (-1)^{m-k}W(m-1,k)\sum_{d=1}^{j+k}W(j+k,d)\end{aligned}\)
将上式分解为四步转移
\(n,i\rightarrow j,O(n^2)\)
\(m\rightarrow k,O(m)\)
\(j,k\rightarrow j+k,O(nm)\)
\(j+k\rightarrow d,O((n+m)^2)\)
其中 \(O(n^2,(n+m)^2)\) 的部分如果用卷积优化，即可做到 \(O(N^2\log N)\)
但是 \(O(N^3)\) 就 \(pts75\) 了...
Tips:注意在将 \(1\) 号节点加入序列时，用上面的方法无法保证它在序列首
需要特殊处理，始终强制它在第一个
\(O(N^2)\)
当我发现这个做法不需要任何优化就可以做到 \(O(N^2)\) 的时候。。。。
把这个容斥的过程爆开
先对于每个儿子的 \(dp\) 值按照容斥系数进行上文中 \(m\rightarrow k\) 的变换，复杂度为 \(O(size_u)\)
然后进行背包合并，由树形背包的复杂度分析，总复杂度为 \(O(N^2)\)
最后发现其实我们只需要知道 \(dp_{u,w(u,fa_u)}\) ，因此这里也只需要 \(O(size_u)\)
综上，复杂度为 \(O(N^2)\)
1 |
|