Submission #447169

#	Time	Username	Problem	Language	Result	Execution time	Memory
447169		Chy_Chy	Zapina (COCI20_zapina)	C++14	110 / 110	533 ms	2628 KiB

zapina

#include<bits/stdc++.h>
using namespace std;

#include<ext/pb_ds/assoc_container.hpp> // common file
#include<ext/pb_ds/tree_policy.hpp> // including tree_order_statistics_node_update

using namespace __gnu_pbds;


#define int             long long
#define pb              push_back
#define ppb             pop_back
#define pf              push_front
#define ppf             pop_front
#define all(x)          (x).begin(), (x).end()
#define uniq(v)         (v).erase(unique(all(v)), (v).end())
#define sz(x)           (int)((x).size())
#define ff              first
#define ss              second
#define rep(i, a, b)    for(int i = a; i <= b; i++)
#define mem1(a)         memset(a, -1, sizeof(a))
#define mem0(a)         memset(a, 0, sizeof(a))
#define endl            "\n"
#define debug(x)        cerr << #x << " == " << (x) << '\n';
#define YES             cout << "YES\n"
#define NO              cout << "NO\n"
#define nn              "\n"

// bit manipulation
#define SetBit(x, k)    (x |= (1LL << k))
#define ClearBit(x, k)  (x &= ~(1LL << k))
#define CheckBit(x, k)  (x & (1LL << k))


typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;

#define ordered_set tree<int, null_type, less<int> , rb_tree_tag, tree_order_statistics_node_update>

const long long INF = 1e18;
const int32_t M = 1e9 + 7;
const int32_t MM = 998244353;


int binpow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = a * res;
        }
        a = a * a;
        b >>= 1;
    }
    return res;
}


void fast_io()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}
int gcd(int a, int b) {if (b == 0) return a; return gcd(b, a % b);}
int lcm(int a, int b) {return a / gcd(a, b) * b;}


const int N = 400;


#define PRIME   M

int binpow(int a, int b = M - 2, int MOD = M) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = a * res % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int fact[N], invfact[N];


void init() {

    int p = PRIME;
    fact[0] = 1;

    int i;
    for (i = 1; i < N; i++) {
        fact[i] = i * fact[i - 1] % p;

    }

    i--;
    invfact[i] = binpow(fact[i], p - 2, p);

    for (i--; i >= 0; i--) {
        invfact[i] = invfact[i + 1] * (i + 1) % p;
    }


}

int ncr(int n, int r) {

    if (r > n || n < 0 || r < 0) return 0;

    return fact[n] * invfact[r] % PRIME * invfact[n - r] % PRIME;
}


int mem[N][N][2];

int n;


int dp(int prog, int baki, int happy) {
    if (prog > n) {
        if (baki == 0 && happy == 1) {
            return 1;
        }
        return 0;
    }
    // debug(prog);
    // debug(baki);
    int &ans = mem[prog][baki][happy];

    if (ans != -1) return ans;

    ans = 0;
    int res;
    for (int i = 0; i <= baki; i++) {
        if (i == prog) {
            res = (ncr(baki, i) * dp(prog + 1, baki - i, 1)) % M;
            ans = (ans + res) % M;
        }
        else {
            res = (ncr(baki, i) * dp(prog + 1, baki - i, happy)) % M;
            ans = (ans + res) % M;
        }
    }

    return ans;
}
void KhelaFinal() {
    cin >> n;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k < 2; k++) {
                mem[i][j][k] = -1;
            }
        }
    }


    cout << dp(1, n, 0) << endl;



}

signed main()
{
    fast_io();
//#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//#endif
    int t = 1;

    // cin >> t;
    init();

    while (t--) {

        KhelaFinal();


    }
    return 0;


}

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