INCSEQ VN

Xem dạng PDF
Gửi bài giải
Điểm: 0,34 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
Neal Wu -SPOJ
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho ~1~ dãy số gồm ~N~(~0~ ~<~ ~N~ ~\leq~ ~10000~) số tự nhiên ~S_1~, ~S_2~, ..., ~S_n~ (~0~ ~\leq~ ~S_i~ ~\leq~ ~10^5~), Hãy đếm số lượng dãy con tăng có độ dài ~K~(~0~ ~<~ ~k~ ~\leq~ ~50~).

Input

Dòng đầu tiên là hai số tự nhiên ~N~ và ~K~.

~N~ dòng tiếp sau mô tả dãy ~S~.

Output

Số lượng dãy con thỏa mãn theo Module ~5000000~.

Sample Input

4 3
1
2
2
10

Sample Output

2

Note

Giải thích: Có ~2~ dãy con thỏa mãn (~S_1~, ~S_2~, ~S_4~) và (~S_1~, ~S_3~, ~S_4~): (~1~, ~2~, ~10~).

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 1
    vominhmanh10  đã bình luận lúc 21, Tháng 4, 2026, 15:50 ← sửa 3

    Làm rõ hướng giải dùng bit
    Đầu tiên, ta có dp[i][j] = số lượng dãy con tăng dài i kết thúc tại j
    dp[i][j] += dp[i - 1][t] với t < j và a[t] < a[j]
    Lúc này ta bỏ for t bằng việc cộng các dp[i - 1][t] thỏa mãn a[t] < a[j] bằng bit, lưu ý ta cập nhật dp[i - 1][t] tuần tự theo dp[i][j] tức không cập nhật t > j để tránh đếm bên phải 

    #include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define all(a) a.begin(), a.end()
#define IO ios::sync_with_stdio(0); cin.tie(0)
#define filled(a, b) memset(a, b, sizeof(a))
#define mini(a, b) (a) = (min((a), (b)))
#define maxi(a, b) (a) = (max((a), (b)))
const ll maxn = 1e6 + 5, inf = 1e18, mod = 5e6;
const ull base = 314;
int n, k, bit[10001], pos[10001];
void add(int i, int x) {
    for (; i <= n; i += i & -i) bit[i] = (bit[i] + x) % mod;
}
int query(int i) {
    int res = 0;
    for (; i > 0; i -= i & -i) res = (res + bit[i]) % mod;
    return res;
}
int main() {
    IO; cin >> n >> k; vector<int> a(n + 1), b(n), dp(n + 1), ndp(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        b[i - 1] = a[i];
    }
    sort(all(b));
    for (int i = 1; i <= n; ++i) {
        pos[i] = lower_bound(all(b), a[i]) - b.begin() + 1;
        dp[i] = 1;
    }
    for (int i = 2; i <= k; ++i) {
        for (int j = 1; j <= n; ++j) {
            ndp[j] = query(pos[j] - 1);
            add(pos[j], dp[j]);
        }
        filled(bit, 0);
        swap(dp, ndp);
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = (ans + dp[i]) % mod;
    cout << ans;
}

  • 8
    pppssslc  đã bình luận lúc 27, Tháng 7, 2025, 10:22

    Bài tương tự: Dãy nghịch thế độ dài K


  • 11
    chitamha  đã bình luận lúc 4, Tháng 3, 2024, 15:56 ← sửa 3

    Chúc mọi người có một ngày tốt lành


  • 34
    kh0i  đã bình luận lúc 16, Tháng 5, 2022, 16:20

    Bài tương tự: Codeforces 597C - Subsequences