「总结」dp1

大概就是做点题。

先列一下要做的题目列表，从\(UOJ\)上找的。

129寿司晚宴

348州区划分

370滑稽树上滑稽果

457数树

22外星人

量子态的棋盘

吉夫特

线段树

题目交流通道

主旋律

1.寿司晚宴

这个题还是不错的，之前学长讲过一次。

不过不记得了。还是被根号算法教做人了。

首先数据范围是500。

考虑这里面的质因子个数有多少个。

事实上很多，早就超过了20个。

而考虑\(\sqrt{n}\)以下的最多有多少个呢？

事实上只有\(8\)个。

而任何一个小于\(n\)的数必然至多含有一个大于\(\sqrt{n}\)的质因子。

那么我们考虑状压这\(8\)个质因子。

设\(dp[s][t]\)为第一个人和第二个人已经选择了的质因子集合直接将没有大于\(\sqrt{n}\)质因子的数字加入贡献。

剩下的我们可以发现只有一个人可以含有某个大于\(\sqrt{n}\)的质因子或者两个人都不含。

这样将全部的最大质因子大于\(\sqrt{n}\)的数先\(dp\)一次压在一起在当成一个数来进行\(dp\)就可以了。

是一个\(dp\)嵌套。

最后统计答案就可以了。

4.州区划分

事实上是\(FMT\)的板子题。

设分成了\(T\)个部分,每个部分的集合为\(S_i\)

首先我们要求的是：

\[\prod\limits_{k=1}^{T}\left(\frac{\sum\limits_{i\in S_k}w_i}{\sum\limits_{j=1}^{k}\sum\limits_{i\in S_k}w_i}\right)\]

事实上可以直接\(dp\)。

但是\(dp\)之前首先要判断一下集合的合法性，就是判断是否是一个联通的欧拉回路。

怎么做？

设\(su[s]=\sum\limits_{i\in S}w_i\)

设\(dp[s]\)为当前已经处理的集合为\(S\)的答案。

那么初始化：

\(dp[0]=1\)

要求的是\(dp[mx]\)

枚举当前添加进来的集合是\(T\)，得到转移方程。

\[dp[S]=\left(\frac{1}{su[S]}\right)^p\sum\limits_{T\subseteq S}dp[T]su[S-T]^p\]

这样直接转移枚举子集的复杂度是\(3^n\)的。

肯定吃不消。

我们考虑如何优化这个过程呢？

这个过程事实上是一个裸的子集并卷积。

直接\(FMT\)即可。

复杂度是\(O(n^22^n)\)

3.滑稽树上滑稽果

说是个树就是骗你的。

如果树上存在一条链，那么显然把剩余的部分接到链的后面更加优秀。

然后呢？

我们把全部果子都有的位置先拿出来因为这些位置最后必然是1,设为\(k\)。

然后让全部果子都异或\(k\),这样最终的与和必然是0。

设\(dp[s]\)为当前与和为\(s\)的情况下的最小代价。

初始化\(dp[a[i]]=a[i]\)。

这样我们来枚举每个果子然后判断转移即可。

考虑如何判断是否可以转移。

我们枚举当前集合的一个子集\(t\)。

然后判断是否存在一个果子可以刚好与掉这一部分子集。

那么我们需要判断的其实是这个果子是否是与掉部分的补集的子集。

但是其实仍然需要判断是否是当前剩余部分\(s-t\)的超集。

然后发现这样其实无所谓。

由于最优决策必然会转移，而这种决策如果是不合法的（能够与掉更大的集合却没有与掉），其实是不优秀的转移，会被更加优秀的转移所覆盖掉（因为最终需要的结果只有一个是\(dp[0]\)，所有的转移最终都会收敛到\(0\)的位置）。

那么需要判断的只有一个了，就是是当前枚举的与掉的补集的子集，这个好判断。

其实就是判断一个是否存在一个\(a_i\)是某个集合的子集。直接用\(FMT\)进行一次子集合并就可以了。

然后紧接着考虑判重问题。

如果一个状态转移了很多次同一个果子怎么办？

其实也无所谓。

因为转移多了的话必定是转移到当前的集合上面来。

这样\(dp[s]=min(dp[s],dp[s]+s)\)

最优结果是不会发生变化的。

4.数树

可以用类似生成树计数的方式来做，不过这里考虑用组合意义来解题。

先考虑第一问。

其实是最简单的。

我们只需要把重边加入并查集，最后判断有几个集合即可。

然后直接快速幂就行了。

第二问是解题的关键部分。

首先有一个很显然的结论：

\[x^n=(x-1+1)^n=\sum\limits_{i=0}^{n}\binom{n}{i}(x-1)^n\]

我们考虑对于每种树所作出的贡献，我们设有\(r\)条重边。

那么枚举这个树为\(T\),得到。

\[ans=\sum\limits_{T}y^{n-r}=y^n\sum\limits_{T}(y^{-1})^r=y^n\sum\limits_{T}\sum\limits_{i=0}^{r}\binom{r}{i}(y^{-1}-1)^i\]

然后我们考虑这个组合意义。

实际上是对于这个重边集合的每个子集\(S\)，都作出\((y^{-1}-1)^{|S|}\)的贡献。

这样我们换个方式直接枚举边集，考虑有多少个生成树的重边集合是包含这个子集的，设包含边集\(E\)的方案为\(F(E)\)。

那么：

\[ans=y^n\sum\limits_{E}(y^{-1}-1)^{|E|}F(E)\]

