Fady and Stable Arrays#12482

Fady and Stable Arrays (Розбір)

Автор задачі:	Fady Rafat (FADY)
Підготував:	Fady Rafat (FADY)
Відредагував:	Hasan Saleh (MathModel)

Розв'язок

Загальна ідея: Потрібно порахувати кількість різних стабільних масивів (у яких жодні два сусідніх елементи не рівні), які можна отримати, застосовуючи операції до початкового масиву.

Ключове спостереження:

Коли ми застосовуємо операцію до двох сусідніх рівних елементів $a_{i} = a_{i + 1} = v$ a_i = a_{i+1} = v, ми замінюємо їх одним елементом зі значенням $v + 1$ v + 1. Це означає, що ми можемо «злити» суміжні блоки однакових значень у більші значення.

Більш формально, неперервний підмасив однакових значень $[v, v, \dots, v]$ [v, v, \ldots, v] довжини $2^{k}$ 2^k можна злити в один елемент зі значенням $v + k$ v + k.

Формулювання ДП:

Нехай $L [i] [v]$ = найлівіший початковий індекс такий, що підмасив $a [L [i] [v] \dots i]$ a[L[i][v] \ldots i] можна злити у значення $v$ .

Це можна обчислити так:

$L [i] [a [i]] = i$ L[i][a[i]] = i (один елемент зливається сам у себе)
$L [i] [v] = L [L [i] [v - 1] - 1] [v - 1]$ L[i][v] = L[L[i][v-1] - 1][v-1], якщо підмасив, що закінчується в $i$ і зливається у $v - 1$ v-1, може бути передований іншим підмасивом, який також зливається у $v - 1$ v-1

Нехай $d p [i] [v]$ dp[i][v] = кількість стабільних масивів, що закінчуються в позиції $i$ з останнім елементом зі значенням $v$ .

Нехай $an s [i]$ = загальна кількість стабільних масивів, що закінчуються в позиції $i$ .

Перехід:

Якщо $L [i] [v] = 0$ L[i][v] = 0: $d p [i] [v] + = 1$ dp[i][v] += 1 (весь префікс зливається у $v$ )
Інакше: $d p [i] [v] + = an s [L [i] [v] - 1] - d p [L [i] [v] - 1] [v]$ dp[i][v] += ans[L[i][v] - 1] - dp[L[i][v] - 1][v]

Ми віднімаємо $d p [L [i] [v] - 1] [v]$ dp[L[i][v] - 1][v], щоб уникнути двох суміжних блоків з однаковим значенням $v$ (умова стабільності).

Нарешті:

an s [i] = v \sum d p [i] [v]

ans[i] = \sum_{v} dp[i][v]

Відповідь — $an s [n - 1]$ ans[n-1].

Аналіз складності:

Обчислення $L [i] [v]$ : $O (n \cdot V)$ \mathcal{O}(n \cdot V), де $V = 80 + lo g_{2} (n) \approx 102$ V = 80 + \log_2(n) \approx 102.

Обчислення $d p$ : $O (n \cdot V)$ \mathcal{O}(n \cdot V).

Загальна складність на один тест: $O (n \cdot V)$ \mathcal{O}(n \cdot V).

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

const int MOD = 1e9 + 7;
const int MAX_V = 102;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    
    vector<vector<int>> L(n, vector<int>(MAX_V, -1));
    vector<vector<long long>> dp(n, vector<long long>(MAX_V, 0));
    vector<long long> ans(n, 0);
    
    for (int i = 0; i < n; i++) {
        L[i][a[i]] = i;
        for (int v = a[i] + 1; v < MAX_V; v++) {
            int right_start = L[i][v - 1];
            if (right_start > 0) {
                int left_start = L[right_start - 1][v - 1];
                if (left_start != -1)
                    L[i][v] = left_start;
            }
        }
        for (int v = 0; v < MAX_V; v++) {
            int start = L[i][v];
            if (start == -1) continue;
            if (start == 0) {
                dp[i][v] = (dp[i][v] + 1) % MOD;
            } else {
                long long ways = (ans[start - 1] - dp[start - 1][v] + MOD) % MOD;
                dp[i][v] = (dp[i][v] + ways) % MOD;
            }
            ans[i] = (ans[i] + dp[i][v]) % MOD;
        }
    }
    
    cout << ans[n - 1] << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}