# ARC169-C Not So Consecutive

2005diff
https://atcoder.jp/contests/arc169/tasks/arc169_c

## 解法

動的計画法を考える。

DP[i][j][k] := ith/末尾の項がj/末尾の項がk項連続している ような列としてありえる数

遷移を考える。

$A_{i} = -1$なら$v = 1, 2, \dots, N$について、$A_{i} \ne -1$なら$v = A_{i}$について以下のように遷移する。
1. DP[i + 1][v] <- DP[i][v]とする
2. DP[i + 1][v]を右(?)に1シフトする
3. DP[i + 1][v][1] に DP[i]の総和 - DP[i][v]の総和 を代入する

答えはDP[N]の総和である。

これをそのまま愚直に計算すると$O(N^3)$かかる。

欲しいものがDP[N]の総和であること、DP[i + 1][v][1]の計算に全体の総和と行の総和しか利用しないことに注目する。DPテーブルを陽に持たなくても「現在のDPの総和」と「現在のDPのv行目の総和」を持っていればできるんじゃないかと疑う。

実際そうで、「右に1シフトする」を「$i + \text{hoge}$回目の遷移でDP[i][v][1]が行の総和から減算される」と言い換える。この$\text{hoge}$を毎回適切に計算してやれば良い。

全体$O(N^2)$で解けた。

## 実装

#include <bits/stdc++.h>

const long long MOD{998244353};

long long add(long long a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}

long long inv(long long v) {
    return (v ? MOD - v : v);
}

long long sub(long long a, long long b) {
    return add(a, inv(b));
}

int N;
int A[5010];

bool check(const std::vector<int>& A) {
    std::vector<std::pair<int, int>> B;
    for (auto x : A) {
        if (B.empty() or B.back().first != x) {
            B.push_back(std::pair{ x, 1 });
        }
        else {
            B.back().second++;
        }
    }
    for (auto [x, len] : B) {
        if (len >= x + 1) return false;
    }
    return true;
}

void brute() {
    std::vector<int> cur;
    long long ans{};
    auto dfs{[&](auto dfs, int i) -> void {
        if (i == (int)N) {
            ans = add(ans, (int)check(cur));
        }
        else {
            if (A[i] == -1) {
                for (int j{1} ; j <= N ; j++) {
                    cur.push_back(j);
                    dfs(dfs, i + 1);
                    cur.pop_back();
                }
            }
            else {
                cur.push_back(A[i]);
                dfs(dfs, i + 1);
                cur.pop_back();
            }
        }
    }};
    dfs(dfs, 0);
    std::cout << ans << '\n';
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    std::cin >> N;
    for (int i{} ; i < N ; i++) {
        std::cin >> A[i];
    }
    long long sumAll{};
    std::vector<long long> rowSum(N + 1);
    std::vector reserveSub(N + 1, std::vector<long long>(N + 1));
    auto reserve{[&](int i, int v, long long val) -> void {
        // std::cout << i << ',' << v << " de " << val << " wo hiku" << std::endl;
        reserveSub[i][v] = add(reserveSub[i][v], val);
    }};
    // A_1の分を計算
    // std::cout << "calc A[1]" << std::endl;
    {
        int j{};
        while (j < N and (A[j] == -1 or A[0] == A[j])) j++;
        int k{j};
        while (k < N and (A[k] == -1 or A[j] == A[k])) k++;
        for (int v{1} ; v <= N ; v++) if (A[0] == v or A[0] == -1) {
            sumAll = add(sumAll, 1);
            rowSum[v] = add(rowSum[v], 1);
            int idx{std::min(A[0] == -1 and j < N and A[j] == v ? k : j, v)};
            reserve(idx, v, 1);
        }
    }
    for (int i{1} ; i < N ; i++) {
        // std::cout << "calc A[" << i + 1 << "]\n";
        std::vector<long long> cur(N + 1);
        for (int v{1} ; v <= N ; v++) if (A[i] == v or A[i] == -1) {
            cur[v] = sub(sumAll, rowSum[v]); 
        }
        for (int v{1} ; v <= N ; v++) {
            long long kiyo{sub(cur[v], reserveSub[i][v])};
            sumAll = add(sumAll, kiyo);
            rowSum[v] = add(rowSum[v], kiyo);
        }
        int j{i};
        while (j < N and (A[j] == -1 or A[j] == A[i])) j++;
        int k{j};
        while (k < N and (A[k] == -1 or A[j] == A[k])) k++;
        for (int v{1} ; v <= N ; v++) {
            int idx{std::min(A[i] == -1 and j < N and v == A[j] ? k : j, i + v)};
            reserve(idx, v, cur[v]);
        }
    }
    std::cout << sumAll << '\n';
    // brute();
}

[提出](https://atcoder.jp/contests/arc169/submissions/58280220)

## 感想

「簡単に思いつく愚直から$N$を一個落とす」問題は得意だと自負しているが、それでも1時間以上かかってしまった。

シフトの言い換えが大変だった。