牛客挑战赛67-题解

A.首先我们注意到，条件等价于$\mathrm{\forall }1\le i\le n\backslash forall\; 1\backslash le\; i\; \backslash le\; n$，有$pr{e}_i\mathrm{\ne }su{f}_{i}pre\_\{i\}\; \backslash neq\; suf\_\{i\}$。因为当$i>ni\; >\; n$时，$pr{e}_i=su{f}_{2n-i}pre\_\{i\}\; =\; suf\_\{2n\; -\; i\}$，即$pr{e}_i\mathrm{\ne }su{f}_{i}pre\_\{i\}\; \backslash neq\; suf\_\{i\}$和$pr{e}_{2n-i}\mathrm{\ne }su{f}_{2n-i}pre\_\{2n-i\}\; \backslash neq\; suf\_\{2n-i\}$是等价的。然后，不妨直接把条件增强，令$\mathrm{\forall }1\le i\le n\backslash forall\; 1\backslash le\; i\; \backslash le\; n$，均有，不难看出，将$11$至$nn$填入前半部分，$n+1n+1$至$2n2n$填入后半部分即可，顺序任意。

然后考虑$P_a=bP\_\{a\}\; =\; b$的限制，如果有$a\le na\; \backslash le\; n$和$b\le nb\; \backslash le\; n$同时满足（或者同时不满足），上面的构造已经符合要求。如果两者一个满足一个不满足，则将$n+1n+1$至$2n2n$填入前半部分，$11$至$nn$填入后半部分即可。

不断随机几个满足$P_a=bP\_\{a\}\; =\; b$的排列，并检查是否符合条件也是可以通过的。

$\backslash space$

B.将字符$00$视为$10^{6}10^6$,字符$11$视为$10^6+110^6\; +\; 1$,字符$22$视为$-(2\cdot 10^6+1)-(2\backslash cdot\; 10^6\; +\; 1)$。则一个子串含有相同数量的$0,1,20,1,2$，当且仅当子串和为$00$。跑一个前缀和+map检查即可。

$\backslash space$

C.在下文中，对于路径$SS$，我们约定用$\mathrm{\mid }S\mathrm{\mid }|S|$表示路径的长度。

假设我们枚举最终的路径$S=(u,v)S\; =\; (u,v)$（$\mathrm{\mid }S\mathrm{\mid }>1|S|\; >\; 1$)，考虑如何计算至多有多少条不同的路径的交为该路径。其答案是$si{z}_u\times si{z}_{v}siz\_\{u\}\backslash times\; siz\_\{v\}$，其中$si{z}_{u}siz\_\{u\}$代表以对方(点$vv$)为根时，$uu$的子树大小。如果统一令$11$号点为根，则当$uu$是$vv$的祖先的时候，答案是$(n-si{z}_u+1)\times si{z}_v(n\; -\; siz\_\{u\}\; +\; 1)\; \backslash times\; siz\_\{v\}$，否则是$si{z}_u\times si{z}_{v}siz\_\{u\}\; \backslash times\; siz\_\{v\}$。

此时可以考虑dsu on the tree。对于每个点$uu$，维护集合$\{(d,s_d)\}\backslash \{(d\; ,\; s\_\{d\})\backslash \}$，代表$uu$的子树中，深度大于等于$dd$的点中，子树大小的最大值$s_{d}s\_\{d\}$。则当合并两个集合时，子树大小为$s_{d}s\_\{d\}$的节点，至少需要匹配一个子树大小为$\lceil \frac{k}{s_d}\rceil \backslash lceil\; \backslash frac\{k\}\{s\_\{d\}\}\; \backslash rceil$的节点。这一步可以通过在另一个集合中lower_bound来实现。而更新对应的$(d,s_d)(d,s\_\{d\})$只需要对后缀取max即可。

特殊判断祖先-子孙节点的情况，和答案等于$11$的情况。

$\backslash space$

