Cũng như bài E1 ở đây ta sẽ dùng tổ hợp để tối ưu 😁

Bây giờ ta sẽ coi một dãy sẽ có con ~minn~ ở đầu và các con đằng sau sẽ phải ~< minn \times x~.

-> Ta sẽ đổi sang bài toán cố định con ~minn~ ở đầu và chọn các số trong đoạn ~[minn,minn*x-1]~ cho ~k-1~ phần tử còn lại

~O~ ~(k)~

Cũng như bài trước ta sẽ for từng con ~minn~, bây giờ ta sẽ gọi ~maxx~ là giá trị lớn nhất thỏa mãn ~< minn \times x~ hay ~maxx = min(minn*x-1,k)~

Bây giờ ta sẽ có công thức chọn ~k-1~ con có giá trị trong đoạn ~[minn,minn*x-1]~ sẽ là ~{maxx-minn+k-1 \choose k-1}~

Chứng minh :

Nguồn : link

Dành cho các bạn nào không hiểu Tiếng Anh thì ta sẽ hiểu như này.

Cho bài toán có 3 loại kẹo C,G,H và phải tạo dãy 6 phần tử với 3 loại giá trị này (thứ tự không quan trọng)

Ví dụ (thứ tự không quan trọng nên ta sẽ sort từ C -> G -> H):

C C C G G H

C G G G G H

C C C C G G

H H H H H H

-> Ta sẽ làm như bài toán chia kẹo Euler và sẽ tạo những thanh chắn giữa các giá trị

C C C | G G | H

C | G G G G | H

C C C C | G G |

| | H H H H H H

-> Bài toán sẽ chuyển sang đếm số cách đặt thanh chắn cho 6 phần tử, ta có số thanh chắn là r-1 và số vị trí đặt thanh chắn là n+r-1

-> Công thức là ~{n+r-1 \choose r-1}~

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 1e9+7;

int fact[200005];
int invmod[200005];
int invfact[200005];

int nCr(int n, int r){
    return ((fact[n] * invfact[r])%mod * invfact[n-r])%mod;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int k,x;
    cin >> k >> x;
    if(x == 1){
        cout << 0;
        return 0;
    }
    if(k == 1){
        cout << 1;
        return 0;
    }

    fact[0] = 1;
    for(int i = 1; i <= 2*k; i++) fact[i] = (fact[i-1]*i)%mod;
    invmod[1] = 1;
    for(int i = 2; i <= 2*k; i++) invmod[i] = mod - (mod/i * invmod[mod%i])%mod;
    invfact[0] = 1;
    for(int i = 1; i <= 2*k; i++) invfact[i] = (invfact[i-1] * invmod[i])%mod;


    int ans = 0;
    for(int minn = 1; minn <= k; minn++){
        int maxx = min(minn*x-1,k);
        ans += nCr(maxx-minn+1+k-1-1,k-1);
        ans %= mod;
    }
    cout << ans;
    return 0;
}

Vì tinh thần là div 3 nên các bạn dùng nCr log k vẫn là thuật chuẩn nhé 😁