P11928 题解

· · 题解

出现至少两次的本质不同子序列不好计数，容斥一下就可以变为两个问题：求本质不同子序列个数、求出现恰好一次的本质不同子序列个数。

求本质不同子序列个数

设 f_{i,j} 表示前 i 个数构成的以 j 为结尾的本质不同子序列个数。那么有转移：

f_{i,j}=\begin{cases} f_{i-1,j}, &s_i\ne j\\ \sum\limits_kf_{i-1,k}+1, &s_i=j \end{cases}

这表示对于一个子序列，每次选择的点都是尽量靠后的。这保证了只计算一次。

显然这个形式可以写成矩阵乘法的形式，然后直接上线段树维护矩阵乘法即可。此处时间复杂度 O(nk^3\log n)，其中 k=6。

求出现恰好一次的本质不同子序列个数

“出现恰好一次”等价于“既是第一个也是最后一个”。举个 abc 的例子。这说明这个子序列中的 a 前面不能有 a，这个子序列中的 a、b 之间不能有 a 或 b、这个子序列中的 b、c 之间不能有 b 或 c、这个子序列中的 c 后面不能有 c。如果满足了这些条件，那么可以推得 abc 这个子序列在串中唯一出现。

这个不是很好 DP，因为还好考虑到两个字符之间的字符集。但是因为是在线段树上做，所以可以改成区间信息合并。区间需要维护 f(x,y) 表示区间内以 x 开头 y 结尾的唯一出现子序列个数，p(x),s(x) 分别表示序列中第一个/最后一个 x 的前面/后面的字符集。合并过程为：

f(x,y)=\sum\limits_{a}\sum\limits_{b}[a,b \notin (s(a)\cup p(b))]f_l(x,a)f_r(b,y)

注意还需要特判某个唯一出现子序列在某一边的情况。

这样就可以做到 O(nk^4\log n) 了，由于 15s 的超长时限，应该可以通过。但是还可以优化。

容易发现这是一个类似矩阵乘法的东西，设 A_{i,j}=f_l(i,j),B_{i,j}=[i,j \notin (s(i)\cup p(j))],C_{i,j}=f_r(i,j)，那么显然 f(x,y)=(ABC)_{x,y}。时间复杂度 O(nk^3\log n)。

代码很好写：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 50005
const int MOD(998244353);

int n, q; string t;

struct Matrix{
    int n, m, a[7][7]; Matrix(){memset(a, 0, sizeof(a));}
    Matrix operator*(Matrix b){
        Matrix c; c.n = n; c.m = b.m;
        for (int i(0); i<n; ++i) for (int j(0); j<b.m; ++j) for (int k(0); k<m; ++k){
            (c.a[i][j] += a[i][k]*b.a[k][j]) %= MOD;
        }
        return c;
    }
    void print(){for (int i(0); i<n; ++i, cerr << '\n') for (int j(0); j<m; ++j) cerr << a[i][j] << ' ';}
};

namespace Seg{
    struct Node{Matrix f, g; int st, p[6], s[6];}tr[MAXN<<2];
    void modify(int p, int l, int r, int x, int k){
        if (l == r){
            tr[p].st = 1<<k; tr[p].p[k] = tr[p].s[k] = 0; tr[p].f.n = tr[p].f.m = 7; tr[p].g.n = tr[p].g.m = 6;
            for (int i(0); i<6; ++i) if (i ^ k) tr[p].p[i] = tr[p].s[i] = 63; tr[p].f.a[6][6] = 1;
            for (int i(0); i<6; ++i) for (int j(0); j<6; ++j) tr[p].f.a[i][j] = i == j || j == k;
            for (int i(0); i<6; ++i) tr[p].f.a[6][i] = i == k;
            for (int i(0); i<6; ++i) for (int j(0); j<6; ++j) tr[p].g.a[i][j] = i == j && j == k; return;
        }
        int mid((l+r)>>1); if (x <= mid) modify(p<<1, l, mid, x, k); else modify(p<<1|1, mid+1, r, x, k);
        tr[p].f = tr[p<<1].f * tr[p<<1|1].f; tr[p].st = tr[p<<1].st | tr[p<<1|1].st;
        for (int i(0); i<6; ++i) tr[p].p[i] = min(tr[p<<1].p[i], tr[p<<1|1].p[i]|tr[p<<1].st);
        for (int i(0); i<6; ++i) tr[p].s[i] = min(tr[p<<1|1].s[i], tr[p<<1].s[i]|tr[p<<1|1].st);
        Matrix yyx; for (int i(0); i<6; ++i) for (int j(0); j<6; ++j) yyx.a[i][j] = !((1<<i|1<<j)&(tr[p<<1].s[i]|tr[p<<1|1].p[j]));
        yyx.n = yyx.m = 6; tr[p].g = tr[p<<1].g * yyx * tr[p<<1|1].g;
        for (int i(0); i<6; ++i) for (int j(0); j<6; ++j){
            if (!(tr[p<<1].st>>i&1)) tr[p].g.a[i][j] += tr[p<<1|1].g.a[i][j];
            if (!(tr[p<<1|1].st>>j&1)) tr[p].g.a[i][j] += tr[p<<1].g.a[i][j];
        }
    }
}
int sol(){
    Matrix f(Seg::tr[1].f), g(Seg::tr[1].g); Matrix a; a.a[0][6] = a.n = 1; a.m = 7;
    a = a*f; int res(0); for (int i(0); i<6; ++i) (res += a.a[0][i]) %= MOD;
    for (int i(0); i<6; ++i) for (int j(0); j<6; ++j) (res += MOD-g.a[i][j]) %= MOD; return res;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> q >> t; t = ' ' + t; for (int i(1); i<=n; ++i) Seg::modify(1, 1, n, i, t[i]-'a'); cout << sol() << '\n';
    for (int x; q; --q){
        char c; cin >> x >> c; Seg::modify(1, 1, n, x, c-'a'); cout << sol() << '\n';
    }

    return 0;
}