D.首先可以对每个连通块单独处理。假设一个连通块具有$nn$个点，$mm$条边。若$n\le 20n\; \backslash le\; 20$，则我们可以暴力枚举哪些点被删除，然后统计答案，时间复杂度$O(2^n\times m)O(2^n\backslash times\; m)$

若$n>20n\; >\; 20$，则必有$m-n\le 20m\; -\; n\; \backslash le\; 20$。我们找出一棵生成树，并先考虑没有非树边的情况应该怎么计算。一个简单的办法是令$f_{i,0\mathrm{/}1}f\_\{i,0/1\}$代表$ii$的子树，点$ii$删或者不删的最小代价，直接dp即可。而对于每条非树边，其有三种可能性：用$aa$的代价直接删掉，被其中一个端点删掉，被另一个端点删掉。假设我们枚举这三种可能性的一种，相当于钦定了某若干个点必须删掉，仍可以套用上述的树dp。时间复杂度$O(3^{m-n}\times n)O(3^\{m-n\}\; \backslash times\; n)$，显然是过不了的。

现在我们假设，对于每条边，强制枚举它被某一个端点删掉，这样复杂度就可以退化到$O(2^{m-n}\times n)O(2^\{m-n\}\backslash times\; n)$。但是这样子会遗漏被直接使用$aa$的代价删掉的情况，怎么办呢？我们可以弱化对点的限制：本来情况下，枚举每条边被哪个点删掉，那个点被要求无法保留，而现在我们增加一个决策：可以保留这个点，但是需要额外支付$aa$的代价（相当于删去这条边，放弃对强制删除点的限制）。仍可以套用上述树dp，复杂度为$O(2^{m-n}\times n)O(2^\{m-n\}\backslash times\; n)$。

赛时有选手写了类似于$O(2^{n\mathrm{/}2})O(2^\{n/2\})$的的独立集做法，没有特别看懂，应该也是对的。

退火是过不了的，不知道有没有其他技巧高超的乱搞可以过。（赛时大家都是怎么过的呢）

$\backslash space$

E.一眼：妈妈我会容斥！考虑假定选取的点具有顺序，并枚举所有的可重联通块。不妨令集合$S_{i,j}S\_\{i,j\}$代表，第$ii$号点和第$jj$号点直接相邻的方案数，则对所有$\frac{k(k-1)}{2}\backslash frac\{k(k-1)\}\{2\}$个集合容斥即可得到答案。具体地，令$f_{i,j}f\_\{i,j\}$表示$ii$个点，违反$jj$条限制（每条限制形如上述的$(i,j)(i,j)$相邻）的方案数。对每个形状的连通快插头dp，算出恰有$xx$条边的连通子图的方案数，然后大力dp转移……

上面这个做法不仅难写而且时间还大。但是它启发我们一件事情：假设一个连通块长为$dxdx$，宽为$dydy$，则它在图中出现的方案数为$(n-dx)(m-dy)(n\; -\; dx)(m\; -\; dy)$。换句话说，纵使我们不清楚它具体的容斥系数，我们也能推断出，当$n,m\ge kn,m\; \backslash ge\; k$的时候，答案是关于$n,mn,m$的，不超过$kk$次的二元多项式（只有当$n,m\ge kn,m\; \backslash ge\; k$时，所有的连通块贡献才均不为$00$）。当$n,m\le kn,m\; \backslash le\; k$时，答案是关于$mm$的多项式，其中对于每个$nn$均有不同的多项式。

接下来只需要计算出所有$n,m\le 2kn,m\; \backslash le\; 2k$的值，便可以插值多项式了。一种做法是轮廓线dp，注意到轮廓线上的点，至多只有一对连续的$11$，故每条长为$nn$的轮廓线状态数是$O({\varphi }^n)O(\; \backslash phi^\{n\})$级别的，共有$n^{2}n^2$个轮廓线要考虑。故令$F_{i,j,k,S}F\_\{i,j,k,S\}$代表在点$(i,j)(i,j)$处，选了$kk$个点，轮廓线状态为$SS$的方案数。单个$nn$复杂度是$O(n^{2}k{\varphi }^n)O(n^2k\backslash phi^n)$，总的复杂度是$O(k^3{\varphi }^{2k})O(k^3\; \backslash phi^\{2k\})$。

