Submission #127531

#	Time	Username	Problem	Language	Result	Execution time	Memory
127531		BThero	Tents (JOI18_tents)	C++17	100 / 100	174 ms	35704 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][MAXN];

int ways[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() {
    for (int i = 1; i < MAXN; ++i) {
        if (i & 1) {
            ways[i] = mulMod((i - 1) / 2, i);
        }
        else {
            ways[i] = mulMod(i / 2, i - 1);
        }
    }
}

void solve() {
    scanf("%d %d", &n, &m);
    
    dp[0][m] = 1;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= m; ++j) {
            dp[i + 1][j] = addMod(dp[i + 1][j], dp[i][j]);

            if (j > 0) {
                dp[i + 2][j - 1] = addMod(dp[i + 2][j - 1], mulMod(dp[i][j], mulMod(j, n - i - 1)));
                dp[i + 1][j - 1] = addMod(dp[i + 1][j - 1], mulMod(4, mulMod(dp[i][j], j)));
            }

            if (j > 1) {
                dp[i + 1][j - 2] = addMod(dp[i + 1][j - 2], mulMod(dp[i][j], ways[j]));
            }
        }
    }

    int ans = MOD - 1;

    for (int i = 0; i <= m; ++i) {
        ans = addMod(ans, dp[n][i]);
    }

    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:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~

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