제출 #942051

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

tents

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

template<int MD> struct mi {
   int v;
   explicit operator int() const { return v; }
   mi(long long _v = 0) {
       v = (-MD <= _v && _v < MD) ? _v : _v % MD;
       if (v < 0) v += MD;
   }
 
   mi &operator+=(const mi &o) { if ((v += o.v) >= MD) v -= MD; return *this; }
   mi &operator-=(const mi &o) { if ((v -= o.v) < 0) v += MD; return *this; }
   mi &operator*=(const mi &o) { v = 1LL * v * o.v % MD; return *this; }
   mi &operator/=(const mi &o) { return (*this) *= inv(o); }
 
   friend mi operator+(mi a, const mi &b) { return a += b; }
   friend mi operator-(mi a, const mi &b) { return a -= b; }
   friend mi operator*(mi a, const mi &b) { return a *= b; }
   friend mi operator/(mi a, const mi &b) { return a /= b; }
 
   friend mi inv(const mi &m) { return binpow(m, MD - 2); }
   friend mi binpow(mi b, long long e) {
       mi ret = 1;
       for (; e; e >>= 1, b *= b) if (e & 1) ret *= b;
       return ret;
   }
 
   friend bool operator==(const mi &a, const mi &b) { return a.v == b.v; }
   friend bool operator!=(const mi &a, const mi &b) { return !(a == b); }
   friend bool operator<(const mi &a, const mi &b) { return a.v < b.v; }
 
   friend istream &operator>>(istream &i, mi &m) { long long x; i >> x; m.v = x; return i; }
   friend ostream &operator<<(ostream &o, const mi &m) { o << m.v; return o; }
};

const int N = 3007, mod = 1e9 + 7;
using Mint = mi<mod>;
int n, m;
Mint fac[N], ifac[N];
Mint dp[N][N];

Mint nck(int n, int k) {
    return fac[n] * ifac[n - k] * ifac[k];
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    fac[0] = 1;
    for (int i = 1; i < N; i++)
        fac[i] = fac[i - 1] * i;
    
    ifac[N - 1] = binpow(fac[N - 1], mod - 2);
    for (int i = N - 2; ~i; i--)
        ifac[i] = ifac[i + 1] * (i + 1);

    cin >> n >> m;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 1;
            else
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * j * 4;
        }
    }

    Mint ans = 0;
    for (int i = 0; i <= min(n / 2, m); i++) {
        Mint w = nck(m, i) * nck(n, i * 2) * fac[i * 2] / binpow((Mint) 2, i);

        int nn = n - i * 2, nm = m - i;
        for (int j = 0; j <= min(nm / 2, nn); j++) {
            Mint cur = w * nck(nn, j) * nck(nm, j * 2) * fac[j * 2] / binpow((Mint) 2, j);

            ans += cur * dp[nn - j][nm - j * 2];
        }
    }

    cout << ans - 1 << '\n';

    return 0;
}

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