Submission #1102401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102401		shidou26	Zapina (COCI20_zapina)	C++14	110 / 110	386 ms	3708 KiB

zapina

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

#define endl '\n'

typedef long long ll;

const int MOD = 1e9 + 7;
ll add(ll x, ll y) {return ((x % MOD) + (y % MOD)) % MOD;}
ll prod(ll x, ll y) {return ((x % MOD) * (y % MOD)) % MOD;}
ll sub(ll x, ll y) {return ((x - y) % MOD + MOD) % MOD;}
ll pwer(ll x, ll y) {
    if(y == 0) return 1;
    ll half = pwer(x, y / 2);
    half = prod(half, half);
    if(y & 1) return prod(half, x);
    else return half;
}

const int N = 1e3 + 3;

int n;

ll fact[N + 1], inv[N + 1];

void preprocess() {
    fact[0] = 1;
    for(int i = 1; i <= N; i++) fact[i] = prod(fact[i - 1], i);
    inv[N] = pwer(fact[N], MOD - 2);
    for(int i = N - 1; i >= 0; i--) inv[i] = prod(inv[i + 1], i + 1);
}

ll C(ll k, ll n) {
    if(k > n) return 0;
    return prod(fact[n], prod(inv[k], inv[n - k]));
}

void input() {
    cin >> n;
}

namespace subtask_two {
    ll compute(int mask) {
        ll candies = n, remains = 0, ways = 1;
        for(int i = 0; i < n; i++) {
            if(mask & (1 << i)) {
                ways = prod(ways, C(i + 1, candies));
                candies -= i + 1;
            }else remains++;
        }
        ways = prod(ways, pwer(remains, candies));
        if(candies < 0) return 0;
        else return ways;
    }

    void solve() {
        ll total = pwer(n, n), answer = 0;
        for(int mask = 0; mask < (1 << n); mask++) {
            if(__builtin_popcount(mask) % 2 == 0) answer = add(answer, compute(mask));
            else answer = sub(answer, compute(mask));
        }
        cout << sub(total, answer) << endl;
    }

    bool check() {
        return n <= 20;
    }
}

namespace subtask_three {
    ll dp[N][N][2];

    void solve() {
        dp[0][0][0] = 1;
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= n; j++) {
                for(int c = 0; c <= j; c++) {
                    if(c == i)
                        dp[i][j][1] = add(dp[i][j][1], add(prod(dp[i - 1][j - c][0], C(c, j)), prod(dp[i - 1][j - c][1], C(c, j))));
                    else {
                        dp[i][j][0] = add(dp[i][j][0], prod(dp[i - 1][j - c][0], C(c, j)));
                        dp[i][j][1] = add(dp[i][j][1], prod(dp[i - 1][j - c][1], C(c, j)));
                    }
                }
            }
        }
        cout << dp[n][n][1] << endl;
    }

    bool check() {
        return n <= 350;
    }
}

void process() {
    if(subtask_two::check()) return subtask_two::solve(), void();
    if(subtask_three::check()) return subtask_three::solve(), void();
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    preprocess();
    input();
    process();

    return 0;
}

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