Submission #414912

#	Time	Username	Problem	Language	Result	Execution time	Memory
414912		Pro_ktmr	Tents (JOI18_tents)	C++17	100 / 100	444 ms	88500 KiB

tents

#include"bits/stdc++.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

template<typename T>
T power(T x, long long n, const T &m){
    if(n == 0) return 1;
    if(n == 1) return x;
    T tmp = power(x, n/2, m);
    if(n%2 == 0) return tmp * tmp % m;
    else return tmp * tmp % m * x % m;
}

template<typename T>
T inverse(T x, const T &m){
    return power(x, m-2, m);
}

struct Combination{

    int N;
    long long M;
    vector<long long> f, i;
public:
    void init(int n, long long m){
        N = n; M = m;
        f.resize(N+1); f[0] = 1;
        i.resize(N+1); i[0] = 1;
        for(long long j=1; j<=N; j++){
            f[j] = f[j-1]*j%M;
            i[j] = inverse(f[j], M);
        }
    }
    long long fact(int n){
        return f[n];
    }
    long long C(int n, int r){
        return f[n] * i[r] % M * i[n-r] % M;
    }
    long long P(int n, int r){
        return f[n] * i[n-r] % M;
    }
};

ll H, W;
Combination comb;

ll memo[3001][3001] ={};
ll calc(ll w, ll n){
    if(n == 0) return 1;
    if(memo[w][n] != 0) return memo[w][n];
    return memo[w][n] = comb.C(w, 2) * calc(w-2, n-1) % MOD;
}

ll dp[3001][3001] ={};
ll solve(ll w, ll h){
    if(w == 0 || h == 0) return 1;
    if(dp[w][h] != 0) return dp[w][h];
    return dp[w][h] = (solve(w-1, h) + solve(w-1,h-1)*h*4) % MOD;
}

ll ans = 0;

signed main(){
    cin >> H >> W;
    comb.init(3000, MOD);
    for(ll ew=0; ew*2<=W && ew<=H; ew++){
        for(ll ns=0; ew*2+ns<=W && ew+ns*2<=H; ns++){
            ll tmp = comb.C(H, ew);
            tmp *= calc(H-ew, ns);
            tmp %= MOD;
            tmp *= comb.i[ns];
            tmp %= MOD;
            tmp *= comb.P(W, ns);
            tmp %= MOD;
            tmp *= calc(W-ns, ew);
            tmp %= MOD;
            tmp *= solve(W-ew*2-ns, H-ew-ns*2);
            tmp %= MOD;
            ans += tmp;
            //cout << tmp << endl;
        }
    }
    cout << (ans-1+MOD) % MOD << endl;
}

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