제출 #1231191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231191		luka_zecevic	Zapina (COCI20_zapina)	C++20	55 / 110	1093 ms	596 KiB

zapina

#include "bits/stdc++.h"
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;

const int N = 355;
int mod = 1e9 + 7;
int fact[N];
int dp[N][N][2];


int stepen(int a, int n)
{
    if(n == 0) return 1;
    if(n % 2 == 0) return stepen((long long)a * a % mod, n / 2);
    return (long long)stepen(a, n - 1) * a % mod;
}

int bk(int n, int k)
{
    return (long long)fact[n] * stepen((long long)fact[n - k] * fact[k] % mod, mod - 2) % mod;
}

int sum(int a, int b)
{
    return (a + b) % mod;
}

int mult(int a, int b)
{
    return (long long)a * b % mod;
}
int main()
{
    FAST;

    fact[0] = 1;
    for(int i = 1; i < N; i++) fact[i] = (long long)fact[i - 1] * i % mod;

    int n; cin >> n;
    dp[0][0][0] = 1;// i, j, k = broj ljudi, broj zadataka, 0/1 - da li sam imao nekog srecnog

    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= n; j++)
        { 
            for(int k = 0; k <= j; k++)
            {
                dp[i][j][1] = sum(dp[i][j][1], mult(dp[i - 1][j - k][1], bk(n - (j - k), k)));
                if(k == i) { dp[i][j][1] = sum(dp[i][j][1], mult(dp[i - 1][j - k][0], bk(n - (j - k), k))); continue; }
                dp[i][j][0] = sum(dp[i][j][0], mult(dp[i - 1][j - k][0], bk(n - (j - k), k)));
            }
        }
    }

    // for(int i = 1; i <= n; i++)
    // {
    //     for(int j = 1; j <= n; j++) cout << "{ " << dp[i][j][0] << " , " << dp[i][j][1] << " } ";
    //     cout << "\n";
    // }
    cout << dp[n][n][1] << "\n";

    return 0;
}

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