Submission #1345728

#TimeUsernameProblemLanguageResultExecution timeMemory
1345728anteknneTents (JOI18_tents)C++20
100 / 100
114 ms142516 KiB
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

const int MAXW = 3000 + 17;
const ll MOD = 1000 * 1000 * 1000 + 7;
ll dp[MAXW][MAXW];
ll newt[MAXW][MAXW];

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int w, h;
    cin >> w >> h;

    newt[0][0] = 1;
    for (int i = 1; i < MAXW; i ++) {
        newt[i][0] = 1;
        for (int j = 1; j < MAXW; j ++) {
            newt[i][j] = newt[i - 1][j - 1] + newt[i - 1][j];
            newt[i][j] %= MOD;
        }
    }

    ll wyn = 0;
    dp[0][0] = 1;
    for (int i = 1; i <= h; i ++) {
        for (int j = 0; j <= w; j ++) {
            if (j == 0) {
                dp[i][j] = dp[i - 1][j];
                continue;
            }
            if (j == 1) {
                dp[i][j] = dp[i - 1][j - 1] * ll(w - (j - 1)) * 4LL;
                dp[i][j] %= MOD;
                dp[i][j] += dp[i - 1][j];
                dp[i][j] %= MOD;
                continue;
            }
            dp[i][j] = dp[i - 1][j - 1] * ll(w - (j - 1)) * 4LL;
            dp[i][j] %= MOD;
            dp[i][j] += dp[i - 1][j];
            dp[i][j] %= MOD;
            ll x = (w - (j - 2));
            dp[i][j] += dp[i - 1][j - 2] * x * (x - 1LL)/ 2LL;
            dp[i][j] %= MOD;
        }
    }

    for (int k = 0; k <= min(w, h/2); k ++) {
        int h2 = h - 2 * k;
        int w2 = w - k;

        ll ile = 1;
        for (ll i = h; i > h2; i -= 2) {
            ile *= i * (i - 1LL)/ 2LL;
            ile %= MOD;
        }

        for (int i = 0; i <= w2; i ++) {
            ll x = dp[h2][i];
            x *= newt[w - i][k];
            x %= MOD;
            x *= ile;
            x %= MOD;
            wyn += x;
        }
    }

    wyn += (MOD - 1LL);
    wyn %= MOD;


    cout << wyn << "\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...