大概就是做点题。
先列一下要做的题目列表，从\(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\)种（后面的都比他要小随便插入进去就可以了）。
原文：https://www.cnblogs.com/Lrefrain/p/12123541.html