Submission #1284922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284922		paronmanukyan	Zapina (COCI20_zapina)	C++20	110 / 110	104 ms	1380 KiB

zapina

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

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define sort_uniq(x) sort(all(x)), uniq(x);
#define no_el(x, y) x.find(y) == x.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define V vector
#define V2dll V<V<ll>>
#define V2dint V<V<int>>
#define V2dchar V<V<char>>
#define V2dbool V<V<bool>>
#define V3dll V<V<V<ll>>>
#define V3dint V<V<V<int>>>
#define V3dchar V<V<V<char>>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define FASTIO                                                                 \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(nullptr);                                                            \
  cout.tie(nullptr);
#define INF INT32_MAX
#define blt __builtin_popcount
#define clr(x) x.clear()
#define ff first
#define ss second
#define popf pop_front
#define popb pop_back
#define sz(x) int(x.size())
#define rep(a, b, c, d) for (int a = b; a <= c; a += d)
#define repl(a, b, c, d) for (int a = b; a >= c; a -= d)

mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());

const int MOD = 1e9 + 7;
const int N = 355;
ll dp[N][N]; // demi i hat, j cragrov
ll fac[N], inv[N];

ll binpow(ll a, ll b) {
    if (b == 0) return 1;
    if (b == 1) return a;
    if (b & 1) return a * binpow(a, b - 1) % MOD;
    return binpow(a * a % MOD, b >> 1);
}

ll mult(ll a, ll b) {
    return a * b % MOD;
}

ll sum(ll a, ll b) {
    if (a + b >= MOD)
        return a + b - MOD;
    else 
        return a + b;
}

void pr() {
    fac[0] = 1;
    rep(i, 1, N - 1, 1) 
        fac[i] = mult(i, fac[i - 1]);
    inv[N - 1] = binpow(fac[N - 1], MOD - 2);
    repl(i, N - 2, 0, 1) {
        inv[i] = mult(i + 1, inv[i + 1]);
    }
}

ll Cnk(ll n, ll k) {
    return mult(mult(fac[n], inv[k]), inv[n - k]);
}

int main()
{
	FASTIO
    pr();
	int n; cin >> n;
    dp[1][1] = 1;
    rep(i, 2, n, 1) {
        rep(j, 0, n, 1) {
            rep(k, 0, j, 1) {
                if (k == i) 
                    dp[i][j] = sum(dp[i][j], mult(Cnk(j, k), binpow(i - 1, j - k)));
                else
                    dp[i][j] = sum(dp[i][j], mult(Cnk(j, k), dp[i - 1][j - k]));
            }
        }
    }

    cout << dp[n][n] << "\n";
}

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