Submission #701410

#	Time	Username	Problem	Language	Result	Execution time	Memory
701410		fatemetmhr	Tents (JOI18_tents)	C++17	100 / 100	227 ms	91952 KiB

tents

// ~ Be Name Khoda ~

#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  3e3   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;

int tak[maxn5][maxn5], dbgr[maxn5][maxn5];
int ent[maxn5][maxn5];

inline void fix(int &a){
    if(a < 0)
        a += mod;
    if(a >= mod)
        a -= mod;
}

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

    int n, m; cin >> n >> m;
    for(int i = 0; i <= n; i++) for(int j = 0; j <= m; j++){
        if(min(i, j) == 0){
            tak[i][j] = 1;
            continue;
        }
        fix(tak[i][j] = tak[i - 1][j] + tak[i - 1][j - 1] * 4LL * j % mod);
    }

    for(int i = 0; i <= max(n, m); i++){
        dbgr[i][0] = 1;
        for(int j = 1; j * 2 <= i; j++)
            fix(dbgr[i][j] = dbgr[i - 1][j] + (dbgr[i - 2][j - 1] * (i - 1LL) * j % mod));
    }

    ent[0][0] = 1;
    for(int i = 1; i < maxn5; i++){
        ent[i][0] = 1;
        for(int j = 1; j < maxn5; j++)
            fix(ent[i][j] = ent[i - 1][j] + ent[i - 1][j - 1]);
    }

    int ans = 0;
    for(int i = 0; i <= n; i++) for(int j = 0; j <= m; j++) if(n >= i + 2 * j && m >= j + 2 * i){
        ll cur = ll(ent[n][i]) * ent[m][j] % mod;
        cur = cur * dbgr[m - j][i] % mod;
        //cout << i << ' ' << j << ' ' << cur << endl;
        cur = cur * dbgr[n - i][j] % mod;
        //cout << i << ' ' << j << ' ' << cur << endl;
        cur = cur * tak[n - i - 2 * j][m - j - 2 * i] % mod;
        fix(ans += cur);
        //cout << i << ' ' << j << ' ' << cur << ' ' << tak[n - i - 2 * j][m - j - 2 * i] << endl;
    }
    fix(--ans);
    cout << ans << endl;
}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52