1 条题解

  • 0
    @ 2026-11-12 21:58:09

    [T] Permutation(dp_t)题解

    题意简述

    给定长度 N−1N-1 的 </> 串,求满足相邻比较关系的 (1..N)(1..N) 排列个数  mod 109+7\bmod 10^9+7。

    思路

    状态设计

    一个关键技巧:只关心最后一位在已用数字中的相对排名,而不关心具体值。设

    $$f_{i,j} = \text{用 } 1..i \text{ 构成的前缀排列中,末尾元素在 } 1..i \text{ 中排名为 } j \text{ 的方案数}.$$

    转移

    处理第 ii 位(对应 ss 的第 i−1i-1 个字符):

    • 若 si−1=s_{i-1} = <(要求 pi−1<pip_{i-1} < p_i):上一位排名 k<jk < j:
    fi,j=∑k<jfi−1,k.f_{i,j} = \sum_{k<j} f_{i-1,k}.
    • 若 si−1=s_{i-1} = >(要求 pi−1>pip_{i-1} > p_i):上一位排名 k≥jk \ge j:
    fi,j=∑k≥jfi−1,k.f_{i,j} = \sum_{k \ge j} f_{i-1,k}.

    前者用前缀和、后者用后缀和,O(1)O(1) 转移。答案 ∑jfN,j\sum_j f_{N,j}。

    为什么"相对排名"够用

    插入新元素时,原有元素的相对顺序不变;把排名 jj 的新元素插到末尾,"上一位在原 i−1i-1 个中的排名"与"在新 ii 个中的排名"之间的比较关系,恰好等价于数值比较。这是本题最精妙的一步。

    复杂度

    时间 O(N2)≤9×106O(N^2) \le 9\times10^6,空间 O(N)O(N)。

    参考代码

    #include <cstdio>
    #include <vector>
    using namespace std;
    const long long MOD = 1000000007LL;
    
    int main() {
        int n;
        static char s[3005];
        scanf("%d %s", &n, s);
        vector<long long> f(n + 1, 0), pre(n + 2, 0);
        f[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i - 1; j++) pre[j] = (pre[j - 1] + f[j]) % MOD;
            for (int j = i; j >= 1; j--) {
                if (s[i - 2] == '<') f[j] = pre[j - 1];
                else f[j] = (pre[i - 1] - pre[j - 1] + MOD) % MOD;
            }
        }
        long long ans = 0;
        for (int j = 1; j <= n; j++) ans = (ans + f[j]) % MOD;
        printf("%lld\n", ans);
        return 0;
    }
    

    易错点

    1. 字符下标错位:处理第 ii 位用的是 s[i-2](0 起)。
    2. < 用 pre[j-1],> 用 pre[i-1] - pre[j-1]——符号写反是最常见错误。
    3. 倒序更新 f[j],或先把 pre 算好(本解先算 pre,顺序无关)。
    4. pre 每轮只用前 i−1i-1 项,别沿用上一轮的长度。

    数据说明

    共 16 组:3 组官方样例;N=2N=2 的 </>;N=3N=3 全 </全 >;N=4N=4 的 <><;N=10/100/500N=10/100/500 随机;N=3000N=3000 随机三组、全 <(答案 11)、全 >(答案 11)。

    • 1

    信息

    ID
    29
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    1
    已通过
    1
    上传者