Submission #1274865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274865		flaming_top1	Zapina (COCI20_zapina)	C++20	110 / 110	124 ms	1412 KiB

zapina

#include <bits/stdc++.h>

#define SPED                                                                                                           \
    ios_base::sync_with_stdio(false);                                                                                  \
    cin.tie(0);                                                                                                        \
    cout.tie(0);

#define endl "\n"
#define fi first
#define se second
#define lint long long
#define fami signed
#define lore main
#define freefire freopen

const lint INF = 0x1f1f1f1f1f1f1f1f;
const lint NEG = 0xE1E1E1E1E1E1E1E1;
const lint mod = 1e9 + 7;

using namespace std;

lint n;
lint dp[355][355], gt[355], inv[355];

lint binpow(lint x, lint k)
{
    if (k == 0)
        return 1;
    lint temp = binpow(x, k >> 1);
    temp *= temp;
    temp %= mod;
    if (k & 1)
    {
        temp *= x;
        temp %= mod;
    }
    return temp;
}

lint C(lint N, lint K)
{
    return ((gt[N] * inv[K]) % mod * inv[N - K]) % mod;
}

fami lore()
{
    SPED;
    cin >> n;

    gt[0] = 1;
    for (int i = 1; i <= 352; i++)
    {
        gt[i] = gt[i - 1] * i;
        gt[i] %= mod;
    }

    inv[352] = binpow(gt[352], mod - 2);
    for (int i = 351; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1);
        inv[i] %= mod;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int k = 0; k <= n; k++)
        {
            if (k >= i)
            {
                dp[k][i] += C(k, i) * binpow(i - 1, k - i);
                dp[k][i] %= mod;
            }

            for (int j = 0; j <= k; j++)
            {
                if (j != i)
                {
                    dp[k][i] += (dp[k - j][i - 1] * C(k, j)) % mod;
                    dp[k][i] %= mod;
                }
            }
        }
    }
    cout << dp[n][n];
}
// Let your soul wander where dreams are born.

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