Submission #434952

#	Time	Username	Problem	Language	Result	Execution time	Memory
434952		Lam_lai_cuoc_doi	Boat (APIO16_boat)	C++17	58 / 100	2029 ms	8336 KiB

boat

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

constexpr bool typetest = 0;
constexpr int N = 5e2 + 2;
constexpr ll mod = 1e9 + 7;

/* https://codeforces.com/blog/entry/57324?#comment-409800 */

int n;

/// dp[i][j]: choose i first elements in j first blocks
ll dp[N][N * 2], d[N * 2][N], inv[N];

pair<int, int> s[N];
vector<int> block;

void Read()
{
    cin >> n;

    block.reserve(n * 2);

    for (int i = 1; i <= n; ++i)
    {
        cin >> s[i].first >> s[i].second;
        block.emplace_back(s[i].first - 1);
        block.emplace_back(s[i].second);
    }

    sort(block.begin(), block.end());
    block.resize(unique(block.begin(), block.end()) - block.begin());
}

ll Pow(ll a, ll b)
{
    ll ans(1);

    for (; b > 0; b >>= 1)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
    }

    return ans;
}

void Solve()
{
    inv[0] = 1;
    for (int i = 1; i <= n; ++i)
        inv[i] = inv[i - 1] * i % mod;

    ll tmp = Pow(inv[n], mod - 2);

    for (int i = n; i; --i)
    {
        inv[i] = tmp * inv[i - 1] % mod;
        (tmp *= i) %= mod;
    }

    /// Pre-calculate d[], I'll define d[] below

    for (int i = 1; i < (int)block.size(); ++i)
    {
        d[i][0] = 1;
        for (int j = 1; j <= n; ++j)
        {
            ll c1(1), c2(1);
            for (int t = 0; t < j && t + 1 <= block[i] - block[i - 1]; ++t)
            {
                (c2 *= inv[t + 1] * (block[i] - block[i - 1] - (t + 1) + 1) % mod) %= mod;

                (d[i][j] += c1 * c2) %= mod;

                (c1 *= inv[t + 1] * (j - 1 - (t + 1) + 1) % mod) %= mod;
            }
        }
    }

    for (int i = 0; i < (int)block.size(); ++i)
        dp[0][i] = 1;

    for (int i = 1; i <= n; ++i)
    {
        dp[i][0] = 1;
        for (int j = 1; j < (int)block.size(); ++j)
        {
            /// no element in j block
            dp[i][j] = dp[i][j - 1];

            /// there're some elements in j block
            for (int t = i, cnt(0); t; --t)
                if (s[t].first <= block[j - 1] + 1 && s[t].second >= block[j])
                {
                    ++cnt;
                    (dp[i][j] += dp[t - 1][j - 1] * d[j][cnt]) %= mod;
                    /// d[j][i] : number of ways to make array that have less or equal i element only from block j
                    /// to prevent overlap counting, we need to change sthg about definition
                }
        }
    }

    cout << dp[n][block.size() - 1] - 1;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 42