제출 #1149506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149506		AtabayRajabli	Zapina (COCI20_zapina)	C++20	110 / 110	127 ms	2256 KiB

zapina

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define int long long
using namespace std;

const int sz = 351, mod = 1e9 + 7;
int n, f[sz], inv[sz], dp[2][sz][sz];

int bp(int a, int b, int r = 1)
{
    while(b > 0)
    {
        if(b & 1) r = r * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return r;
}

int C(int n, int k)
{
    if(n < k) return 0;
    return f[n] * inv[k] % mod * inv[n - k] % mod;
}

void solve()
{
    cin >> n;
    dp[0][0][0] = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            for(int cur = 0; cur <= j; cur++)
            {
                if(cur != i) 
                {
                    dp[0][i][j] = (dp[0][i][j] + dp[0][i - 1][j - cur] * C(j, cur)) % mod;
                    dp[1][i][j] = (dp[1][i][j] + dp[1][i - 1][j - cur] * C(j, cur)) % mod;
                }
                else
                {
                    dp[1][i][j] = (dp[1][i][j] + (dp[1][i - 1][j - cur] + dp[0][i - 1][j - cur]) * C(j, cur)) % mod;
                }
            }
        }
    }
    cout << dp[1][n][n];
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); 

    f[0] = inv[0] = 1;
    for(int i = 1; i < sz; i++)
    {
        f[i] = f[i - 1] * i % mod;
        inv[i] = bp(f[i], mod - 2);
    }
    
    int t = 1;
    // cin >> t;
    while(t--) solve();
}

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