제출 #1307044

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307044		chithanhnguyen	Tents (JOI18_tents)	C++20	100 / 100	1071 ms	71116 KiB

tents

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

#define int long long
#define ull unsigned long long
#define ld long double
#define pii pair<int, int>
#define fi first
#define se second
#define __builtin_popcount __builtin_popcountll
#define all(x) (x).begin(), (x).end()
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(x) ((1ll << (x)))

#define debug(a, l, r) for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n';

namespace math {
    template<int _MOD>
    struct Modint{
        static const int mod = _MOD;
        int v;

        Modint() : v(0) {}
        Modint(int _v) : v(_v) {}
        Modint& operator += (const Modint &other) {
            v += other.v;
            if (v >= mod) v -= mod;
            return *this;
        }

        Modint& operator -= (const Modint &other) {
            v -= other.v;
            if (v < 0) v += mod;
            return *this;
        }

        Modint& operator *= (const Modint &other) {
            v = 1ll * v * other.v % mod;
            return *this;
        }

        Modint pow(int k) const {
            Modint res(1), base = *this;
            while (k) {
                if (k & 1) res *= base;
                base *= base;
                k >>= 1;
            }

            return res;
        }

        Modint inv() const {return pow(mod - 2);}

        Modint& operator /= (const Modint &other) {
            *this *= other.inv();
            return *this;
        }

        friend Modint operator + (Modint a, const Modint &b) {return a += b;}
        friend Modint operator - (Modint a, const Modint &b) {return a -= b;}
        friend Modint operator * (Modint a, const Modint &b) {return a *= b;}
        friend Modint operator / (Modint a, const Modint &b) {return a /= b;}

        Modint operator - () const {return Modint(0) - *this;}

        friend ostream& operator << (ostream &stream, const Modint &other) {
            return stream << other.v;
        }
    };

    template <int _MOD>
    struct Combinatorics{
        int n;
        vector<Modint<_MOD>> fact, ifact;

        Combinatorics(int _n) : n(_n) {
            fact.resize(n + 1, 0);
            ifact.resize(n + 1, 0);

            fact[0] = 1;
            for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
            ifact[n] = fact[n].inv();
            for (int i = n - 1; i >= 0; --i) ifact[i] = ifact[i + 1] * (i + 1);
        }

        Modint<_MOD> C(int n, int k) {
            if (k < 0 || k > n) return 0;
            return fact[n] * ifact[k] * ifact[n - k];
        }
    };
}

using namespace math;

const int MOD = 1e9 + 7;
#define mint Modint<MOD>
const int MAXN = 3005;
int n, m;
mint dp[MAXN][MAXN];

signed main() {
    #ifdef NCTHANH
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (i * j == 0) {
                dp[i][j] = mint(1);
                continue;
            }

            // Không lắp thêm lều nào
            dp[i][j] += dp[i - 1][j];
            // Lắp thêm một lều
            dp[i][j] += dp[i - 1][j - 1] * mint(4) * mint(j);

            // Lắp thêm lên, xuống
            if (i - 2 >= 0) dp[i][j] += dp[i - 2][j - 1] * mint(j) * mint(i - 1);

            // Lắp thêm trái, phải
            if (j - 2 >= 0) dp[i][j] += dp[i - 1][j - 2] * mint(j) * mint(j - 1) / 2;
        }
    }

    cout << dp[n][m] - mint(1);

    return 0;
}

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