제출 #1326305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326305		husseinjuanda	Tents (JOI18_tents)	C++20	100 / 100	888 ms	73388 KiB

tents

#include <bits/stdc++.h>
using namespace std;
#define int long long 

const int mod = 1e9+7;
vector<int> fact(1e5+1);
vector<int> inv(1e5+1);

int fpow(int n, int k){
    //n^k
    if(k == 0) return 1;
    int r = 1;
    if(k%2 == 1){
        r = n;
    }
    int f = fpow(n, k/2);
    return f*f%mod*r%mod;
}

int C(int n, int k){
    return fact[n] * inv[k]%mod * inv[n-k]%mod;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int h, w; cin >> h >> w;
    fact[0] = 1;
    inv[0] = 1;
    int c = 1;
    for(int i = 1; i <= 1e5; i++){
        c *= i;
        c%=mod;
        fact[i] = c;
        inv[i] = fpow(fact[i], mod-2);
    }
    vector<int> pref(1e5+1);
    pref[1] = 1;
    pref[0] = 1;
    for(int i = 2; i <= 1e5; i++){
        pref[i] = ((i * (i-1))/2%mod * pref[i-2])%mod;
    }
    vector<vector<int>> precomp(3001, vector<int>(3001));
    for (int i = 0; i <= 3000; i++) precomp[i][0] = 1;
    for (int j = 0; j <= 3000; j++) precomp[0][j] = 1;
    for(int i = 1; i <= 3000; i++){
        for(int y = 1; y <= 3000; y++){
            precomp[i][y] = precomp[i-1][y] + precomp[i-1][y-1] * (4*y)%mod;
            precomp[i][y]%=mod;
        }
    }
    int ans = 0;
    for(int i = 0; i <= h; i++){
        for(int y = 0; y <= w; y++){
            //h vertical
            //w hori
            if(w - i - y*2 < 0 || h - i*2 - y < 0) continue;
            int ns = C(w, i) * (pref[h] * fpow(pref[h - i*2], mod-2)%mod)%mod;
            if(i == 0){
                ns = 1;
            }
            int sisa = w-i;
            int colsisa = h-i*2;
            if(y > 0){
                ns = ns * C(colsisa, y)%mod * pref[sisa]%mod * fpow(pref[sisa - y*2], mod-2)%mod;
            }
            sisa -= y*2;
            colsisa -= y;
            if(min(sisa, colsisa) > 0){
                ns = ns*(precomp[max(sisa, colsisa)][min(sisa, colsisa)]+mod)%mod;
            }
            ans += ns;
            ans%=mod;
        }
    }
    cout << ans-1 << "\n";
    return 0;
}

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