AtCoder Regular Contest 125 D - Unique Subsequence

D - Unique Subsequence

考えたこと

dp[i] := iを先頭に使ったときの答えとして

iを後ろから更新する時にどう遷移するかを考える

以降A[i]の後ろにA[j]から始まる部分列を付け加えられる事を

iにjを加えられると呼ぶことにする

上の図を見るとA[i]==A[j]かつi<jを満たす最小のjについて

iにk(j+1<=k<=N)を加えることは出来ないことが分かる。

なぜなら、jにkを加えることで同じ部分列が作れてしまうためである。

反対に、iにk(i+1<=k<=j)を加えることは出来る

よってiを後ろから見ていき

dp[i] = sigma(k=i+1~j,  dp[k])

dp[j] = 0

とすればいい、ちなみにdp[j]を0にする理由は上に書いたようにjを先頭にした時の部分列はiを先頭にして同じものが作れてしまうため、問題文の条件に反するから。

この操作はbinary indexed treeやセグメントツリーで出来る

void solve() {
    int N;
    vi A(N);
    cin >> N;
    for (auto &a : A)cin >> a;
    seg<modint> dp(N + 1);
    vi pos(N + 1, N);
    rer(i, N - 1) {
        int j = pos[A[i]];
        modint sum = dp(i + 1, j + 1);
        if (j == N)sum++;//自分だけ使う
        dp.update(i, sum);

        pos[A[i]] = i;
        dp.update(j, 0);
    }
    cout<dp(0, N+1)<<endl;
}