AGC031 Reversi

atcoder.jp

なんか同じ考え方の人が全然いないので書きます

とすれば, 遷移は高々「被覆を開始する」「被覆を終了する」だけになるので, disjointに気をつけてDPして終わりです

int main() {
    int N;
    cin >> N;
    int A[N];
    rep(i, N) cin >> A[i];
    mint DP[200001] = {};
    DP[0] = 1;
    rep(i, N) if (i == N - 1 or A[i] != A[i + 1]) {
        mint a = DP[0], b = DP[A[i]];
        DP[A[i]] += a;
        DP[0] += b;
    }
    cout << DP[0] << endl;
}