Submission #2947875


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
template<int MOD> struct ModInt {
    static const int Mod = MOD; unsigned x; ModInt() : x(0) { }
    ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    int get() const { return (int)x; }
    ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
    ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0;
        while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); }
        return ModInt(u); }
    bool operator==(ModInt that) const { return x == that.x; }
    bool operator!=(ModInt that) const { return x != that.x; }
    ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
template<int MOD> ostream& operator<<(ostream& st, const ModInt<MOD> a) { st << a.get(); return st; };
template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
    ModInt<MOD> r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; }
template<typename T, int FAC_MAX> struct Comb { vector<T> fac, ifac;
    Comb(){fac.resize(FAC_MAX,1);ifac.resize(FAC_MAX,1);rep(i,1,FAC_MAX)fac[i]=fac[i-1]*i;
        ifac[FAC_MAX-1]=T(1)/fac[FAC_MAX-1];rrep(i,FAC_MAX-2,1)ifac[i]=ifac[i+1]*T(i+1);}
    T aPb(int a, int b) { if (b < 0 || a < b) return T(0); return fac[a] * ifac[a - b]; }
    T aCb(int a, int b) { if (b < 0 || a < b) return T(0); return fac[a] * ifac[a - b] * ifac[b]; }
    T nHk(int n, int k) { if (n == 0 && k == 0) return T(1); if (n <= 0 || k < 0) return 0;
        return aCb(n + k - 1, k); }}; // nHk = (n+k-1)Ck
typedef ModInt<998244353> mint;
/*---------------------------------------------------------------------------------------------------
            ∧_∧  
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     
    /   \     | |     
    /   / ̄ ̄ ̄ ̄/  |  
  __(__ニつ/     _/ .| .|____  
     \/____/ (u ⊃  
---------------------------------------------------------------------------------------------------*/






int N, A[1010], B[1010];
mint dp[1010][2010];
Comb<mint, 2020> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) B[A[i]]++;

    dp[N + 1][0] = 1;
    rrep(team, N + 1, 2) rep(rest, 0, N + 1) if(dp[team][rest].get()) {
        int team2 = team - 1;
        int rest2 = rest + B[team2];

        for (int i = 0; i*team2 <= rest2; i++) {
            dp[team2][rest2 - i * team2] += dp[team][rest] * com.aPb(rest2, i * team2) * com.ifac[i] / (com.fac[team2] ^ i);
        }
    }

    cout << dp[1][0] << endl;
}

Submission Info

Submission Time
Task F - チーム分け
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 600
Code Size 4178 Byte
Status
Exec Time 772 ms
Memory 8192 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0
All 600 / 600 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 8 ms 8192 KB
02.txt 8 ms 8192 KB
03.txt 8 ms 8192 KB
04.txt 8 ms 8192 KB
05.txt 8 ms 8192 KB
06.txt 11 ms 8192 KB
07.txt 10 ms 8192 KB
08.txt 10 ms 8192 KB
09.txt 10 ms 8192 KB
10.txt 10 ms 8192 KB
11.txt 589 ms 8192 KB
12.txt 627 ms 8192 KB
13.txt 605 ms 8192 KB
14.txt 597 ms 8192 KB
15.txt 544 ms 8192 KB
16.txt 772 ms 8192 KB
17.txt 763 ms 8192 KB
18.txt 758 ms 8192 KB
19.txt 761 ms 8192 KB
20.txt 757 ms 8192 KB
21.txt 8 ms 8192 KB
22.txt 8 ms 8192 KB
23.txt 8 ms 8192 KB
24.txt 8 ms 8192 KB
s1.txt 8 ms 8192 KB
s2.txt 8 ms 8192 KB
s3.txt 8 ms 8192 KB