2019-01-20：loli的两场模拟赛的题解

今天 loli 搞了上午下午连续两场模拟赛，于是来写一篇题解。

上午记为 D1，下午记为 D2。

D1

T1 简 - simple

给你 $2n$ 个数，让你配成 $n$ 对数，每个数恰属于一对数，一对数的得分是其中的较小值，让你最大化得分和。

$n\leqslant 100000$。

不予置评。

T2 单 - single

给你一棵树，每个点有点权 $a_{i}$，$dist(u,v)$ 表示 $u$ 到 $v$ 的树上路径经过的边数。定义

$$b_{u}=\sum_{i=1}^{n}dist(u,i)a_{i}$$

还会给你一个 $\text{tp}$，$\text{tp}=0$ 时给你 $\{a_{n}\}$ 让你求 $\{b_{n}\}$，$\text{tp}=1$ 时给你 $\{b_{n}\}$ 让你求 $\{a_{n}\}$。多组数据。

$n\leqslant 100000,T\leqslant 5$。

$\text{tp}=0$ 时就是一个简单的树形 DP。

$\text{tp}=1$……高斯消元？不是很会写而且 $O(n^{3})$ 会 T 飞啊（

他给的题解我也没看懂（

我就打了 $\text{tp}=0$ 的 $30$ 分。

T3 题 - problem

有一个平面直角坐标系。一开始你在原点，每次移动可以从 $(x,y)$ 移动到 $(x+1,y)$，$(x-1,y)$，$(x,y+1)$，$(x,y-1)$。再给你一个无穷点集 $S$，你只能停留在这个点集内的点上，问你恰好 $n$ 步后回到原点的方案数。对 $10^{9}+7$ 取模。

关于 $S$，首先会给你一个 $\text{tp}$，然后 $S$ 如下定义

$$S=\begin{cases} &\{(x,y)\mid x,y\in\mathbb{Z}\}\;\;&(\text{tp}=0)\\ &\{(x,y)\mid x\in\mathbb{N},y=0\}&(\text{tp}=1)\\ &\{(x,y)\mid xy=0\}&(\text{tp}=2)\\ &\{(x,y)\mid x,y\in\mathbb{N}\}&(\text{tp}=3) \end{cases}$$

$n\leqslant 100000$，$n\equiv 0\pmod{2}$，$\text{tp}\in\{0,1,2,3\}$。特殊地，当 $\text{tp}=2$ 时 $n\leqslant 1000$。

四合一数论提答（

很明显，无论是 $x$ 坐标上还是 $y$ 坐标上，我们都需要移动偶数次。再加上 $n$ 保证是偶数，我们可以将 $n$ 除以 $2$，然后走 $2n$ 步。

$\text{tp}=0$ 时，我们枚举 $2i$ 步沿 $x$ 轴方向走，$2(n-i)$ 步沿 $y$ 轴方向走。
我们可以将这抽象成一个序列，其中有 $i$ 个 $x+1/x-1$，$n-i$ 个 $y+1/y-1$，总排列方案数就是 $\cfrac{(2n)!}{i!i!(n-i)!(n-i)!}$。因此

$$\text{Ans}=(2n)!\sum_{i=0}^{n}\cfrac{1}{i!i!(n-i)!(n-i)!}$$

$\text{tp}=1$ 直接卡特兰数。

$\text{tp}=2$ 比较特殊。因为我们不能离开坐标系，一旦我们离开了原点，我们必须要先走回原点，才能沿着另一个坐标轴的方向继续走。我们可以考虑两种不同的括号，不同种括号之间不能嵌套，然后问有多少个长度为 $2n$ 的序列是匹配的。

如果说我们有连续一段一共 $i$ 对同种括号，不难发现排列方案数是 $\cfrac{(2i)!}{i!i!}$，于是我们就有了一个 $O(n^{2})$ 的 DP

$$f[x]=\sum_{i=1}^{x}f[x-i]\cfrac{(2i)!}{i!i!}$$

其实如果改一下模数的话这个东西可以用 NTT 优化到 $O(n\log n)$ 的。虽然现在这个样子 MTT 也能搞……但是我不会写（

$\text{tp}=3$ 大概是 $\text{tp}=0$ 与 $\text{tp}=1$ 的结合。枚举沿 $x$ 轴方向走多少步，然后两个方向分别卡特兰，然后把两个序列合并起来。于是

