Submission #1034081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034081		anHiep	Tents (JOI18_tents)	C++14	48 / 100	2090 ms	313700 KiB

tents

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define ll long long
#define ii pair<int, int>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<ii>
#define cd complex<double>
#define ld long double
#define all(x) (x).begin(), (x).end()
#define iii tuple<int, int, int>
const ll mod = 1e9 + 7;
const ll INF = 1e18L + 5;
const double PI = acos(-1);
const int block = 320;
const int N = 1e7;
int tc, tt = 1;

ll h, w;
ll fac[N + 5], inv[N + 5];
ll g[N + 5];
ll f[N + 5];

ll powmod(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return ans;
}

void prep() {
    fac[0] = 1;
    for(int i=1; i<=N; i++) fac[i] = fac[i - 1] * i % mod;
    inv[N] = powmod(fac[N], mod - 2);
    for(ll i=N-1; i>=0; i--)
        inv[i] = inv[i + 1] * (i + 1) % mod;
}

ll C(ll n, ll k) {
    ll ans = fac[n];
    ans = ans * inv[k] % mod;
    ans = ans * inv[n - k] % mod;
    return ans;
}

void solve() {
    prep();
    f[0] = 1;
    for(int i=1; i<=N; i++) f[i] = f[i - 1] * 4 % mod;
    g[0] = 1;
    for(int i=2; i<=N; i+=2) g[i] = g[i - 2] * C(i, 2) % mod; 
    cin>>h>>w;
    ll ans = 0;
    for(int i=0; i<=min(h, w/2); i++) {
        ll cal = C(h, i) * C(w, i * 2) % mod;
        cal = cal * g[i * 2] % mod;
        for(int j=0; j<=min(w - 2 * i, (h - i)/2); j++) {
            ll cal2 = C(w - 2 * i, j) * C(h - i, j * 2) % mod;
            cal2 = cal2 * g[j * 2] % mod;
            ll cnt = min((w - 2 * i - j), (h - i - j * 2));
            ll fical = cal * cal2 % mod;
            ll sum = 0;
            for(int k=0; k<=cnt; k++) {
                if(i == 0 && j == 0 && k == 0) continue;
                ll v = f[k];
                v = v * C(w - 2*i - j, k) % mod;
                v = v * C(h - i - j * 2, k) % mod;
                v = v * fac[k] % mod;
                sum = (sum + v) % mod;
            }
            fical = fical * sum % mod;
            ans = (ans + fical) % mod;
        }
    }
    cout<<ans;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    for(tc=1; tc<=tt; tc++) solve();
    cerr<<"\nTime elapsed: "<<1000.0*clock()/CLOCKS_PER_SEC<<" ms.\n";
    return 0;
}

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