遗迹[JOISC 2020 Day2]
题目链接
题解
先来看看给一个 $a_i$，最后柱子的高度 $b_i$ 可以怎么算。
显然可以从后面倒着枚举 $i$，然后从 $a_i$ 倒着枚举到 $0$ 找到一个 $j$ ，使得 $[1,j]$ 已经全部在 $i$ 后面使用过了。那么这个$b_i=j$。
这样就可以进行DP了，显然是倒着来的。
为了方便，我们设两个 $i$ 是不相同的，这样做就不需要处理是否出现过 $i$，那么只要最后答案除以 $2^n$ 就可以了。
设 $f _ {i,j} $ 表示从后往前考虑到第 $i$ 位时，$[1,j]$ 已经全部使用过，$j+1$ 没有使用的方案数。
- 若这一位的 $b_i$ 为 $0$：
那么这一位的 $a_i$ 则必须选在 $[1,j]$ 中的数，假设后面有 $m$ 个位置答案为 $0$，也就是说，已经有 $m$ 个位置选了 $[1,j]$ 中的数，且 $[1,j]$ 中所有数至少过一次（不然不可能 $[1,j]$ 全部数都使用过），也就是还有 $2j-(m+j)=j-m$ 个数可以选。
因此有：$f_{i,j}=f_{i+1,j}\times (j-m)$。
- 若这一位最后不为 $0$：
如果这一位最终不为 $j+1$，则只能以后再考虑。
如果这一位最终的 $b_i$ 为 $j+1$，那么再枚举这个 $j$ 转移到的 $j+k$，也就是当 $j+1$ 已经使用过后，$[1,j+k]$ 都将被使用过。下面考虑这个系数是什么。
设 $m$ 为 $[i+1,2n]$ 中，$b$ 不为 $0$ 的数的个数。
此时需要把 “如果这一位最终不为 $j+1$，则只能以后再考虑。”的情况考虑进去。也就是需要搞出后面的数是如何让 $[j+1,j+k]$ 都使用过的方案数。那么 $[i+1,2n]$ 最终的 $b_i$ 中，$[j+2,j+k]$ 的数都只能且必须出现 $1$ 次，也就是 $\binom{m-j}{k-1}$。
然后考虑 $a_i$ 能选的方案数，显然是 $2+((j+k)-(j+2)+1)=k+1$ 中情况。
然后还剩下一个 $s_{k-1}$，其中 $s_{m}$ 表示在 $[1,m]$ ，每个数能选两次，一共选 $m$ 个，最终的 $b_i$ 在 $[1,m]$ 均出现的方案数。
这个 $s_{m}$ 显然也可以DP解决。设 $g_{i,j}$ 表示考虑到第 $i$ 个数，最终的 $b_i$ 在 $[1,j]$ 均出现的方案数。
那么考虑第 $i$ 个数选了多少个，有： $g_{i,j}=g_{i-1,j}+g_{i-1,j-1}\times 2j+g_{i-1,j-2}\times j(j-1)$。
则有：$s_m=g_{m,m}$。
时间复杂度 $O(n^3)$。
程序
1 |
|