題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🔵 CF367E. Sereja and Intervals

Problem Statement

題目簡述

給定整數 n,m,xn,m,x。需要寫出一個長度為 nn 的有序區間序列，每個區間都是 [li,ri][l_i,r_i]，滿足 1≤li≤ri≤m1 \le l_i \le r_i \le m。
序列中不能存在某個區間被另一個區間包含，也就是不能有兩個區間 [l1,r1][l_1,r_1]、[l2,r2][l_2,r_2] 滿足 l2≤l1≤r1≤r2l_2 \le l_1 \le r_1 \le r_2。
此外，至少要有一個區間的左端點等於 xx。
求合法有序區間序列的數量，答案對 109+710^9+7 取模。

Constraints

約束條件

  • 1≤n⋅m≤1000001 \le n \cdot m \le 100000
  • 1≤x≤m1 \le x \le m
  • 所有輸入皆為整數

思路：Open and Close Interval Trick

Open and Close Interval Trick

[Tutorial] Non-trivial DP Tricks and Techniques

核心技巧是把「選 nn 個互不包含的區間」改寫成「在值域上放置 nn 個左端點與 nn 個右端點」。這樣就不需要直接枚舉區間，而是從左到右掃描每個座標，維護目前已經放了多少左端點、多少右端點。

為什麼可以只看端點數量

先把所有區間按照左端點從小到大排序。若有兩個區間滿足左端點較小、右端點卻不小於另一個區間的右端點，那麼後者就會被前者包含，違反條件。

因此，在合法方案中，左端點排序後，右端點也必須按照同樣順序遞增。也就是說，一旦選好了所有左端點位置與所有右端點位置，合法配對方式其實是唯一的：第 kk 小的左端點配第 kk 小的右端點。

關鍵轉換

問題等價於在 11 到 mm 的座標上放端點，使得任意前綴中右端點數量不超過左端點數量，最後左、右端點都各有 nn 個，且座標 xx 必須放一個左端點。

這個前綴限制和括號序列很像：掃描到某個位置時，若右端點已經比左端點多，就表示有某個區間必須在尚未開始前就結束，這不可能形成合法配對。

左端點不能重複

若兩個區間左端點相同，右端點較小的那個一定會被右端點較大的那個包含。因此每個座標最多放一個左端點；這也解釋了為什麼當 n>mn>m 時答案必定為 00。

掃描時的四種選擇

對每個座標，只需要關心目前已放置的左端點數量與右端點數量。處理一個普通座標時，有四種選擇：

  1. 不放任何端點。
  2. 放一個左端點。
  3. 放一個右端點，前提是放完後右端點數量不超過左端點數量。
  4. 同時放一個左端點與一個右端點。

第四種看起來像是同一個座標上同時出現開始與結束。這在端點模型中是必要的，因為合法區間允許 l=rl=r，也允許某個區間在此結束、另一個區間在此開始。由於最後會按照排序後的位置唯一配對，DP 不需要在當下判斷這兩個端點屬於哪個區間。

座標 xx 的限制

題目要求至少一個區間的左端點等於 xx。由於左端點不能重複，所以這等價於「座標 xx 必須放左端點」。因此掃描到 xx 時，不能選擇「什麼都不放」或「只放右端點」。

狀態與轉移

狀態定義

設 f[i][a][b]f[i][a][b] 表示處理完座標 1∼i1\sim i 後，已經放置 aa 個左端點、bb 個右端點的方案數。其中必須滿足：

  • 0≤b≤a≤n0 \le b \le a \le n：任意前綴中，右端點數量不能超過左端點數量。
  • 每個座標最多新增一個左端點，因為左端點不能重複。

初始狀態為：

f[0][0][0]=1f[0][0][0]=1

其餘狀態皆為 00。程式中用二維表保存目前掃描前綴的狀態，並用滾動陣列省掉座標維度。

轉移方程：刷表法

下面使用的是「刷表法」：枚舉上一層已經存在的狀態，然後把它的方案數貢獻到下一層能到達的狀態。也就是從 f[i−1][a][b]f[i-1][a][b] 往外推到若干個 f[i][⋅][⋅]f[i][\cdot][\cdot]，而不是固定某個新狀態再反過來枚舉它有哪些來源。

