Submission #127428

#	Time	Username	Problem	Language	Result	Execution time	Memory
127428		BThero	Tents (JOI18_tents)	C++17	0 / 100	184 ms	112480 KiB

tents

// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;   
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MOD = (int)1e9 + 7;
const int MAXN = (int)3e3 + 5;

int dp[MAXN];

int C[MAXN][MAXN];

int R[MAXN][MAXN];

int fact[MAXN];

int n, m;

int addMod(int a, int b, int m = MOD) {
    a += b;

    if (m <= a) {
        a -= m;
    }

    return a;
}

int mulMod(int a, int b, int m = MOD) {
    return a * 1ll * b % m;
}

int binPow(int a, int b, int m = MOD) {
    int ret = 1;

    while (b > 0) {
        if (b & 1) {
            ret = mulMod(ret, a, m);
        }

        a = mulMod(a, a, m);
        b >>= 1;
    }

    return ret;
}

void pre() {
    fact[0] = 1;

    for (int i = 1; i < MAXN; ++i) {
        fact[i] = mulMod(fact[i - 1], i);
    }

    C[0][0] = 1;

    for (int i = 1; i < MAXN; ++i) {
        C[i][0] = C[i - 1][0];

        for (int j = 1; j <= i; ++j) {
            C[i][j] = addMod(C[i - 1][j - 1], C[i - 1][j]);
        }
    }

    for (int i = 0; i < MAXN; ++i) {
        for (int j = 0; j <= i; ++j) {
            R[i][j] = mulMod(C[i][j], fact[j]);
        }
    }

    dp[0] = 1;

    for (int i = 1; i < MAXN; ++i) {
        dp[i] = mulMod(dp[i - 1], C[i * 2][2]);
    }
}

void solve() {
    scanf("%d %d", &n, &m);
    int ans = MOD - 1;

    for (int a = 0; a <= m; ++a) {
        for (int b = 0; b <= m; ++b) {
            for (int c = 0; c <= m; ++c) {
                if (a + b + c * 2 <= m && a + 2 * b + c <= n) {
                    int cur = binPow(4, a);

                    cur = mulMod(cur, C[n][2 * b]);
                    cur = mulMod(cur, dp[b]);
                    cur = mulMod(cur, C[n - 2 * b][c]);
                    cur = mulMod(cur, C[n - c - 2 * b][a]);
                    cur = mulMod(cur, C[m][2 * c]);
                    cur = mulMod(cur, dp[c]);
                    cur = mulMod(cur, C[m - 2 * c][b]);
                    cur = mulMod(cur, C[m - 2 * c - b][a]);
                    cur = mulMod(cur, fact[a]);

                    ans = addMod(ans, cur);
                }
            }
        }
    }

    printf("%d\n", ans);
}

int main() {
    int tt = 1;

    pre();

    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

tents.cpp: In function 'void solve()':
tents.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
tents.cpp: In function 'void pre()':
tents.cpp:93:23: warning: iteration 1502 invokes undefined behavior [-Waggressive-loop-optimizations]
         dp[i] = mulMod(dp[i - 1], C[i * 2][2]);
                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tents.cpp:92:23: note: within this loop
     for (int i = 1; i < MAXN; ++i) {
                     ~~^~~~~~

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