原题概述

有n座城池，编号为1-n，每个城池可选择 建/不建 防御关卡，同时给了m个约束，每个约束用区间[l, r]表示，代表编号l-r区间至少有1个防御关卡，问总共有多少种建造方案？

输入：第一行n,m，接下来m行代表每个约束中的l, r，输出方案数对1e9+7取余结果

思路

代码

from functools import lru_cache
MOD = 10 ** 9 + 7
modpow2 = lambda exp: pow(2, exp, MOD)
n, m = map(int, input().split())
pos = sorted([tuple(map(int, input().split())) for _ in range(m)])

@lru_cache(maxsize=None)
def solve(k, lastl, lastr):
    if k < len(pos):
        l, r = pos[k][0] - 1, pos[k][1]
        if l >= lastr:
            # [lastl, lastr) 至少1个, [lastr, l) 任取, 递归考虑[l, r)和剩下区间
            ans = (modpow2(l - lastl) - modpow2(l - lastr)) * solve(k + 1, l, r)
        elif r <= lastr:
            # [lastl, l) 任取, 递归考虑[l, r)和剩下区间
            ans = modpow2(l - lastl) * solve(k + 1, l, r)
        else:
            # 情况1: [lastl, l) 至少1个, 递归考虑[l, r) 和剩下区间
            # 情况2: [lastl, l) 都没有, 递归考虑[l, lastr) 和剩下区间
            ans = (modpow2(l - lastl) - 1) * solve(k + 1, l, r) + solve(k + 1, l, lastr)
    else:
        # 边界情况，[lastl, lastr) 至少1个, [lastr, n) 任取
        ans = modpow2(n - lastl) - modpow2(n - lastr)
    return ans % MOD

print(solve(0, -1, 0))