F - チーム分け Mujin Programming Challenge 2018

問題概略

N人の人をチーム分けしたい。
ただしi番目の人はai人以下のチームに配属しなくてはいけない

制約
1<=N<=1000
1≤ai≤N

解法
一人ひとりについてどのチームに属するか考える事はできない。
oo人以下にしか属せない物の数を数えておけばまとめて考えることが出来る。
N人チームがoo個、N-1人チームがoo個、N-2人チームが……という様な物を全通り試せれば答えがわかる
dp[i][j]を今i人以上のチームについて考えていて、j人が自由に属する事が出来るという風に定義すれば大きいiから順に見ていき遷移できる。

r人の中からs人チームをk組選ぶ方法は
rCs * r-sCs * .... / k!を漸化的にもつ方法と
r人からs*k人を横にならべ、s人ずつでk回区切り重複を消す方法
r! / (r-s*k)! / k! / s!^k　を調べる場合がある　
後者は漸化的に書かなくていい代わりにpowで対数時間かかる。

Submission #3391769 - Mujin Programming Challenge 2018 | AtCoder

//mod関連
ll MOD = (int) 1e9 + 7;
const int setModMax = 510000;
ll fac[setModMax], finv[setModMax], inv[setModMax];

void setMod() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < setModMax; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}


ll minv(ll a) {
    if (a < setModMax) return inv[a];
    a %= MOD;
    ll b = MOD, x = 1, y = 0;
    while (b) {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        x -= t * y;
        swap(x, y);
    }
    return (x % MOD + MOD) % MOD;
}


class mint {
private:
    ll v;
public:
    static ll mod(ll a) { return (a % MOD + MOD) % MOD; }

    mint(ll a = 0) { this->v = mod(a); }

    mint(const mint &a) { v = a.v; }

    mint operator+(const mint &a) { return mint(v + a.v); }

    mint operator+(const ll a) { return mint(v + a % MOD); }

    friend mint operator+(const ll a, const mint &b) { return mint(a % MOD + b.v); }

    void operator+=(const mint &a) { v = (v + a.v) % MOD; }

    void operator+=(const ll a) { v = mod(v + a % MOD); }

    friend void operator+=(ll &a, const mint &b) { a = mod(a % MOD + b.v); }

    mint operator-(const mint &a) { return mint(v - a.v); }

    mint operator-(const ll a) { return mint(v - a % MOD); }

    friend mint operator-(const ll a, const mint &b) { return mint(a % MOD - b.v); }

    void operator-=(const mint &a) { v = mod(v - a.v); }

    void operator-=(const ll a) { v = mod(v - a % MOD); }

    friend void operator-=(ll &a, const mint &b) { a = mod(a % MOD - b.v); }

    mint operator*(const mint &a) { return mint(v * a.v); }

    mint operator*(const ll a) { return mint(v * (a % MOD)); }

    friend mint operator*(const ll a, const mint &b) { return mint(a % MOD * b.v); }

    void operator*=(const mint &a) { v = (v * a.v) % MOD; }

    void operator*=(const ll a) { v = mod(v * (a % MOD)); }

    friend void operator*=(ll &a, const mint &b) { a = mod(a % MOD * b.v); }

    mint operator/(const mint &a) { return mint(v * minv(a.v)); }

    mint operator/(const ll a) { return mint(v * minv(a)); }

    friend mint operator/(const ll a, const mint &b) { return mint(a % MOD * minv(b.v)); }

    void operator/=(const mint &a) { v = (v * minv(a.v)) % MOD; }

    void operator/=(const ll a) { v = mod(v * minv(a)); }

    friend void operator/=(ll &a, const mint &b) { a = mod(a % MOD * minv(b.v)); }

    mint operator^(const mint &a) {
        ll x = v, n = a.v, res = 1;
        while (n) {
            if (n & 1)res = (res * x) % MOD;
            x = (x * x) % MOD;
            n >>= 1;
        }
        return res;
    }

    //単項演算子
    mint operator+() { return *this; }

    mint operator++() {
        v++;
        return *this;
    }

    mint operator++(signed d) {
        mint res = *this;
        v++;
        return res;
    }

    mint operator-() { return operator*(-1); }

    mint operator--() {
        v++;
        return *this;
    }

    mint operator--(signed d) {
        mint res = *this;
        v++;
        return res;
    }

    bool operator==(mint &a) {
        return v == a.v;
    }

    bool operator==(signed a) {
        return v == a;
    }

    friend bool operator==(signed a, mint &b) {
        return a == b.v;
    }

    bool operator!=(mint &a) {
        return v != a.v;
    }

    bool operator!=(signed a) {
        return v != a;
    }

    friend bool operator!=(signed a, mint &b) {
        return a != b.v;
    }

    operator int() { return v; }
};

mint com(ll n, ll r) {
    if (n < r || n < 0 || r < 0)return 0;
    if (fac[0] == 0)setMod();
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

ll u(ll a) {
    return a < 0 ? 0 : a;
}

int N, A[1010], B[1010];
mint dp[1010][1010];

signed main() {
    MOD = 998244353;
    setMod();
    cin >> N;
    rep(i, N)cin >> A[i];
    rep(i, N)B[A[i]]++;
    dp[N + 1][0] = 1;
    rer(i, N + 2, 1)rep(j, N + 1) {
            if (dp[i + 1][j] == 0)continue;
            mint prec = dp[i + 1][j];
            int r = j + B[i];
            for (int k = 0; r - i * k >= 0; ++k) {
                dp[i][r - i * k] += prec * finv[k];
                prec *= com(r - i * k, i);
            }
        }
    cout << dp[1][0] << endl;
    return 0;
}