考慮目前正在處理的座標 ii，從狀態 (a,b)(a,b) 出發，記目前方案數為 f[i−1][a][b]f[i-1][a][b]。

若 i≠xi\ne x，可以不放任何端點：

f[i][a][b]+=f[i−1][a][b]f[i][a][b] \mathrel{+}= f[i-1][a][b]

若 a+1≤na+1\le n，可以放一個左端點：

f[i][a+1][b]+=f[i−1][a][b]f[i][a+1][b] \mathrel{+}= f[i-1][a][b]

若 i≠xi\ne x 且 b+1≤ab+1\le a，可以放一個右端點：

f[i][a][b+1]+=f[i−1][a][b]f[i][a][b+1] \mathrel{+}= f[i-1][a][b]

若 a+1≤na+1\le n，可以同時放一個左端點與一個右端點：

f[i][a+1][b+1]+=f[i−1][a][b]f[i][a+1][b+1] \mathrel{+}= f[i-1][a][b]

在座標 xx，因為必須放左端點，所以「不放任何端點」與「只放右端點」兩種轉移被禁止，只保留包含新增左端點的兩種轉移。

目標答案

最後取左右端點都剛好為 nn 的方案數。這時 DP 算到的是「無標號區間集合」的端點選法；題目問的是有序序列，nn 個區間可以任意排列，所以還要乘上 n!n!。

ans=f[m][n][n]⋅n!(mod109+7)\mathrm{ans}=f[m][n][n]\cdot n! \pmod {10^9+7}

小結

可復用模型是：當一類物件可以由「開啟事件」與「關閉事件」描述，且合法性只依賴目前開啟數量或前綴平衡時，可以嘗試從左到右掃描事件位置，把原本複雜的配對問題壓成端點數量 DP。

複雜度分析

  • 時間複雜度：O(mn2)\mathcal{O}(mn^2)。外層掃描 mm 個座標，每個座標枚舉左右端點數量。由於 n⋅m≤100000n \cdot m \le 100000 且 n≤mn \le m 才可能有解，實際可通過。
  • 空間複雜度：O(n2)\mathcal{O}(n^2)，使用滾動陣列保存目前座標的 DP 狀態。
為什麼 O(mn2)\mathcal{O}(mn^2) 能過？

乍看三層枚舉很大，但因為 n>mn>m 答案直接為 00，所以只需要考慮 n≤mn\le m 的情況。又因為題目保證 n⋅m≤100000n\cdot m\le 100000，可推出 n2≤n⋅m≤100000n^2\le n\cdot m\le 100000，也就是 n≲316n\lesssim 316。因此狀態表最多約 n2n^2，外層總掃描量受 mn2=(n⋅m)nmn^2=(n\cdot m)n 控制，在最壞可行範圍內約為 3.16×1073.16\times 10^7 級別，可以通過。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from functools import reduce

MOD = int(1e9 + 7)


def solve():
    n, m, x = map(int, input().split())

    if n > m:
        print(0)
        return

    # f[i][j][k] 表示：考慮到第 i 個坐標，已選了 j 個左端點，k 個右端點的方案數
    f = [[0] * (n + 1) for _ in range(n + 1)]
    f[0][0] = 1

    for i in range(1, m + 1):
        nf = [[0] * (n + 1) for _ in range(n + 1)]
        for j in range(min(i, n) + 1):
            for k in range(j + 1):
                v = f[j][k] % MOD
                if not v: continue
                # 1. 什麼都不做
                if i != x:
                    nf[j][k] += v
                # 2. 放一個左端點
                if j + 1 <= n:
                    nf[j + 1][k] += v
                # 3. 放一個右端點
                if i != x and k + 1 <= j:
                    nf[j][k + 1] += v
                # 4. 同時放左端點和右端點
                if j + 1 <= n:
                    nf[j + 1][k + 1] += v
        f = nf

    # 最終答案為 f[n][n] * n!
    print(f[n][n] * reduce(lambda x, y: x * y % MOD, range(1, n + 1)) % MOD)

if __name__ == '__main__':
    solve()