Submission #1167499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167499		ali2241	Tents (JOI18_tents)	C++20	0 / 100	4 ms	4168 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;
    if (n > m) {
        swap(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 dp1[m + 1][m + 1];
    memset(dp1, 0, sizeof dp1);
    for (int i = 0; i <= m; ++i) {
        dp1[i][0] = 1;
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (2 * j <= i) {
                dp1[i][j] = (comb(i, 2) * dp1[i - 2][j - 1]) % 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) * dp1[m][i]) % M;
        // 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) * dp1[n1][j]);
            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: 0 / 48
• Subtask 2: 0 / 52