Submission #210032

#	Time	Username	Problem	Language	Result	Execution time	Memory
210032		apostoldaniel854	Zapina (COCI20_zapina)	C++14	110 / 110	108 ms	1272 KiB

zapina

/*
https://oj.uz/problem/view/COCI20_zapina
*/


#include <bits/stdc++.h>

using namespace std;


typedef long long ll;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

const int N = 350;


/// dp[i][many] = the number of ways to not make anybody happy with many tasks and on prefix 1..i of programmers

const int MOD = 1e9 + 7;

int dp[1 + N][1 + N];
int comb[1 + N][1 + N];
void add (int &a, int b) {
    a += b;
    if (a >= MOD)
        a -= MOD;
}

int main() {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    int n;
    cin >> n;
    for (int i = 0; i <= n; i++) {
        comb[i][0] = 1;
        for (int j = 1; j <= i; j++)
            comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
    }
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int many = 0; many <= n; many++) {
            for (int j = 0; j <= many; j++) {
                if (j == i) continue;
                add (dp[i][many], 1ll * dp[i - 1][many - j] * comb[n - (many - j)][j] % MOD);
            }
        }
    }
    int ans = 1;
    for (int i = 1; i <= n; i++)
        ans = 1ll * ans * n % MOD;
    ans -= dp[n][n];
    if (ans < 0)
        ans += MOD;
    cout << ans << "\n";
    return 0;
}

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