Dựa vào điều kiện ~2\cdot h_i > n~, có thể nhận giá trị bất kì, ta chia dãy độ dài ~m~ ra thành các phần, mỗi phần bắt đầu là một giá trị bất kì và kết thúc khi thỏa mãn điều kiện thứ 2.

Dựa vào điều kiện thứ 3, ta nhận thấy mỗi phần có độ dài tối đa là ~log_2(n)~.

Định nghĩa ~f[i][len]~ là số phần bắt đầu bằng thanh gỗ độ dài ~i~, và phần này có độ dài ~len~: ~f[i][len] = \sum_{j=i\times 2}^n f[j][len-1]~.

Ta có thể tính nhanh ~f[i][len]~ trong ~O(1)~ bằng tổng tiền tố.

Gọi ~cnt[len]~ là số phần có độ dài len, ta có: ~cnt[len] = \sum^n_{i=1} f[i][len]~.

Gọi ~dp[i]~ là số hàng rào đẹp độ dài ~i~, ta có: ~dp[i] = \sum^{min(log_2(n),i)}_{j=1} cnt[j]\times dp[i-j]~.

Code mẫu

//TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int , int>
#define fi first
#define se second
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x)  (1LL<<(x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"  

using namespace std;
const int N = (int)1e5+228;
const int M = (int)5e5+228;
const int mod = (int)1e9+7;

void add(int &x, const int &y)
{
    x += y;
    if(x >= mod) x -= mod;
}
void sub(int &x, const int &y)
{
    x -= y;
    if(x < 0) x += mod;
}
#define PRODUCT(x,y) (1LL*(x)*(y)%mod)

int power(int x, int y)
{
    int res = 1;
    while(y > 0)
    {
        if(1&y) res = PRODUCT(res, x);
        x = PRODUCT(x, x);
        y /= 2;
    }
    return res;
}

int n, m;
int dp[M], f[N][20], sum[20];

void solve()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n >> m;
        memset(dp, 0, sizeof(dp));
        memset(f, 0, sizeof(f));
        memset(sum, 0, sizeof(sum));

        for(int i=n; i>=1; --i)
        {
            for(int len = 1; len <= 18; ++len)
            {
                if(2 * i > n)
                    f[i][len] = (len == 1);
                else 
                    f[i][len] = f[2 * i][len - 1];
                add(sum[len], f[i][len]);
                add(f[i][len], f[i+1][len]);
            }
        }

        dp[0] = 1;
        for(int i=1; i<=m; ++i)
        {
            for(int j=1; j<=min(18, i); ++j)
                add(dp[i], PRODUCT(dp[i-j], sum[j]));
        }
        cout << dp[m] << '\n';
    }
}    

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    //cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}