제출 #525226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
525226		AA_Surely	Tents (JOI18_tents)	C++17	100 / 100	100 ms	71244 KiB

tents

#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(int i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(int i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;
typedef long long 		LL;

typedef pair<int, int> 	PII;
typedef pair<LL, LL> 	PLL;

typedef vector<int> 	VI;
typedef vector<LL> 		VLL;
typedef vector<PII> 	VPII;
typedef vector<PLL> 	VPLL;

const int MAXN = 3000 + 7;
const int ALPHA = 27;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;

int n, m;
LL fact[MAXN << 1], inv_fact[MAXN << 1];
LL dp[MAXN << 1], f[MAXN][MAXN];

inline LL pw(LL a, LL b) {
    LL res = 1;
    for(; b; b >>= 1, a = a * a % MOD) 
        if (b & 1) res = res * a % MOD;
    return res;
}

inline LL nCr(int nn, int rr) {
    if (nn < rr || rr < 0) return 0;
    return (fact[nn] * inv_fact[rr] % MOD) * inv_fact[nn - rr] % MOD;
}

void precalc() {
    fact[0] = 1;
    FOR(i, 1, (MAXN << 1)) fact[i] = fact[i - 1] * i % MOD;

    inv_fact[(MAXN << 1) - 1] = pw(fact[(MAXN << 1) - 1], MOD - 2);
    R0F(i, (MAXN << 1) - 1) inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
    //cout << pw(8, MOD - 2) << ' ' << inv_fact[8] << endl;
    
    dp[0] = 1;
    for(int i = 2; i < (MAXN << 1); i += 2) 
        dp[i] = nCr(i, 2) * dp[i - 2] % MOD;
    
    F0R(p, MAXN) f[p][0] = f[0][p] = 1;

    FOR(p, 1, MAXN) {
        f[p][0] = 1;
        FOR(q, 1, MAXN) f[p][q] = (f[p - 1][q] + 4ll * q * f[p - 1][q - 1]) % MOD;
    }

    return;
}

int main() {
    IOS;
    
    precalc();
    cin >> n >> m;
    
    LL ans = 0;
    F0R(x, n + 1) F0R(y, m + 1) {
        if (n - 2 * x - y < 0 || m - x - 2 * y < 0) continue;
        ans = (ans + (((((nCr(n, 2 * x) * nCr(m, 2 * y) % MOD) * nCr(m - 2 * y, x) % MOD) * nCr(n - 2 * x, y) % MOD) * f[n - 2 * x - y][m - x - 2 * y] % MOD) * dp[2 * x] % MOD) * dp[2 * y] % MOD);
    }

    cout << (ans - 1 + MOD) % MOD;
}

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