「塔」题解

题意简化

在 $[1, l]$ 整数点上造 $n$ 座塔：

• 塔 $i$ 高度为 $i$（编号从 1 到 $n$）
• 每座塔与前后相邻塔的距离 ≥ 该塔高度
• 塔的建造顺序任意（即塔的编号不一定要按位置顺序）
• 求方案数模 $m$

$n \le 100$，$l$ 可达 $10^9$。

核心观察

1. 距离条件

塔 $i$ 高度为 $i$，所以：

• 与左边邻居距离 ≥ $i$
• 与右边邻居距离 ≥ $i$

这意味着塔的编号越大，要求间距越大。

2. 重编号

由于建造顺序任意，我们可以先决定位置，再分配编号。

考虑将塔按位置排序后，给它们分配编号 $1..n$ 的排列 $\pi$，使得： 如果位置相邻的塔编号为 $i$ 和 $j$，它们的间距 ≥ $\max(i,j)$。

3. 转化为排列问题

设排序后位置为 $p_1 < p_2 < \dots < p_n$，分配的编号为排列 $\pi_1, \pi_2, \dots, \pi_n$。

条件：$p_{k+1} - p_k \ge \max(\pi_k, \pi_{k+1})$，对 $k=1..n-1$。

我们要求：

• 有多少种 $(p_1, \dots, p_n)$ 和排列 $\pi$ 满足上述条件？
• 其中 $1 \le p_1 < p_2 < \dots < p_n \le l$，且为整数。

关键思路：动态规划

状态设计

考虑从大到小插入塔的编号（先处理大塔，因为限制更严）。

DP状态： $dp[i][j]$ = 已经处理了编号最大的 $i$ 个塔（编号 $n, n-1, \dots, n-i+1$），形成了 $j$ 个连续段（块）的方案数。

转移

当插入编号为 $k = n-i$ 的塔时（当前是第 $i+1$ 步）：

1. 新建一个段：放在最左或最右，需要预留 $k$ 的空间 → 方案数 $2$（乘到系数）
2. 连接两个段：放在两个段之间，需要预留 $2k$ 的空间（左右各 $k$）→ 合并两个段，段数减 $1$
3. 接在一个段旁边：左接或右接，需要预留 $k$ 的空间 → 段数不变

但空间预留的总长度需要最后检查是否 ≤ $l$。

进一步转化

由于我们只关心预留空间的总长度，不关心具体位置，可以：

• 将每个塔需要的间距转化为“占用长度”
• 最后检查总占用长度是否 ≤ $l$

具体来说：

• 对于相邻塔 $(i,j)$，需要间距 $\max(i,j)$
• 如果我们按编号从大到小插入，每插入一个塔 $k$：
  • 新建段：贡献 $k$ 长度（一边预留）
  • 连接段：贡献 $2k$ 长度（两边预留）
  • 接在段边：贡献 $k$ 长度

所有段还会扩展，所以总占用长度 = $\sum$（每个塔的贡献） + 1（$n$ 个塔占 $n$ 个点，但间距占更多）

经典结论

实际上，这个问题等价于： 总占用长度 = $\sum_{i=1}^n 2c_i$，其中 $c_i$ 是塔 $i$ 在排列中的“邻接次数”

更简单的公式： 总占用长度 = $\sum_{i=1}^{n-1} \max(\pi_k, \pi_{k+1}) + 1$

最终算法

1. DP计算： $dp[i][j][s]$ = 考虑最大的 $i$ 个编号，形成 $j$ 个连续段，当前总占用长度为 $s$ 的方案数

2. 转移： 插入编号 $k = n-i$：

   • 新建段：$dp[i+1][j+1][s+k] += 2j \cdot dp[i][j][s]$（有 $j+1$ 个插入位置？需要调整） 实际上，有 $j+1$ 个空隙（包括最左最右）可新建段。

   正确的：

   • 新建段：$dp[i+1][j+1][s+k] += (j+1) \cdot dp[i][j][s]$
   • 合并段：$dp[i+1][j-1][s+2k] += (j-1) \cdot dp[i][j][s]$
   • 扩展段：$dp[i+1][j][s+k] += 2j \cdot dp[i][j][s]$

3. 统计答案： 最终 $dp[n][1][s]$ 表示所有塔形成一个段，总占用长度 $s$。 方案数 = $\sum_{s \le l} dp[n][1][s] \times C(l-s+1, n)$ 因为 $s$ 是间距总长，实际占点 $n$ 个，所以需要 $l \ge s+n-1$。

复杂度优化

• $n \le 100$，最大占用长度 $O(n^2)$，所以 $s \le O(n^2)$
• $l$ 很大但只用判断 $s \le l$
• DP复杂度 $O(n^4)$ 可接受

关键点

• 从大到小插入编号
• 连续段DP模型
• 总占用长度公式
• 最后乘组合数确定具体位置