抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

比赛地址

A 就不写了。

B - Fusing Slimes

题意

\(N\) 个史莱姆,从左到右第 \(i\) 个在 \(x_i\)。执行 \(N-1\) 次操作,对于第 \(i\) 次操作:

  • \(1\)\(N-i\) 中等概率选择一个整数 \(k\)
  • 将从左到右第 \(k\) 个史莱姆向右移动到第 \(k+1\) 个史莱姆处,合并成一个新的史莱姆。

求期望移动距离乘 \((N-1)!\) 的值,对 \(10^9+7\) 取模。合并后的史莱姆只算一个。

\(N\le 10^5\)

题解

\(f_i\) 表示初始有 \(i+1\) 个史莱姆时,执行 \(i\) 次操作后,最后一段的期望贡献。分两种情况:

  • 第一次选择的是 \(i\)。此时最后一段被多贡献了一次,转化成 \(i\) 个史莱姆的子问题,所以贡献为 \(\frac{1}{i}(f_{i-1}+1)\)
  • 第一次选择的不是 \(i\)。此时最后一段没有贡献,仍然转化成了 \(i\) 个史莱姆的子问题,所以贡献为 \(\frac{i-1}{i}f_{i-1}\)

将两种情况的贡献相加,得到 \(f_i=f_{i-1}+\frac{1}{i}\)

考虑如何计算 \(x_i\)\(x_{i+1}\) 这一段的贡献。此时我们只需要考虑前 \(i\) 个史莱姆的相对操作顺序,而不需要考虑 \(i+1\)\(n\) 这些史莱姆的操作顺序,所以期望贡献次数就是 \(f_i\)

时间复杂度 \(O(n)\)

代码

题意

\(N\) 个数 \(c_1,c_2,\ldots,c_N\),初始为 \(0\)。有 \(K\) 次操作,第 \(i\) 次操作会选择 \(N\) 个数中的恰好 \(a_i\) 个加 \(1\)。求 \(\prod\limits_{i=1}^{N} c_i\) 的期望乘 \(\prod\limits_{i=1}^{K}\begin{pmatrix}N\\a_i\end{pmatrix}\) 的值。

\(N\le 1000,K\le 20\)

题解

考虑 \(\prod\limits_{i=1}^{N} c_i\) 的组合意义,即为对于每个 \(i\),在所有选择到 \(i\) 的操作中选择一个的方案数。

那么我们可以考虑先对于每个 \(i\),固定最终方案中选择的操作,记第 \(j\) 个操作被选择了 \(x_j\) 次。

此时方案数很好算,即 \[\prod\limits_{i=1}^{K}\begin{pmatrix}N-x_i\\a_i-x_i\end{pmatrix}\] 假设只固定 \(x_i\),而没有固定选择的方案,那么需要乘上选择的方案数 \[\frac{N!}{\prod\limits_{i=1}^{K} x_i!}\]

直接对 \(x_i\) 进行 DP 即可。

时间复杂度 \(O(N^2K)\)

代码

D - Arrangement

题意

给定 \(a_1,a_2,\ldots,a_N\),求一个字典序最小的 \(1\)\(N\) 的排列 \(b_i\),满足以下条件:

  • 对于所有 \(1\le i\le N-1\)\(a_{b_i}\ne b_{i+1}\)

\(N\le 10^5,a_i\ne i\)

题解

\(N=3\) 时可以通过讨论各种可能情况证明一定有解,而 \(N>3\) 时可以通过构造归纳证明。下面我们直接构造一组字典序最小的解。

考虑逐位确定,在逐位确定的过程中,若我们将 \(i\)\(a_i\) 连边,当前还未填的数形成的图一定是一个包含基环内向树和树的森林。

若存在一个点的入度等于当前总点数减 \(1\),即其他所有点都连向该点,那么此时必须选择这个点,否则我们选择能填的编号最小的点。

注意到这样填唯一会出问题的情况是剩下两个数没有填而这两个数形成了一个大小为 \(2\) 的环。但是因为我们证明了 \(N=3\) 时一定可行,此时限制比一般的 \(N=3\) 的情况更少,所以在剩下 \(3\) 个数时一定有合法解。

所以我们在剩下 \(3\) 个数时按字典序枚举所有 \(3!\) 种排列判断是否合法即可。

时间复杂度 \(O(N)\)\(O(N\log N)\)

代码

E - Span Covering

题意

你需要在数轴上 \([0,X)\) 这段区间中放 \(N\) 个有标号的区间。

放第 \(i\) 个区间时,你需要选择一个 \(0\le j\le X-L_i\) 的整数 \(j\),然后第 \(i\) 个区间为 \([j,j+L_i)\)

求覆盖 \([0,X)\) 中每个点的方案数。

\(N\le 100,X\le 500\)

题解

有一个简单的容斥想法是,钦定 \(k\) 个位置 \(x_1,x_2,\ldots,x_k\) 不被覆盖,假设 \(x_0=-1,x_{k+1}=X\),那么贡献是 \[(-1)^k\prod_{j=1}^{N}\left(\sum_{i=1}^{k+1}\max(0,x_i-x_{i-1}-L_j)\right)\]

假设 \(L_j=i\)\(j\ (1\le j\le N)\) 的数量为 \(c_i\)。记上述容斥中 \(x_j-x_{j-1}-1=i\)\(j\ (1\le j\le k+1)\) 的数量为 \(a_i\),那么上面的贡献式子也可以写成 \[(-1)^{X-\sum a_i}\prod_{i=1}^{X}\left(\sum_{j=i}^{X}a_j(j+1-i)\right)^{c_i}\]

我们考虑钦定 \(a_1,a_2,\ldots,a_X\),只需要在上述式子中再乘上 \(x_1,x_2,\ldots,x_k\) 的方案数,即 \[ \left(\sum_{i=1}^{X} a_i\right)!\prod_{i=1}^{X}\frac{1}{a_i!}\begin{pmatrix}X-\sum ia_i+1\\\sum a_i\end{pmatrix} \]

整理后得到贡献为 \[ \boxed{\prod_{i=1}^{X}\frac{1}{a_i!}\left(\sum_{j=i}^{X}a_j(j+1-i)\right)^{c_i}}\cdot\left(\sum_{i=1}^{X} a_i\right)!\cdot(-1)^{X-\sum a_i}\cdot \begin{pmatrix}X-\sum ia_i+1\\\sum a_i\end{pmatrix} \]

考虑从后往前对序列 \(a\) DP。令 \(f_{i,j,k}\) 表示固定 \(a_i,a_{i+1},\ldots,a_X\)\(\sum a_i=j\)\(\sum ia_i=k\) 时,画框部分式子的和。后面部分可以在最后计算答案是加入贡献。转移为 \[ f_{i,j,k}=\sum_{l=0}^{j} f_{i+1,j-l,k-i\cdot l}\cdot\frac{1}{l!}\cdot (k-(i-1)\cdot j)^{c_i} \]

注意到有 \(k\ge ij,l\le j\) 的限制,所以合法的 \((i,j,k,l)\) 四元组数量约为 \[X\sum_{i=1}^{X} \frac{X^2}{i^2}=O(X^3)\]

代码

评论