Submission #242669

#	Time	Username	Problem	Language	Result	Execution time	Memory
242669		kingfran1907	Zapina (COCI20_zapina)	C++14	110 / 110	382 ms	5372 KiB

zapina

#include <bits/stdc++.h>

using namespace std;
typedef long long llint;

const int maxn = 400;
const llint mod = 1e9+7;

int n;
llint dp[maxn][maxn][3];
llint fac[maxn];
llint chos[maxn][maxn];

llint f(int x, int y, bool flag) {
    if (x == n + 1) {
        if (y == 0) return flag;
        else return 0;
    }

    llint &ret = dp[x][y][flag];
    if (ret != -1) return ret;

    ret = 0;
    for (int i = 0; i <= y; i++) {
        ret += chos[y][i] * f(x + 1, y - i, flag || (i == x));
        ret %= mod;
    }
    return ret;
}

llint pot(llint a, llint b) {
    if (b == 0) return 1;
    else if (b % 2 == 1) return (a * pot(a, b - 1)) % mod;
    else {
        llint out = pot(a, b / 2);
        return (out * out) % mod;
    }
}

llint inv(llint x) {
    return pot(x, mod - 2);
}

llint choose(int a, int b) {
    llint out = fac[a];
    out *= inv(fac[b]), out %= mod;
    out *= inv(fac[a - b]), out %= mod;
    return out;
}

int main() {
    memset(dp, -1, sizeof dp);
    scanf("%d", &n);
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i, fac[i] %= mod;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            chos[i][j] = choose(i, j);
        }
    }
    printf("%lld\n", f(1, n, false));
    return 0;
}

Compilation message (stderr)

zapina.cpp: In function 'int main()':
zapina.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~

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