1. ~O(k^4)~

Mấu chốt của bài toán này là những nhận xét sau :

• Vì vị trí của các phần tử trong dãy không quan trọng nên ta chỉ cần quan tâm đến các giá trị xuất hiện trong dãy
• Một dãy thỏa mãn khi "phần tử lớn nhất" ko chứa được "phần tử bé nhất"

Từ những nhận xét đó ta có thể nhận ra công thức dp như sau :

~dp[i][minn][maxx]~ là số dãy có i phần tử và giá trị nhỏ nhất là ~minn~ và giá trị lớn nhất là ~maxx~ suy ra để thỏa mãn điều kiện đề bài thì ~maxx < minn*x~

Với mỗi cặp ~(minn,maxx)~ thỏa mãn ta sẽ tìm những con ~maxx' \le maxx~ để ~dp[i][minn][maxx] += dp[i-1][minn][maxx']~

Dễ thấy base case sẽ là ~dp[1][minn][minn] = 1~ từ đó ta ra được thuật toán ~O(k^4)~

LƯU Ý : Vì giới hạn 512MB nên ta sẽ phải bỏ long long hoặc tối ưu bộ nhớ bằng cách bỏ đi biến ~i~ ở mảng dp

2. ~O(k^3)~

Đến đây ta sẽ có thuật toán tối ưu cơ bản như sau :

Dễ thấy, các con ~maxx'~ thỏa mãn sẽ chạy liên tiếp trong đoạn ~[minn,maxx]~ từ đó ta có ý tưởng tối ưu bằng prefixsum

Ta sẽ tạo mảng ~pf[i][minn][cur]~ (~minn*x > cur \ge minn~) tức tổng của các ~dp[i][minn][maxx]~ với mọi ~maxx~ trong đoạn ~[minn,cur]~ để bớt đi 1 vòng for ~maxx'~

Từ đây công thức dp sẽ chỉ còn là ~dp[i][minn][maxx] = pf[i][minn][maxx]~ với mọi cặp ~(minn,maxx)~

Code mẫu

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9+7;

int dp[505][505];
int pf[505][505];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int k,x;
    cin >> k >> x;
    if(x == 1){
        cout << 0;
        return 0;
    }

    for(int minn = 1; minn <= k; minn++) dp[minn][minn] = 1;
    for(int minn = 1; minn <= k; minn++) for(int maxx = minn; maxx <= k; maxx++){
        pf[minn][maxx] = pf[minn][maxx-1] + dp[minn][maxx];
        pf[minn][maxx] %= mod;
    }

    for(int i = 2; i <= k; i++){
        for(int minn = 1; minn <= k; minn++){
            for(int cur = minn; cur <= k; cur++) if(cur < minn*x){
                dp[minn][cur] = pf[minn][cur];
            }
        }
        for(int minn = 1; minn <= k; minn++) for(int maxx = minn; maxx <= k; maxx++){
            pf[minn][maxx] = 0;
            pf[minn][maxx] = pf[minn][maxx-1] + dp[minn][maxx];
            pf[minn][maxx] %= mod;
        }
    }

    int ans = 0;
    for(int minn = 1; minn <= k; minn++) for(int maxx = minn; maxx <= k; maxx++){
        ans += dp[minn][maxx];
        ans %= mod;
    }
    cout << ans;
    return 0;
}