Submission #442866

#	Time	Username	Problem	Language	Result	Execution time	Memory
442866		colossal_pepe	Zapina (COCI20_zapina)	C++17	0 / 110	1 ms	1228 KiB

zapina

#include <iostream>
#include <cstring>
using namespace std;

#define int long long

const int MOD = 1000000007;

int n, dp[355][355];

void setup() {
    memset(dp, -1, sizeof(dp));
    for (int i = n + 1; i < 355; i++) {
        dp[i][0] = 1;
        for (int j = 1; j < 355; j++) {
            dp[i][j] = 0;
        }
    }
}

int ways(int x) {
    int ans = 1;
    for (int i = 0; i < x; i++) {
        ans *= x;
        ans %= MOD;
    }
    return ans % MOD;
}

int badWays(int p, int t) {
    if (dp[p][t] != -1) return dp[p][t] % MOD;
    dp[p][t] = 0;
    for (int i = 0; i <= t; i++) {
        if (i == p) continue;
        dp[p][t] += badWays(p + 1, t - i) % MOD;
        dp[p][t] %= MOD;
    }
    return dp[p][t] % MOD;
}

signed main() {
    cin >> n;
    setup();
    cout << ways(n) - badWays(1, n) << endl;
    return 0;
}

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