Submission #127344

#	Time	Username	Problem	Language	Result	Execution time	Memory
127344		BThero	Tents (JOI18_tents)	C++17	48 / 100	277 ms	1560 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 = 500 + 5;

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

void solve() {
    scanf("%d %d", &n, &m);

    dp[0][0][m] = 1;
    dp[0][1][m - 1] = m;

    if (m > 1) {
        dp[0][0][m - 2] = ways[m];
    }

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

                if (a > 0) {
                    dp[1][a - 1][b] = addMod(dp[1][a - 1][b], mulMod(a, dp[0][a][b]));
                }

                if (b > 0) {
                    dp[1][a + 1][b - 1] = addMod(dp[1][a + 1][b - 1], mulMod(b, dp[0][a][b]));
                }

                if (b > 1) {
                    dp[1][a][b - 2] = addMod(dp[1][a][b - 2], mulMod(dp[0][a][b], ways[b]));
                }
            }
        }

        for (int a = 0; a <= m; ++a) {
            for (int b = 0; b <= m; ++b) {
                dp[0][a][b] = dp[1][a][b];
                dp[1][a][b] = 0;
            }
        }
    }

    int ans = MOD - 1;

    for (int a = 0, cur = 1; a <= m; ++a) {
        for (int b = 0; b <= m; ++b) {
            ans = addMod(ans, mulMod(dp[0][a][b], cur));
        }

        cur = mulMod(cur, 4);
    }

    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: 0 / 52