ABC214F - Substrings

問題

https://atcoder.jp/contests/abc214/tasks/abc214_f

略説

部分列dp

同じ文字列ならばindex列が辞書順最小になるように選択していくことで重複を回避する

nxt[i][j] := i以降で最初に出現する文字jのindex

dp[i] := i文字目までの文字列の種類数 (i文字めは必ず使う)

dp[nxt[i][j] (隣合うときは更にもう一つ進める)] += dp[i]

ACコード

#include <bits/stdc++.h>
using namespace std;

template <unsigned int MOD>
struct Modint {
    unsigned int x;
    constexpr Modint(): x(0) {}
    template <typename T>
    constexpr Modint(T _x) noexcept : x((_x%=MOD)<0 ? _x+MOD : _x) {}
    constexpr Modint inv() const noexcept {
        long long a = x, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b;
            swap(a, b);
            u -= t * v;
            swap(u, v);
        }
        return Modint(u);
    }
    constexpr Modint operator+() const noexcept {return *this;}
    constexpr Modint operator-() const noexcept {return Modint()-*this;}
    constexpr Modint &operator++() noexcept {
        if (++x == MOD) x = 0;
        return *this;
    }
    constexpr Modint &operator--() noexcept {
        if (x-- == 0) x += MOD;
        return *this;
    }
    constexpr Modint operator++(int) noexcept {
        Modint res = *this;
        ++*this;
        return res;
    }
    constexpr Modint operator--(int) noexcept {
        Modint res = *this;
        --*this;
        return res;
    }
    constexpr Modint &operator+=(const Modint &y) noexcept {
        if ((x+=y.x) >= MOD) x -= MOD;
        return *this;
    }
    constexpr Modint &operator-=(const Modint &y) noexcept {
        if (x < y.x) x += MOD;
        x -= y.x;
        return *this;
    }
    constexpr Modint &operator*=(const Modint &y) noexcept {
        x = (unsigned long long)x*y.x%MOD;
        return *this;
    }
    constexpr Modint &operator/=(const Modint &y) noexcept {return *this*=y.inv();}
    friend constexpr Modint operator+(const Modint &l, const Modint &r) {return Modint(l)+=r;}
    friend constexpr Modint operator-(const Modint &l, const Modint &r) {return Modint(l)-=r;}
    friend constexpr Modint operator*(const Modint &l, const Modint &r) {return Modint(l)*=r;}
    friend constexpr Modint operator/(const Modint &l, const Modint &r) {return Modint(l)/=r;}
    friend constexpr bool operator==(const Modint &l, const Modint &r) {return l.x==r.x;}
    friend constexpr bool operator!=(const Modint &l, const Modint &r) {return l.x!=r.x;}
    friend constexpr istream &operator>>(istream &is, Modint &y) {
        long long z;
        y = (is>>z, z);
        return is;
    }
    friend constexpr ostream &operator<<(ostream &os, const Modint &y) {return os<<y.x;}
};

using mint = Modint<1000000007>;

int N;
string S;
int nxt[2<<17][26];
mint dp[2<<17];

int main() {
    cin >> S;
    N = S.size();
    int last[26];
    fill(last, last+26, N+100);
    for (int i=N; i>=1; i--) {
        copy(last, last+26, nxt[i]);
        last[S[i-1]-'a'] = i;
    }
    copy(last, last+26, nxt[0]);
    dp[0] = 1;
    for (int i=0; i<N; i++) {
        for (int j=0; j<26; j++) {
            if (i && nxt[i][j]==i+1) {
                dp[nxt[nxt[i][j]][j]] += dp[i];
            } else {
                dp[nxt[i][j]] += dp[i];
            }
        }
    }
    mint ans = 0;
    for (int i=1; i<=N; i++) ans += dp[i];
    cout << ans << '\n';
}