SubSequence

Xem PDF
Tác giả:
admin
Dạng bài
Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

An đang tìm kiếm các dãy con biến đổi của một dãy cho trước \(a = (a_1, a_2, …, a_n)\).

Với một dãy số, nếu An bỏ bớt một số phần tử bất kỳ nào của nó (có thể số lượng bỏ bớt là 0) thì thu được một dãy con của nó. Cụ thể hơn, dãy con của dãy \(a\) là dãy bất kỳ (\(a_{i_1}, a_{i_2}, ... , a_{i_k}\)), trong đó \(1 \leq i_1 < i_2 < … < i_k \leq n\).

Một dãy con biến đổi là một dãy con mà cứ hai phần tử đứng cạnh nhau thì khác nhau. Ví dụ, dãy (\(1, 3, 1, 2\)) là dãy con biến đổi của dãy (\(1, 2, 3, 1, 3, 2, 2\)). Giờ An muốn biết có bao nhiêu dãy con biến đổi riêng biệt và khác rỗng của một dãy cho trước. Hai dãy con được xem là riêng biệt nếu vị trí tương ứng với chúng trong dãy \(a\) là khác nhau. Ví dụ, dãy (\(1, 2, 3, 1, 3, 2, 2\)) có 2 dãy con biến đổi riêng biệt cùng có dạng là (\(1, 3, 1, 2\)).

Input

  • Dòng đầu tiên chứa 1 số nguyên \(n\) (\(2 \leq n \leq 5 \times 10^5\)) cho biết độ dài của dãy \(a\).
  • Dòng thứ hai có \(n\) số nguyên \(a_i\) (\(1 \leq a_i \leq 5 \times 10^5\)).

Output

  • Một dòng in một số nguyên duy nhất: số lượng các dãy con biến đổi khác rỗng của dãy đầu vào theo modulo \(\ 10^9 + 7\).

Example

Test 1

Input 
4
1 2 1 1
Output 
9

Bình luận


  • 0
    SPyofgame    2:35 p.m. 13 Tháng 6, 2020 ← đã chỉnh sửa

    Spoiler Alert

    Hint 1

    • Xét các trường hợp khi số hiện tại khác hay giống số trước nó --> công thức quy hoạch động

    Hint 2

    • Nhận xét: Nếu phần tử hiện tại bằng phần tử trước đó, thì số cách bằng lượng được tính toán trước đó

    Có một lượng cal dãy nối với a[i - 1] để tạo thành dãy con biến đổi

    Thì tương tự cũng có một lượng cal dãy như thế nối với a[i] = a[i - 1]

    • Nhận xét: Nếu phần tử hiện tại là phần tử chưa từng xuất hiện trước đó, thì số cách bằng lượng kết quả trước đó

    Có một lượng b[i - 1] dãy con biến đổi trước đó, mỗi dãy đều có phần tử cuối khác a[i] nên nối được với a[i]

    Còn một trường hợp bạn nên cẩn thận là bản thân a[i] cũng là một dãy con biến đổi

    • Nhận xét: Nếu phần tử hiện tại đã từng xuất hiện và bằng phần tử đứng trước, thì số cách bằng lượng kết quả trước đó trừ đi lượng kết quả đã được tính ở vị trí trước đó

    Trong b[i - 1] dãy con biến đổi trước đó, có b[M[a[i]] - 1] dãy con biến đổi nối với a[i] tại vị trí M[a[i]] trước đó

    Vậy phần còn lại là b[i - 1] - b[M[a[i]] - 1] dãy có phần tử cuối khác a[i] và có thể nối với a[i] để tạo thành dãy con biến đổi

    Reference AC code | O(n) time | O(n) auxiliary space | Online Solving, STL, DP_count

    C++
    /// Input
int n;
cin >> n;

/// Input array
vector<int> a(n + 1);
for(int i = 1; i <= n; ++i)
    cin >> a[i];

vector<int> b(n + 1);            /// Mang ket qua
unordered_map<int, int> M;       /// M[x] la vi tri cuoi xuat hien x
int cal = 1;                     /// Bien tinh toan
b[0] = 0; b[1] = 1; M[a[1]] = 1; /// Base cases
for(int i = 2; i <= n; ++i)
{
    if (a[i] != a[i - 1])
    {
        if (M[a[i]] != 0) /// Neu ton tai phan tu truoc do
            cal = (b[i - 1] - b[M[a[i]] - 1] + MOD) % MOD;
        else
            cal = (b[i - 1] + 1) % MOD;
    }

    b[i] = (b[i - 1] + cal) % MOD; /// Cong them ket qua
    M[a[i]] = i;                   /// Luu lai vi tri cuoi cua ai
}

/// Xuat ket qua
cout << b[n];