Submission #1203825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203825		Mighilon	Zapina (COCI20_zapina)	C++20	55 / 110	138 ms	952 KiB

zapina

#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "../Library/debug.h"
#else
#define dbg(x...)
#endif
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) for (int i = 0; i < (a); ++i)
#define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i)
#define trav(a, x) for (auto& a : x)
#define f first 
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
 
const char nl = '\n';
const int INF = 1e9;
const ll MOD = 998244353;


template <const int32_t MOD>
struct modint {
    int32_t value;
    modint() = default;
    modint(int32_t value_) : value(value_) {}
    modint<MOD> operator + (const modint<MOD>& other) const { int32_t c = value + other.value; return modint<MOD>(c >= MOD ? c - MOD : c); }
    modint<MOD> operator - (const modint<MOD> other) const { int32_t c = value - other.value; return modint<MOD>(c < 0 ? c + MOD : c); }
    modint<MOD> operator * (const modint<MOD> other) const { int32_t c = (int64_t)value * other.value % MOD; return modint<MOD>(c < 0 ? c + MOD : c); }
    modint<MOD>& operator += (const modint<MOD> other) { value += other.value; if (value >= MOD) value -= MOD; return *this; }
    modint<MOD>& operator -= (const modint<MOD> other) { value -= other.value; if (value < 0) value += MOD; return *this; }
    modint<MOD>& operator *= (const modint<MOD> other) { value = (int64_t)value * other.value % MOD; if (value < 0) value += MOD; return *this; }
    modint<MOD> operator - () const { return modint<MOD>(value ? MOD - this->value : 0); }
    modint<MOD> pow(uint64_t k) const { modint<MOD> x = *this, y = 1; for (; k; k >>= 1) { if (k & 1) y *= x; x *= x; } return y; }
    modint<MOD> inv() const { return pow(MOD - 2); }  // MOD must be a prime
    modint<MOD> operator / (const modint<MOD> other) const { return *this * other.inv(); }
    modint<MOD> operator /= (const modint<MOD> other) { return *this *= other.inv(); }
    bool operator == (const modint<MOD> other) const { return value == other.value; }
    bool operator != (const modint<MOD> other) const { return value != other.value; }
    bool operator < (const modint<MOD> other) const { return value < other.value; }
    bool operator > (const modint<MOD> other) const { return value > other.value; }
};
template <int32_t MOD> modint<MOD> operator * (int32_t value, modint<MOD> n) { return modint<MOD>(value) * n; }
template <int32_t MOD> modint<MOD> operator * (int64_t value, modint<MOD> n) { return modint<MOD>(value % MOD) * n; }
template <int32_t MOD> istream& operator >> (istream& in, modint<MOD>& n) { return in >> n.value; }
template <int32_t MOD> ostream& operator << (ostream& out, modint<MOD> n) { return out << n.value; }

using mint = modint<(int)1e9 + 7>;
void __print(mint x) { cerr << x; }

struct Combinatorics{
    int n; vector<mint> facts, finvs, invs;
    Combinatorics(int _n): n(_n), facts(_n), finvs(_n), invs(_n){
        facts[0] = finvs[0] = 1;
        invs[1] = 1;
        
        for(int i = 1; i < n; ++i)
            facts[i] = facts[i - 1] * i;

        finvs[n - 1] = facts[n - 1].inv();
        for(int i = n - 1; i >= 1; --i){
            invs[i] = finvs[i] * facts[i - 1];
            finvs[i - 1] = finvs[i] * i;
        }
    }
    mint fact(int x) { return facts[x]; }
    mint finv(int x) { return finvs[x]; }
    mint inv(int x) { return invs[x]; }
    mint chose(int a, int b) { return a < b or b < 0 ? 0 : facts[a] * finvs[b] * finvs[a - b]; }
} C(351);

int n;
mint dp[351][351];
mint f(int i, int j){
    // dbg(i,j)
    if(dp[i][j]!=-1)
        return dp[i][j];
    if(i>n)
        return 0;
    mint res=0;
    if(j>=i){
        // dbg(j,i,n-i,j-i)
        res= C.chose(j,i) * mint(n-i).pow(j-i);
    }
    FOR(k,0,j+1){
        if(k!=i){
            res += f(i+1,j-k)*C.chose(j,k);
        }
    }
    return dp[i][j]=res;
}

void solve(){
    cin>>n;
    memset(dp,-1,sizeof dp);
    cout<<f(1,n)<<nl;
}
 
int32_t main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int TC = 1;
    // cin >> TC;
    while(TC--){
        solve();
    }
    return 0;
}

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