Editorial for Bedao Grand Contest 12 - FENCE


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

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;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.