제출 #545665

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545665		AlperenT	Zapina (COCI20_zapina)	C++17	110 / 110	258 ms	1356 KiB

zapina

#include <bits/stdc++.h>

using namespace std;

const int N = 350 + 5, MOD = 1e9 + 7;

struct mint{
    int val = 0;
 
    mint(long long a = 0) : val(a % MOD) {if(val < 0) val += MOD; }
    mint(long long a, long long b) {*this += a; *this /= b; }
 
    mint &operator += (const mint &b) {val += b.val; if(val >= MOD) val -= MOD; return *this; }
    mint &operator -= (const mint &b) {val -= b.val; if(val < 0) val += MOD; return *this; }
    mint &operator *= (const mint &b) {val = (1ll * val * b.val) % MOD; return *this; }
 
    mint mexp(mint a, long long b){
        mint c(1);
        for(; b > 0; b /= 2, a *= a) if(b & 1) c *= a;
        return c;
    }
 
    mint minv(const mint &a) {return mexp(a, MOD - 2); };
 
    mint &operator /= (const mint &b) {*this *= minv(b); return *this; }
 
    friend mint operator + (mint a, const mint &b) {return a += b; }
    friend mint operator - (mint a, const mint &b) {return a -= b; }
    friend mint operator - (const mint &a) {return 0 - a; }
    friend mint operator * (mint a, const mint &b) {return a *= b; }
    friend mint operator / (mint a, const mint &b) {return a /= b; }
 
    friend bool operator == (const mint &a, const mint &b) {return a.val == b.val; }
    friend bool operator != (const mint &a, const mint &b) {return a.val != b.val; }
 
    friend istream &operator >> (istream &is, mint &a) {long long b; is >> b; a = b; return is; }
    friend ostream &operator << (ostream &os, const mint &a) {return os << a.val; }
};

int n;

mint dp[N][N][2], fact[N], invfact[N];

void precalc(){
    fact[0] = 1;
    for(int i = 1; i < N; i++) fact[i] = fact[i - 1] * i;

    invfact[N - 1] = mint().minv(fact[N - 1]);
    for(int i = N - 2; i >= 0; i--) invfact[i] = invfact[i + 1] * (i + 1);
}

mint comb(int a, int b){
    return fact[a] * (invfact[a - b] * invfact[b]);
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    precalc();

    cin >> n;

    dp[0][0][0] = 1;

    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= n; j++){
            for(int k = 0; k <= j; k++){
                if(k == i){
                    dp[i][j][1] += dp[i - 1][j - k][0] * comb(n - (j - k), k);
                    dp[i][j][1] += dp[i - 1][j - k][1] * comb(n - (j - k), k);
                }
                else{
                    dp[i][j][0] += dp[i - 1][j - k][0] * comb(n - (j - k), k);
                    dp[i][j][1] += dp[i - 1][j - k][1] * comb(n - (j - k), k);
                }
            }
        }
    }

    cout << dp[n][n][1];
}

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