1 条题解

  • 0
    @ 2026-11-15 13:56:27

    题目分析

    30 pts

    对于30%的数据,有 m=0m = 0。

    如何统计一个给定串不同的子序列个数?

    DP

    • last[i]last[i] 表示字符 s[i]s[i] 上一次出现的位置
    • f[i]f[i] 表示以第 ii 位结尾的新出现的不同子序列个数

    考虑加入一个新的 ii,那么所有以第 xx 位(last[i]≤x≤i−1last[i] \leq x \leq i - 1)结尾的新出现的子序列,都可以加上一个 ii,得到一个新的子序列。

    如何证明 x(1≤x≤last[i]−1)x(1 \leq x \leq last[i] - 1) 接上 s[i]s[i] 不会形成新的子序列?

    反证法

    • 如果以 last[i]−1last[i] - 1 之前的某个位置为结尾的子序列接上第 ii 位,会产生一个新的子序列,那么之前的子序列直接加上 last[i]last[i] 也可以产生这个新的子序列。
    • 与这个子序列在 ii 第一次出现矛盾。

    于是我们得到方程 f[i]=∑j=last[i]i−1f[j]f[i] = \sum_{j=last[i]}^{i-1} f[j]。

    用树状数组或前缀和优化即可。

    100 pts

    对于100%的数据,有 0≤n,m≤1000000,1≤k≤260 \leq n, m \leq 1000000, 1 \leq k \leq 26。

    记 g[i]g[i] 为 f[i]f[i] 的前缀和 f[i]=g[i−1]−g[last[i]−1]f[i] = g[i - 1] - g[last[i] - 1]。

    每次贪心选取使 last[i]−1last[i] - 1 最小即可。

    时间复杂度 O((n+m)×26)O((n + m) \times 26),空间复杂度 O(n)O(n)。

    很容易发现 f[i]f[i] 与 f[last[i]]f[last[i]] 有关,所有变量都可开成临时变量。内存可以优化为 O(k)O(k)。

    • 1

    信息

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