제출 #931351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
931351		Whisper	Zapina (COCI20_zapina)	C++17	110 / 110	217 ms	2312 KiB

zapina

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using str = string;
// using T = tuple<double, ll, ll>;

#define int long long
#define Base 31
#define sz(a) (int)a.size()
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for ( int i = b ; i >= a ; i-- )
#define REP(i, n) for ( int i = 0 ; i < n ; ++i )
#define REPD(i, n) for ( int i =  n - 1 ; ~(--i) ; )
#define all(x) x.begin() , x.end()
#define pii pair<int , int>
#define fi first
#define se second
#define Lg(x) 31 - __builtin_clz(x)

constexpr ll LINF = (1ll << 62);
constexpr int INF = (1ll << 31);
constexpr int MAX = 351;
constexpr int Mod = 1e9 + 7;

void setupIO( const string& PROB ){

    //Phu Trong from Nguyen Tat Thanh High School for gifted student

    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
//    freopen( (PROB + ".inp").c_str(), "r", stdin);
//    freopen( (PROB + ".out").c_str(), "w", stdout);
    cout << fixed << setprecision(10);
}

int ifac[MAX], fac[MAX];

int power(int a, int b){
    int res = 1;
    for ( ; b; b >>= 1 , a = (a * a) % Mod) if(b & 1){
        res = (res * a) % Mod;
    }
    return res;
}
void genFac(int n){
    ifac[0] = fac[0] = 1;
    for(int i = 1 ; i <= n ; i++) fac[i] = fac[i - 1] * i % Mod;
    for(int i = 1 ; i <= n ; i++) ifac[i] = power(fac[i] , Mod - 2);
}

int c(int n , int k){
    assert(n >= k);
    return fac[n] * ifac[n - k] % Mod * ifac[k] % Mod;
}
int n;
int f[MAX][MAX][2];

//f(i, j, k): cách chia bánh cho i thằng đầu sao cho dư j cái bánh và đã có thằng thỏa mãn hay chưa
void Whisper(){ 
    int n; cin >> n;

    genFac(n);
    f[0][n][0] = 1;
    for ( int i = 1 ; i <= n ; i++ ){ // thằng thứ i
        for ( int j = 0 ; j <= n ; j++ ){ // còn dư j cái bánh
            for ( int k = 0 ; k <= j ; k++ ){ // cho thằng thứ i k cái bánh
                if (i == k){
                    f[i][j - k][1] += (f[i - 1][j][0] + f[i - 1][j][1]) % Mod * c(j , k);
                    f[i][j - k][1] %= Mod;
                }
                else{
                    (f[i][j - k][1] += (f[i - 1][j][1] * c(j , k)) % Mod) %= Mod;

                    (f[i][j - k][0] += (f[i - 1][j][0] * c(j , k)) % Mod)  %= Mod;
                }
            }
        }
    }
    cout << f[n][0][1];
}   
    
signed main(){
    setupIO("Whisper");
    int Test = 1;
    // cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

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