浙江科技学院第17届大学生程序设计竞赛（公开赛）F

每个本质不同子序列的贡献是1。本题的期望可以转化为概率。
由于序列自动机就是子序列的最小表示。
我们依据序列自动机进行概率转移。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;

const int N = 1e5 + 100;
const int M = 26 + 2;
const int MOD = 998244353;

int n;
int nex[N][M];
ll pp[N], qq[N], dp[N];
char str[N];

ll qpow(ll x, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % MOD;
        n /= 2;
        x = x * x % MOD;
    }
    return res;
}

void upd(ll &a, ll b) {
    a = (a + b) % MOD;
}

int main() {
    //freopen("0.txt", "r", stdin);
    scanf("%d%s", &n, str + 1);
    ll R100 = qpow(100, MOD - 2);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", qq + i);
        pp[i] = (100 - qq[i]) * R100 % MOD;
        qq[i] = qq[i] * R100 % MOD;
    }
    dp[0] = pp[0] = 1;
    memset(nex, 0x3f3f3f3f, sizeof(nex));
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j < 26; j++) nex[i][j] = nex[i + 1][j];
        nex[i][str[i] - 'a'] = i;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 26; j++) {
            if (nex[i + 1][j] <= n) {
                upd(dp[nex[i + 1][j]], dp[i] * pp[i]);
            }
        }
        if (nex[i + 1][str[i] - 'a'] <= n)
            upd(dp[nex[i + 1][str[i] - 'a']], dp[i] * qq[i]);
    }
    ll ans = 1;
    for (int i = 1; i <= n; i++) ans = (ans + dp[i] * pp[i]) % MOD;
    printf("%lld\n", ans);
    return 0;
}