Submission #464830

#	Time	Username	Problem	Language	Result	Execution time	Memory
464830		TheScrasse	Zapina (COCI20_zapina)	C++17	110 / 110	334 ms	1348 KiB

zapina

#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 1000000007
#define maxn 360

ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll fc[maxn], nv[maxn], dp[maxn][maxn];

ll fxp(ll b, ll e) {
    ll r = 1, k = b;
    while (e != 0) {
        if (e % 2) r = (r * k) % mod;
        k = (k * k) % mod; e /= 2;
    }
    return r;
}

ll inv(ll x) {
    return fxp(x, mod - 2);
}

ll bnm(ll a, ll b) {
    if (a < b || b < 0) return 0;
    ll r = (fc[a] * nv[b]) % mod;
    r = (r * nv[a - b]) % mod;
    return r;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    fc[0] = 1; nv[0] = 1;
    for (i = 1; i < maxn; i++) {
        fc[i] = (i * fc[i - 1]) % mod; nv[i] = inv(fc[i]);
    }

    cin >> n;

    dp[0][0] = 1;
    for (i = 1; i <= n; i++) {
        for (j = 0; j <= n; j++) {
            dp[i][j] = 0;
            for (k = 0; k <= j; k++) {
                dp[i][j] = (dp[i][j] + dp[i - 1][k] * bnm(n - k, n - j)) % mod;
            }
        }
    }
    res = dp[n][n];

    dp[0][0] = 1;
    for (i = 1; i <= n; i++) {
        for (j = 0; j <= n; j++) {
            dp[i][j] = 0;
            for (k = 0; k <= j; k++) {
                if (j - k == i) continue;
                dp[i][j] = (dp[i][j] + dp[i - 1][k] * bnm(n - k, n - j)) % mod;
            }
        }
    }
    res = (res - dp[n][n] + mod) % mod;

    cout << res << nl;

    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55