Submission #42748337

---

Source Code Expand

/*+Rainybunny+*/

#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)
#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)

const int MAXN = 500, MOD = 998244353;
int n, a[MAXN + 5], bino[MAXN + 5][MAXN + 5], fac[MAXN + 5], ifac[MAXN + 5];
int f[2][MAXN + 5][MAXN + 5];

inline int mul(const int u, const int v) { return 1ll * u * v % MOD; }
inline void subeq(int& u, const int v) { (u -= v) < 0 && (u += MOD); }
inline int sub(int u, const int v) { return (u -= v) < 0 ? u + MOD : u; }
inline void addeq(int& u, const int v) { (u += v) >= MOD && (u -= MOD); }
inline int add(int u, const int v) { return (u += v) < MOD ? u : u - MOD; }
inline int mpow(int u, int v) {
    int ret = 1;
    for (; v; u = mul(u, u), v >>= 1) ret = mul(ret, v & 1 ? u : 1);
    return ret;
}

inline void init() {
    fac[0] = 1;
    rep (i, 1, n) fac[i] = mul(i, fac[i - 1]);
    ifac[n] = mpow(fac[n], MOD - 2);
    per (i, n - 1, 0) ifac[i] = mul(i + 1, ifac[i + 1]);
    rep (i, 0, n) {
        bino[i][0] = 1;
        rep (j, 1, i) bino[i][j] = add(bino[i - 1][j - 1], bino[i - 1][j]);
    }
}

int main() {
    scanf("%d", &n), init();
    rep (i, 1, n) scanf("%d", &a[i]);
    std::sort(a + 1, a + n + 1, std::greater<int>());

    int cnt = 0;
    f[~n & 1][0][0] = 1;
    per (i, n, 1) {
        auto fcur = f[i & 1], flas = f[~i & 1];
        while (cnt < n && a[cnt + 1] >= i) ++cnt;
        rep (j, 0, cnt) { // value chosen
            rep (k, 0, cnt) if (int& cur = flas[j][k]) { // place chosen
                int dj = 0, dk = 0, inv = 1;
                do {
                    addeq(fcur[j + dj][k + dk], mul(mul(cur,
                    mul(bino[cnt - j][dj], bino[cnt - k][dk])),
                    mul(fac[dk], inv)));
                    ++dj, dk += i, inv = mul(inv, ifac[i]);
                } while (j + dj <= cnt && k + dk <= cnt);
                cur = 0;
            }
        }
    }

    int ans = 0;
    rep (i, 1, n) addeq(ans, f[1][i][n]);
    printf("%d\n", ans);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:35:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   35 |     scanf("%d", &n), init();
      |     ~~~~~^~~~~~~~~~
./Main.cpp:36:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   36 |     rep (i, 1, n) scanf("%d", &a[i]);
      |                   ~~~~~^~~~~~~~~~~~~

Judge Result