$$\begin{aligned} \text{Ans}&=\sum_{i=0}^{n}C_{2n}^{2i}C_{i}C_{n-i}\\ &=\sum_{i=0}^{n}\cfrac{(2n)!}{(2i)!(2(n-i))!}\left(\cfrac{(2i)!}{i!i!}-\cfrac{(2i)!}{(i+1)!(i-1)!}\right)\left(\cfrac{(2(n-i))!}{(n-i)!(n-i)!}-\cfrac{(2(n-i))!}{(n-i+1)!(n-i-1)!}\right)\\ &=(2n)!\sum_{i=0}^{n}\left(\cfrac{1}{i!i!}-\cfrac{1}{(i+1)!(i-1)!}\right)\left(\cfrac{1}{(n-i)!(n-i)!}-\cfrac{1}{(n-i+1)!(n-i-1)!}\right) \end{aligned}$$

于是愉快地 $230$ 直接 rank1（

话说 wzx 打了 $240$ 分的啊……然而炸成 $210$（

D2

T1 印章 - seal

给你一张 $n\times m$ 的纸，上面有些格子要印墨水。你有一个 $r\times c$ 的印章，上面有些格子是凸起的可以印。纸和印章不可以旋转，不可以重复印同一个格子，不可以把墨水印到纸外面去。问是否可行。多组数据。

$n,m,r,c\leqslant 1000,T\leqslant 10$。

首先我们不难想出一个 $O((n-r)(m-c)rc)$ 也就是差不多 $O(n^{4})$ 的暴力。不过这样只有 $60$ 分。当时我用了一个 bitset 瞎搞了一波把复杂度降到了 $O(n^{3})$，然而……并没有什么用（

拿了 $60$ 就跑（

T2 多边形 - polygon

一个 $0-n$ 边形被定义为一个正常的 $n$ 边形。对于一个 $k-n$ 边形，对于它最外层的每一条边，我们向外做 $n$ 边形，得到一个 $(k+1)-n$ 边形。

这是一个 $0-4$ 边形

这是一个 $1-4$ 边形

这是一个 $2-4$ 边形

给你一个 $k-n$ 边形，问你它的生成树数量。对 $998244353$ 取模。

$0\leqslant k\leqslant 10^{6},3\leqslant n\leqslant 10^{9}$。

告辞（

彻底放弃治疗（

T3 扔球 - ball

给你 $n$ 个球和 $n$ 个瓶子，编号从 $1$ 到 $n$。每个球只能扔到指定集合的瓶子里。对于每个球，把它指定集合里的瓶子按编号从小到大排序，然后依次往里面扔球。每次扔进去的概率是 $p$，扔不进去就试下一个瓶子，试完所有瓶子一遍还是没扔进去就从头再来一遍直到扔进去为止。指定集合为空就跳过这个球。

所有球扔完之后，记 $i$ 号球被扔进了 $a_{i}$ 号瓶子，问你 $\{a_{n}\}$ 的期望逆序对数量。四舍五入保留两位小数。

如果扔球时跳过了 $i$ 号球，那么当做 $a_{i}$ 不存在。

$n\leqslant 500000,0.4\leqslant p\leqslant 0.6$。记 $i$ 号球的指定集合为 $S_{i}$，$\Sigma|S_{i}|\leqslant 500000$。

从后往前扫，扫到 $x$ 时枚举 $a_{x}$ 的可能取值 $y$，将答案累加上 $a_{x}=y$ 的概率与 $a_{x+1}$ 到 $a_{n}$ 中小于 $y$ 的数的数量的期望值的乘积。然后 $a_{x}$ 到 $a_{n}$ 中 $y$ 的出现次数的期望值就是 $a_{x+1}$ 到 $a_{n}$ 中 $y$ 的出现次数的期望值再加上 $a_{x}=y$ 的概率。

套个树状数组就行。

但是等会，$a_{x}=y$ 的概率怎么算啊。

首先我们考虑集合中最小的那个数，把球扔进那个瓶子的概率应该是

$$\begin{aligned} \lim_{n\rightarrow+\infty}\sum_{i=0}^{n}(1-p)^{i|S_{x}|}p&=p\cfrac{(1-p)^{(n+1)|S_{x}|}-1}{(1-p)^{|S_{x}|}-1}\\ &=\cfrac{p}{1-(1-p)^{|S_{x}|}} \end{aligned}$$

那么第 $2$ 小呢？首先我们第一次扔不能扔进去，所以首先需要乘个 $1-p$，然后就和上面一样了。依次类推，扔进编号第 $i$ 小的瓶子的概率为

$$\cfrac{p(1-p)^{i-1}}{1-(1-p)^{|S_{x}|}}$$

最后总分只有 $160$，被 $190$ 分的 wzx 吊着打（