我们设这个边集所形成的点集为\(m\)个，并且每个联通块的大小用\(\{a_i\}\)来表示。

利用\(prufer\)序列得到：

\[F(E)=n^{m-2}\prod\limits_{i=1}^{m}a_i\]

就是说我现在让\(n\)个点生成一个\(m-2\)长度的\(prufer\)序列，相当于将每个点分配给\(m\)个联通块作为代表元素，而同时，每个联通块都有\(a_i\)个点,每个点都有可能作为代表元素，所以有了后面的\(\prod\)。

这样接着推柿子：

\[\begin{aligned}
ans&=y^n\sum\limits_{E}(y^{-1}-1)^{|E|}F(E)\&=y^n\sum\limits_{E}(y^{-1}-1)^{|E|}n^{m-2}\prod\limits_{i=1}^{m}a_i\&=y^n\sum\limits_{E}(y^{-1}-1)^{n-m}n^{m-2}\prod\limits_{i=1}^{m}a_i\&=y^n(y^{-1}-1)^nn^{-2}\sum\limits_{E}((y^{-1}-1)^{-1}n)^{m}\prod\limits_{i=1}^{m}a_i\&=(1-y)^nn^{-2}\sum\limits_{E}\prod\limits_{i=1}^{m}a_i(y^{-1}-1)^{-1}n\\end{aligned}\]

考虑后面这个东西的组合意义。

就是在要求把树分成\(m\)个联通块的情况下在每个点中选择一个特殊点作为染色点，然后每个联通块要乘上的贡献是\(n(y^{-1}-1)^{-1}\)

这样问题就变得简单起来了。

我们做一次\(dp\)就可以解决了。

我们设\(dp[x][0/1]\)为当前点为\(x\),\(x\)及其归并的子树中\(x\)所在的联通块(已经/还未)存在关键点的贡献总和。

设\(w=n(y^{-1}-1)^{-1}\)

初始化：\(dp[x][0]=1,dp[x][1]=w\)

这样有转移方程：

\[dp[x][0]=dp[x][0]dp[t][1]+dp[x][0]dp[t][0]\]

\[dp[x][1]=dp[x][0]dp[t][1]+dp[x][1]dp[t][0]+dp[x][1]dp[t][1]\]

这样就可以\(O(n)\)的得到答案了。

第三问要用到生成函数了。

我们考虑一下对于每个生成树，我们仍然考虑他的边集所做的贡献。

这样的话仍然枚举一次生成树：

\[ans=(1-y)^nn^{-2}\sum\limits_{T}\sum\limits_{E}\prod\limits_{i=1}^{m}a_i(y^{-1}-1)^{-1}n\]

仍然枚举边集，考虑被计算的次数：

\[\begin{aligned}
ans&=(1-y)^{n}n^{-2}\sum\limits_{E}F(E)\prod\limits_{i=1}^{m}a_i(y^{-1}-1)^{-1}n\&=(1-y)^nn^{-2}\sum\limits_{E}n^{m-2}\prod\limits_{i=1}^{m}a_i^2(y^{-1}-1)^{-1}n\&=(1-y)^{n}n^{-4}\sum\limits_{E}\prod\limits_{i=1}^{m}a_i^2(y^{-1}-1)^{-1}n^2\&=(1-y)^{n}n^{-4}\sum\limits_{E}((y^{-1}-1)^{-1}n^2)^{m}\prod\limits_{i=1}^{m}a_i^2\P(m)&=((y^{-1}-1)^{-1}n^2)^{m}\&=(1-y)^{n}n^{-4}\sum\limits_{E}P(m)\prod\limits_{i=1}^{m}a_i^2\\end{aligned}\]

这样我们设立一个指数生成函数\(G(x)\)。

我们让\(e_i=P(i)i^2i^{i-2}\)，这个是什么呢？

我们用一个大小为\(i\)的联通块进行组合，这样我们得到了的贡献就是\(i^2\)，而这种情况存在的内部的方案有\(i^{i-2}\)种（\(prufer\)）序列。

而我们让：

\[G(x)=\sum\limits_{i=1}^{\infty}\frac{e_ix^i}{i!}\]

这样的话就是一个联通块的方案和贡献合并的生成函数了。

我们考虑一棵树是多个生成函数的组合。

于是我们设有\(n\)个点的树的贡献生成函数为\(F(x)\)。

因为必然至少有一个联通块,并且每个联通块内部已经有所编号，那么联通块是没有编号的，所以除掉阶乘，那么有：

\[F(x)=\sum\limits_{i=1}^{\infty}\frac{G^i(x)}{i!}=e^{G(x)}\]

这样直接用一个\(exp\)就可以算出来了。

答案就是：

\[ans=(1-y)^{n}n^{-4}n![x^n]F(x)\]

复杂度是\(O(nlogn)\)的。

5.外星人

这个题好像还挺简单的。

首先我们知道如果一个比较小的数比一个比较大的数更加靠前的话。

那么后边那个比较大的数其实是没有用的。

这样我们按照从小到大排序，然后枚举每个数是否起作用就可以转移了。

当然最小的那个数必须要其作用。

然后考虑如何\(dp\)方案。

设\(dp[i][j]\)为在考虑前\(i\)个人的情况下，当前答案为\(j\)的方案数。

这样可以得到转移方程：

\[dp[i][j]=[k\%a[i]=j]dp[i-1][k]+dp[i-1](n-i)\]

后面那个表示当前这个不起作用，那么他所在的位置就有\(n-i\)种（后面的都比他要小随便插入进去就可以了）。