赛时有一票子选手打表多项式，我应该手动输入模数$pp$的（悲

$\backslash space$

F.本来发现了插值做法之后想加强成算$S^k(k\le 1000)S^k(k\; \backslash le\; 1000)$，后来因为种种原因就没有加……谢罪.jpg。

这里直接介绍原做法：令$F_{i,k,p}F\_\{i,k,p\}$表示$ii$个变量，每个变量从$11$取到$mm$，答案不超过$pp$的方案数。我们递归地证明，$F_{i,k,p}F\_\{i,k,p\}$是关于$k,pk,p$的，总次数不超过$ii$的二维多项式()。

考虑枚举最左边的最大值位置$xx$，令其值为$k_{1}k\_\{1\}$，则若$2k_1\le p2k\_\{1\}\; \backslash le\; p$，方案数为$k_1^{i}k\_\{1\}^i$，若$2k_1>p2k\_\{1\}\; >\; p$则方案数为$F_{x-2,k_1-1,p}\times F_{i-x-1,k_1,p}\times (k-k_1{)}^{2}F\_\{x\; -\; 2\; ,\; k\_\{1\}\; -\; 1,p\}\; \backslash times\; F\_\{i\; -\; x\; -\; 1\; ,\; k\_\{1\}\; ,\; p\}\; \backslash times\; (k\; -\; k\_\{1\})^2$。式子的含义是，最大值两端的值必须取$\le k-k_1\backslash le\; k-k\_\{1\}$的值，并且取完之后对剩下部分没有影响。（当$x\le 2x\; \backslash le\; 2$或$x\ge i-1x\; \backslash ge\; i\; -\; 1$）时式子会有所区别，不再赘述。

故对于这个$xx$，有$F_{i,k,p}=(\lfloor \frac{p}{2}\rfloor {)}^i+{\sum }_{k_1=\lfloor \frac{p}{2}\rfloor +1}^k{F}_{x-2,k_1-1,p}\times F_{i-x-1,k_1,p}\times (k-k_1{)}^{2}F\_\{i,k,p\}\; =\; (\backslash lfloor\; \backslash frac\{p\}\{2\}\; \backslash rfloor)^i\; +\; \backslash sum\_\{k\_\{1\}\; =\; \backslash lfloor\; \backslash frac\{p\}\{2\}\; \backslash rfloor\; +\; 1\}^\{k\}\{F\_\{x\; -\; 2\; ,\; k\_\{1\}\; -\; 1,p\}\; \backslash times\; F\_\{i\; -\; x\; -\; 1\; ,\; k\_\{1\}\; ,\; p\}\; \backslash times\; (k\; -\; k\_\{1\})^2\}$

如果把$F_{i,k,p}F\_\{i,k,p\}$写成$\sum a_{i,j}{k}^i{p}^j\backslash sum\{a\_\{i,j\}\; k^ip^j\}$的形式，可以发现我们需要的仅仅是卷积后求一次若干次幂前缀和，这是完全可以预处理的部分。

但是有另一个问题，$\frac{p}{2}\backslash frac\{p\}\{2\}$是没法写进多项式里的（这个$\frac{1}{2}\backslash frac\{1\}\{2\}$不能简单地作为系数）。解决方案是分$p=2x+1p\; =\; 2x\; +\; 1$和$p=2xp=2x$讨论，分别建立两部分的多项式。细节会有点多。得到了最终的多项式，可以轻松求得期望。

一个事实是最终对$pp$求和会让答案退化成关于$mm$的一元多项式，于是可以暴力插值。如果题意改为询问$S^{k}S^k$的值，答案会进化成$n+kn+k$次多项式，就无法暴力dp求得点值了。