您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

BZOJ 4361 isn 詳解：序列刪除操作計數與 DP + 容斥原理

編輯：關於C++

題目大意

給定長度 n 的序列 A[1..n]。若序列非非遞減（即存在 A[i] > A[i+1]），必須刪除一個元素，重複此操作直到序列非遞減。求不同操作方案數，模 10^9+7。n ≤ 2000。

範例：A = [1, 7, 5, 3] → 輸出 18。

核心轉化

「反覆刪除直到非遞減」等價於：保留一個最長非遞減子序列 (LNDS)，刪除其餘元素。但順序不同視為不同方案。

設最終保留長度為 k 的非遞減子序列，刪除順序為其餘 n-k 個元素的全排列：(n-k)! 種。但不同保留子序列可能導致相同最終序列，需去重。

DP 計算非遞減子序列計數

定義

f[i][j]：以 A[i] 結尾、長度為 j 的非遞減子序列個數
g[j]：長度為 j 的非遞減子序列總數 = Σ f[i][j]

轉移

f[i][j] = Σ f[k][j-1]，其中 k < i 且 A[k] ≤ A[i]。

直接雙重循環為 O(n³)。優化：對值域建立樹狀數組 (Fenwick Tree)，每層 j 維護一棵樹狀數組，按值域查詢前綴和。時間 O(n² log n)。

值域離散化

A[i] 範圍未知，先排序去重映射到 [1..m]（m ≤ n）。

容斥原理計算方案數

設 g[k] 為長度為 k 的非遞減子序列數。保留長度 k 子序列的方案數為 g[k] * (n-k)!。但長度 k+1 的子序列包含長度 k 的子序列，會被重複計算。

容斥公式：

ans = Σ [ g[k] * (n-k)! - g[k+1] * (n-k-1)! * (k+1) ]

其中 g[k+1] * (k+1) 為長度 k+1 子序列中每個子序列包含的長度 k 子序列數（刪除 1 個元素）。

完整代碼邏輯

const int MOD = 1e9+7;
int n, A[MAXN], B[MAXN], id[MAXN];
ll f[MAXN][MAXN], g[MAXN], fac[MAXN];
ll bit[MAXN][MAXN];  // bit[j][v]：長度 j、值 ≤ v 的子序列數

void add(int j, int v, ll val) {
    for (; v <= n; v += v&-v) bit[j][v] = (bit[j][v] + val) % MOD;
}
ll query(int j, int v) {
    ll res = 0;
    for (; v; v -= v&-v) res = (res + bit[j][v]) % MOD;
    return res;
}

int main() {
    n = read();
    for (int i=1; i<=n; ++i) A[i] = B[i] = read();
    
    // 離散化
    sort(B+1, B+n+1);
    int m = unique(B+1, B+n+1) - B - 1;
    for (int i=1; i<=n; ++i) id[i] = lower_bound(B+1, B+m+1, A[i]) - B;
    
    // 階乘預處理
    fac[0] = 1;
    for (int i=1; i<=n; ++i) fac[i] = fac[i-1] * i % MOD;
    
    // DP + BIT
    add(0, 1, 1);  // 空子序列
    for (int i=1; i<=n; ++i) {
        for (int j=i; j>=1; --j) {
            f[i][j] = query(j-1, id[i]);
            add(j, id[i], f[i][j]);
        }
    }
    
    // 統計 g[j]
    for (int i=1; i<=n; ++i)
        for (int j=i; j<=n; ++j)
            g[j] = (g[j] + f[i][j]) % MOD;
    
    // 容斥計算答案
    ll ans = 0;
    for (int k=1; k<=n; ++k) {
        ll term1 = g[k] * fac[n-k] % MOD;
        ll term2 = g[k+1] * fac[n-k-1] % MOD * (k+1) % MOD;
        ans = (ans + term1 - term2) % MOD;
    }
    ans = (ans + MOD) % MOD;
    printf("%lld\n", ans);
    return 0;
}