题解：AT_arc138_e [ARC138E] Decreasing Subsequence

Daniel1234 · 2025-12-12 16:56:09 · 题解

来一篇不用斯特林数的题解（

思路

我们考虑枚举钦定子序列的开头 i，然后我们把序列分成两部分：[1 \sim i-1] 和 [i \sim n]，考虑两部分之间可能的交集就是后一部分可能有一些位置会填前一部分的值，即 [1 \sim i-1] 这些值。

所以我们延后钦定：

由于是恰好所以最后两部分的 j 相同，再枚举 i 即可直接求答案，注意可能要特判 i 位置的贡献。

时间复杂度：O(n^2)。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
int n, k;
int pre[5005][5005], suf[5005][5005];
int fac[5005], inv[5005], invfac[5005];
int C(int n, int m){
    if(min(n, m) < 0 || n < m)return 0;
    return fac[n] * invfac[m] % mod * invfac[n-m] % mod;
}
signed main(){
    fac[0] = invfac[0] = 1;
    fac[1] = invfac[1] = 1;
    inv[1] = 1;
    for(int i = 2; i <= 5e3; i++){
        fac[i] = fac[i-1] * i % mod;
        inv[i] = mod - (mod / i) * inv[mod % i] % mod;
        invfac[i] = invfac[i-1] * inv[i] % mod;
    }
    cin >> n >> k;
    pre[0][0] = 1;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= i; j++){
            if(!pre[i][j])continue;
            pre[i][j] %= mod;
            pre[i+1][j] += pre[i][j];
            pre[i+1][j+1] += pre[i][j];
            if(j)pre[i+1][j-1] += pre[i][j] * j % mod;
            pre[i+1][j] += pre[i][j] * (j+1) % mod;
        }
    }
    suf[n+1][0] = 1;
    for(int i = n+1; i >= 1; i--){
        for(int j = 0; j <= n-i+1; j++){
            if(!suf[i][j])continue;
            suf[i][j] %= mod;
            suf[i-1][j+1] += suf[i][j];
            suf[i-1][j] += suf[i][j];
            suf[i-1][j] += suf[i][j] * (j+1) % mod;
            if(j)suf[i-1][j-1] += suf[i][j] * j % mod;
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            if(j >= k)ans += pre[i-1][j] * suf[i+1][j-1] % mod * C(j-1, k-1) % mod * C(j, k) % mod * fac[j-k] % mod;
            if(j+1 >= k)ans += pre[i-1][j] * suf[i+1][j] % mod * C(j, k-1) % mod * C(j+1, k) % mod * fac[j+1-k] % mod;
        }
    }
    cout << ans % mod << "\n";
    return 0;
}