oj.uz

Submission #942051

# Submission time Handle Problem Language Result Execution time Memory
942051 2024-03-10T05:37:56 Z juliany2 Tents (JOI18_tents) C++17
100 / 100
 344 ms 35852 KB 
#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.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35676 KB Output is correct
2 Correct 6 ms 35676 KB Output is correct
3 Correct 5 ms 35744 KB Output is correct
4 Correct 7 ms 35732 KB Output is correct
5 Correct 5 ms 35676 KB Output is correct
6 Correct 5 ms 35676 KB Output is correct
7 Correct 6 ms 35756 KB Output is correct
8 Correct 5 ms 35768 KB Output is correct
9 Correct 5 ms 35676 KB Output is correct
10 Correct 7 ms 35676 KB Output is correct
11 Correct 6 ms 35672 KB Output is correct
12 Correct 8 ms 35672 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35676 KB Output is correct
2 Correct 6 ms 35676 KB Output is correct
3 Correct 5 ms 35744 KB Output is correct
4 Correct 7 ms 35732 KB Output is correct
5 Correct 5 ms 35676 KB Output is correct
6 Correct 5 ms 35676 KB Output is correct
7 Correct 6 ms 35756 KB Output is correct
8 Correct 5 ms 35768 KB Output is correct
9 Correct 5 ms 35676 KB Output is correct
10 Correct 7 ms 35676 KB Output is correct
11 Correct 6 ms 35672 KB Output is correct
12 Correct 8 ms 35672 KB Output is correct
13 Correct 6 ms 35672 KB Output is correct
14 Correct 5 ms 35744 KB Output is correct
15 Correct 198 ms 35676 KB Output is correct
16 Correct 9 ms 35676 KB Output is correct
17 Correct 32 ms 35676 KB Output is correct
18 Correct 59 ms 35848 KB Output is correct
19 Correct 236 ms 35676 KB Output is correct
20 Correct 195 ms 35852 KB Output is correct
21 Correct 127 ms 35676 KB Output is correct
22 Correct 119 ms 35676 KB Output is correct
23 Correct 30 ms 35676 KB Output is correct
24 Correct 344 ms 35844 KB Output is correct
25 Correct 252 ms 35844 KB Output is correct
26 Correct 294 ms 35852 KB Output is correct
27 Correct 330 ms 35844 KB Output is correct