题解：胶带折叠方案的组合计数与动态规划

---

问题分析

本题要求计算胶带折叠的方案数，使得胶带能够被还原而不被粘住。关键条件：

• 胶带长 $N$ 段，只能在段间折叠180°
• 胶带有两面：
  • 一面：全部涂胶（称为"全胶面"）
  • 另一面：前 $A$ 段和后 $B$ 段涂胶（称为"部分胶面"）
• 要求：折叠后没有两个胶面接触（否则撕不开）

---

核心观察

1. 折叠的本质

180°折叠意味着胶带会被分成若干"层"，每层由连续的若干段组成，且相邻层方向相反（一个朝上，一个朝下）。

折叠过程可以看作：选择一些折叠点，将胶带反复对折。

2. 胶面接触条件

由于一面全胶、一面部分胶，要避免胶面接触，需要考虑：

• 当两段接触时，它们必须是一段的全胶面对另一段的无胶面
• 或者一段的部分胶面对另一段的无胶面

3. 问题转化

实际上，问题可以转化为：将 $N$ 段胶带分成若干连续的组，每组内部段的朝向相同（要么全胶面朝上，要么部分胶面朝上），且满足涂胶段的约束。

更精确地，我们需要考虑"全胶面朝上"的段和"部分胶面朝上"的段的分布。

---

算法框架

动态规划定义

设 $dp[n][k]$ 表示将长度为 $n$ 的胶带分成若干段，每段长度至少为 $k$ 的方案数。

这里的 $k$ 实际上代表当前考虑的分组的最小长度限制。

状态转移

考虑第一段的长度：

• 如果第一段长度至少为 $k+1$，方案数为 $dp[n][k+1]$
• 如果第一段长度恰好为 $k$，剩下的 $n-k$ 段要求每段长度至少为 $k$，方案数为 $dp[n-k][k]$

因此：

$$dp[n][k] = dp[n][k+1] + dp[n-k][k]$$

边界条件：$dp[n][n] = 1$（只有一段的情况）

最终答案计算

我们需要计算所有满足条件的折叠方案。关键观察：

• 设全胶面朝上的部分总长度为 $x$（$x \ge A$）
• 部分胶面朝上的部分总长度为 $y$（$y \ge B$）
• 且 $x + y \le N$

方案数为：

$$\text{ans} = \sum_{i=0}^{N-A-B} (dp[A+i][A] - dp[A+i-1][A]) \times dp[N-(A+i)][B] $$

其中：

• $dp[A+i][A] - dp[A+i-1][A]$ 表示全胶面部分长度为 $A+i$ 的方案数
• $dp[N-(A+i)][B]$ 表示部分胶面部分长度为 $N-(A+i)$ 的方案数

---

关键实现细节

1. DP初始化

for (int i = 0; i <= n + 1; i++)
    dp[i][i] = 1;  // 长度为i，最小段长i：只有一段

2. DP计算

从 $n$ 到 $1$ 逆序计算：

for (int i = 1; i <= n; i++) {
    for (int j = n; j >= 0; j--) {
        if (j >= i) continue;  // 最小段长不能超过总长
        dp[i][j] = (dp[i][j+1] + dp[i-j][j]) % mod;
    }
}

3. 答案计算

int ans = 0;
for (int i = 0; i <= (n - a - b); i++) {
    int term1 = (dp[a+i][a] - dp[a+i-1][a] + mod) % mod;
    int term2 = dp[n-(a+i)][b] % mod;
    ans = (ans + term1 * term2) % mod;
}

---

正确性证明

1. DP转移的正确性

$dp[n][k]$ 表示将 $n$ 分成若干段，每段长度至少为 $k$：

• 情况1：第一段长度 $\ge k+1$，对应 $dp[n][k+1]$
• 情况2：第一段长度恰好为 $k$，剩下 $n-k$ 需要每段长度至少为 $k$，对应 $dp[n-k][k]$

2. 答案公式的正确性

考虑全胶面部分长度 $L = A+i$：

• $dp[L][A]$：将长度 $L$ 分成若干段，每段至少 $A$ 长
• $dp[L-1][A]$：将长度 $L-1$ 分成若干段，每段至少 $A$ 长
• 两者之差恰好表示"总长度为 $L$ 且最后一段恰好结束"的方案数

同样，部分胶面部分长度 $M = N-L$ 需要满足每段至少 $B$ 长。

---

复杂度分析

• 时间复杂度：$O(N^2)$
  • DP计算：$O(N^2)$
  • 答案计算：$O(N)$
• 空间复杂度：$O(N^2)$

对于 $N \le 1000$ 完全可行。

---

总结

本题是一道组合计数与整数划分的难题，主要考察：

1. 问题转化能力：将物理折叠问题转化为整数划分问题
2. 动态规划技巧：设计合适的DP状态表示划分方案
3. 组合计数思想：使用差分计算特定长度的方案数
4. 模运算处理：正确处理负数和模运算

算法的核心在于：

• 将折叠方案转化为胶带段的两种朝向的分布
• 使用DP计算满足最小长度限制的划分方案数
• 通过组合计算得到最终答案

这种"整数划分+组合计数"的方法是解决此类折叠/分割问题的典型思路，需要深入理解问题本质才能设计出正确的DP状态。