51nod 算法马拉松13

四月是你的跪烂

(离题一句，codechef MAY16居然要等到5月6日。。那么中间的时间只能开了噜

果真是，有了钱就有了动力

取余最长路

考虑$3\times n$的矩阵的答案。

假设强制路径经过点$(2,mid)$，那么从$(1,1)$走到$(2,mid)$有$O(n)$种路径，从$(2,mid)$走到$(3,n)$也有$O(n)$种路径。我们排序+二分查找或two pointers就可以合并出答案。复杂度$O(n\log n)$。

如果路径不经过$(2,mid)$，那么要么经过$(1,mid)$要么经过$(3,mid)$，那么两边分治一下就好。

算一下复杂度是$O(n\log^2 n)$的。

树有几多愁

考虑所有叶子$L_1,L_2,\dots,L_K$，其中$K\le 20$是叶子个数。最优决策一定是确定一个叶子排列$L'_1,L'_2,\dots,L'_K$，然后按顺序遍历所有叶子，对于一个叶子我们把它到根的路径上没有确定标号的点的标号都尽可能大地确定下来。比如说样例就是先染4，那么标号就是(5,4,?,3,?)，然后染5，标号就是(5,4,2,3,1)。

证明?不会。打表找规律大法好。

接下来使用状态压缩dp，$f_s$表示已经确定的叶子集合为$s$的最优答案。话说这个最优答案要记一个答案值用于比大小(取对数就好)和一个答案模$10^9+7$的值。预处理lca什么的搞搞可以把复杂度压到$O(2^KK)$辣。

比大小

首先$B_0=2B_0+1$，那么$B_0=-1$。然后暴力算$B$数组，打表找规律，发现以$B_1=B_2,B_2<B_3$开头，答案就是=<><循环。所以只要特判$A_N=0$的情况，求$A_N\bmod 4$的值就好咯。矩乘啊循环节啊瞎jb搞搞。

有限背包计数问题

膜吨

首先打一个大暴力，得到了小数据的答案1,1,2,3,4,5,7,10,13,17,22,28,36,46,58,73,91,114,141,173...

然后在OEIS上找到了答案数列A052335

考虑答案数列的母函数$\prod_{i\ge 1,i\ne j(j+1)}\frac{1}{1-x^i}$

然后沿着维基百科一路走过来，可以看到这个，所以$\prod_{i\ge 1}(1-x^i)$的前$n$项系数只有$O(\sqrt{n})$个不为$0$的。而且一定是$1,-1,-1,1,1,-1,-1,1\dots$。根据公式其实是可以$O(\sqrt{n})$求出这个多项式的。

然后脑补一下就可以$O(n\sqrt{n})$地求出其逆元辣!因为多项式$f$中只有$O(\sqrt{n})$个系数不为$0$，所以在求逆元的时候利用$f^{-1}_p=[p=0]-\sum_{i=1}^pf_if^{-1}_{p-i}$(其中$f_0=1$)，求一个$f^{-1}_p$实际上只需要考虑$O(\sqrt{n})$个不为$0$的系数，所以可以$O(\sqrt{n})$。这样求出整个逆元多项式就是$O(n\sqrt{n})$的。

接下来把$O(\sqrt{n})$个形如$(1-x^{i(i+1)})$的多项式乘过去。暴力乘法即可，一次复杂度$O(n)$。

总复杂度$O(n\sqrt{n})$。

B君的骗局

记$A,B,C,D,E,F,G,H,I$为“关键点“，令$f_{i,s}$表示经过的关键点集合为$s$，现在在点$i$，之后期望多久意识到自己被骗。

对于某些$s$，已经意识到自己被骗了，答案就是$0$。

否则枚举他去哪儿。$f_{i,s}=\frac{\sum_{(i,j)\in E}f_{j,s'}}{deg(i)}+1$。

按照$s$从多到少转移，相同的$s$中$i$的转移可以解方程。不想写辣，cc的码农题不知道比你们高明到哪里去了，写起来满满的都是享♂受!

复杂度$O(n^3\times 2^9)$。

(艹，居然要保留正好6位小数，老子第一个版本保留了17位小数→_→

FancyCat问题

fancy爷这么出题真的好么= =

就是给你三棵树(trie)，求它们的两两距离和。

在求两棵树的两两距离和的时候，可以在它们之间连一条边，组成一棵新的树，然后求新树的两两距离和。

求三棵树的两两距离和的时候，在$A,B$之间连一条边，在$B,C$之间也连一条边。

求最大和最小的答案。

考虑两棵树的情况，假设选$A$的点$u$和$B$的点$v$，那么答案就是

$$f(A)+f(B)+\sum_{i\in A} d(u,i)|B|+\sum_{i\in B}d(v,i)|A|+|A||B|$$

首先我们花式dp可以对每个点求出$\sum_{i\in A}d(u,i)$。选出使得$\sum_{i\in A} d(u,i)$和$\sum_{i\in B}d(v,i)$最大/最小的$u,v$即可。

三棵树的话，假设选$A$的点$u$与$B$的点$v$相连，$B$的点$x$与$C$的点$y$相连，答案就是

$$f(A)+f(B)+f(C)+\sum_{i\in A}d(u,i)|B|+\sum_{i\in B}d(v,i)|A|+|A||B|+\sum_{i\in B}d(x,i)|C|$$
$$+\sum_{i\in C}d(y,i)|B|+|B||C|+\sum_{i\in A}d(i,u)|C|+d(v,x)|A||C|+\sum_{j\in C}d(y,j)|A|+2|A||C|$$

令$g(i)$为$i$所在的树中所有点到$i$的距离的和。答案就是

$$c+g(u)(|B|+|C|)+g(v)|A|+g(x)|C|+g(y)(|B|+|A|)+d(v,x)|A||C|$$

其中$c=f(A)+f(B)+f(C)+|B||C|+|A||B|+2|A||C|$。

$u,y$可以直接贪心。至于$v,x$的话。。枚举$LCA(v,x)$，那么我们要最大/最小化$(dep_v+dep_x)|A||C|+g(v)|A|+g(x)|C|$。对每个子树记录一下$dep_x|A||C|+g(x)|A|$与$dep_x|A||C|+g(x)|C|$的最值即可。

复杂度$O(n)$。

这个题卡空间卡读入。trie树不能用$O(\sigma n)$的空间存下来，只能存下有用的边(Hash搞搞吧)；三棵树中只有一棵($B$)要求$(dep_v+dep_x)|A||C|+g(v)|A|+g(x)|C|$的最值(这部分会耗空间)，就只申请一次这种空间。读入的时候用读入优化，一个字符一个字符扫描，顺便记一下有没有'\n'。

唔。。cf 上有个题叫做 Three Trees 。是个傻逼E题，是这个题的一小问。

于是Ctrl+C,Ctrl+V大法好，叫你出原题