제출 #1284896

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284896		hrantsargsyan	Zapina (COCI20_zapina)	C++20	110 / 110	447 ms	10592 KiB

zapina

// Task Zapina.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>

using namespace std;

const int N = 1005;

long long dp[N][N][2];
long long C[N][N];
long long mod = 1e9 + 7;

long long add(long long a, long long b)
{
    a %= mod; b %= mod;
    long long res = a + b;
    if (res >= mod) res -= mod;
    return res;
}
long long mult(long long x, long long y)
{
    return (x % mod) * (y % mod) % mod;
}

void precalcC() {
    for (int n = 0; n <= 1000; n++) {
        C[n][0] = C[n][n] = 1;
        for (int k = 1; k < n; k++)
            C[n][k] = add(C[n - 1][k - 1], C[n - 1][k]);
    }
}

int main()
{
    int n;
    cin >> n;
    precalcC();
    dp[1][1][1] = 1;
    dp[1][0][0] = 1;
    dp[1][1][0] = 0;
    for (int i = 2;i <= n;++i)
    {
        dp[1][i][0] = 1;
    }
    for (int i = 1;i <= n;++i)
    {
        for (int j = 0;j <= n;++j)
        {
            for (int k = 0;k <= j;++k)
            {
                int x = C[j][k];
                if (k != i)
                {
                    dp[i][j][0] = add(dp[i][j][0], mult(dp[i - 1][j - k][0], x));
                }
                else
                {
                    dp[i][j][1] = add(dp[i][j][1], mult(dp[i-1][j - k][0], x));
                }
                dp[i][j][1] = add(dp[i][j][1], mult(dp[i-1][j - k][1], x));
            }
        }
    }
    //for (int i = 1;i <= n;++i)
    //{
    //    for (int j = 0;j <= n;++j)
    //    {
    //        cout << i << " people " << j << " tasks." << endl;
    //        cout << dp[i][j][1] << " Happy " << endl;
    //        cout << dp[i][j][0] << " uhappy " << endl;
    //    }
    //}
    cout << dp[n][n][1] << endl;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

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