제출 #1167490

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167490		ali2241	Tents (JOI18_tents)	C++20	48 / 100	2071 ms	47360 KiB

tents

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define arr2 array<int, 2>
#define arr3 array<int, 3>
#define all(a) a.begin(), a.end()
#define double long double
#define ctz __builtin_ctz
#define clz __builtin_clz
#define popcount __builtin_popcount
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")

using namespace std;
using namespace __gnu_pbds;

//I got tired from div.2s



// template<class T> using rb3 = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using mrb3 = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// bool comp(ar2 a, arr2 b) {
//     return (a[0] - a[1]) < (b[0] - b[1]);
// }

const int N = 2e5 + 10, M = 1e9 + 7;

int bow(int a, int b) {
    if (b == 0) {
        return 1;
    }
    int c = bow(a, b / 2);
    if (b & 1) {
        return (((c * c) % M) * a) % M;
    }
    return (c * c) % M;
}

int rev[N], fact[N];

void pre() {
    fact[0] = 1;
    for (int i = 1; i < N; ++i) {
        fact[i] = (i * fact[i - 1]) % M;
    }
    rev[N - 1] = bow(fact[N - 1], M - 2);
    for (int i = N - 2; i >= 0; --i) {
        rev[i] = ((i + 1) * rev[i + 1]) % M;
    }
}

int comb(int n, int k) {
    int a = fact[n], b = rev[k], c = rev[n - k];
    return (((a * b) % M) * c) % M;
}

void fun() {
    int n, m;
    cin >> n >> m;
    int dp[n + 1][m + 1];
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = 1;
    }
    for (int i = 0; i <= m; ++i) {
        dp[0][i] = 1;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            dp[i][j] = (dp[i - 1][j - 1] * 5) % M;
            if (i > 1) {
                dp[i][j] = (dp[i][j] + dp[i - 2][j - 1] * (i - 1) * 4) % M;
            }
            if (j > 1) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j - 2] * (j - 1) * 4) % M;
            }
            if (i > 1 and j > 1) {
                dp[i][j] = (dp[i][j] + dp[i - 2][j - 2] * (i - 1) * (j - 1) * 16) % M;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= min(n, m / 2); ++i) {
        int n1 = n - i, m1 = m - i * 2;
        int c1 = comb(n, i);
        for (int j = 0; j < i; ++j) {
            c1 = (c1 * comb(m - 2 * j, 2)) % M;
        }
        for (int j = 0; j <= (min(m1, n1 / 2)); ++j) {
            int c2 = comb(m1, j);
            for (int k = 0; k < j; ++k) {
                c2 = (c2 * comb(n1 - 2 * k, 2)) % M;
            }
            ans = (ans + (((c2 * c1) % M) * dp[n1 - 2 * j][m1 - j])) % M;
        }
    }
    cout << ans - 1 << "\n";
}

int32_t main() {
    pre();
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // int tc;
    // cin >> tc;
    // while (tc--)
    fun();
}

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