会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
暴力做法（部分分）
先给一个直接的做法，它不是满分做法，只能通过 n 较小的数据。
融合树的根把区间 [l,r] 分成 [l,k] 与 [k+1,r]，左右两边再各自是一棵融合树。于是可以写一个递归 dfs(l, r)：枚举根的分割点 k，用前缀和求出两段字节长度 a,b，若 ∣a−b∣>D 就跳过，否则递归求两边的方案数并相乘累加。l=r 时返回 1。
这个递归没有记忆化，相同的子区间会被反复计算。约束恒成立时，调用次数满足 C(n)=1+2∑i=1n−1C(i)，即 C(n)=3n−1，时间复杂度为 O(3n)，空间复杂度为 O(n)（递归栈）。实测 C++ 在 n≤18 左右可以在时限内跑完，Python 大约只能到 n≤13。n 稍大或 D 很大时一定超时，满分需要下面的区间 DP。
Python
