← Real problems

shoi16p3

unratedStatement on DMOJ

CP Lang

25 lineschecks
// SDOI 2016 "Grade Comparison": n students, m courses with score caps and
// B's rank in each; count score tables where B beats exactly k students in
// every course. The score count of a course is a degree-n polynomial in its
// cap, so it is interpolated from its values at 0..=n + 1.
use std.poly.{lagrange_at}

type Z = Mod<1e9 + 7>
let (n, m, k) = read<(1..=100, 1..=100, 0..=99)>()
domain Course = [m]
let cap = read<[Course]1..=1e9>()
let rank = read<[Course]1..=n>()
let comb = Comb<Z>(n)

fn scores(c: Course) -> Z:
    let (above, below) = (n - rank[c], rank[c] - 1)
    let ys = [(1..=u).sum(of: s => Z(s) ** above * Z(u - s) ** below) for u in 0..=n + 1]
    lagrange_at(ys, Z(cap[c]))

var beaten = [0..n] j => Z(Int(j == k))
for c in Course.rev:
    let below = n - rank[c]
    let ways = scores(c)
    beaten = [0..n] j => ways * (0..=below).sum(of: t =>
        beaten[t] * comb.choose(j, t) * comb.choose(n - 1 - j, below - t))
print(beaten[n - 1])

Accepted C++

267 lines · 0.08 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

struct mint {
    static constexpr int MOD = 1e9 + 7;

    static constexpr int norm(long x) {
        x %= MOD;
        if (x < 0) {
            x += MOD;
        }
        return int(x);
    }

    static constexpr mint pow(mint base, long exp) {
        mint ans = 1;
        while (exp) {
            if (exp & 1) {
                ans *= base;
            }
            base *= base;
            exp >>= 1;
        }
        return ans;
    }

    static constexpr mint inv(mint base) {
        return pow(base, MOD - 2);
    }

    int x;

    constexpr mint() : x(0) {}
    constexpr mint(long x) : x(norm(x)) {}
    constexpr mint(int x, bool) : x(x) {}

    friend ostream& operator<<(ostream& out, const mint& m) {
        return out << m.x;
    }

    mint operator-() const {
        if (!x) {
            return 0;
        }
        return mint(MOD - x, true);
    }

    mint& operator+=(const mint& m) {
        x += m.x;
        if (x >= MOD) {
            x -= MOD;
        }
        return *this;
    }
    mint& operator-=(const mint& m) {
        return *this += -m;
    }

    mint& operator*=(const mint& m) {
        x = int(long(x) * m.x % MOD);
        return *this;
    }
    mint& operator/=(const mint& m) {
        return *this *= inv(m);
    }

    friend mint operator+(mint a, const mint& b) {
        return a += b;
    }
    friend mint operator-(mint a, const mint& b) {
        return a -= b;
    }
    friend mint operator*(mint a, const mint& b) {
        return a *= b;
    }
    friend mint operator/(mint a, const mint& b) {
        return a /= b;
    }
};

struct M {
    static constexpr int maxn = 1e4 + 5;

    mint fact[maxn], ifact[maxn];

    M() {
        fact[0] = ifact[0] = 1;
        for (int i = 1; i < maxn; i++) {
            fact[i] = i * fact[i - 1];
            ifact[i] = mint::inv(fact[i]);
        }
    }

    mint choose(int n, int k) const {
        return fact[n] * ifact[k] * ifact[n - k];
    }

    mint choose1(int n, int k) const {
        if (k < 0 || k > n) {
            return 0;
        }
        return choose(n, k);
    }
} M;

struct Poly {
    vector<mint> v;

    mint operator()(mint x) const {
        mint ans = 0, base = 1;
        for (auto& a : v) {
            ans += a * base;
            base *= x;
        }
        return ans;
    }

    friend Poly operator*(mint m, const Poly& p) {
        vector<mint> ans = p.v;
        for (auto& a : ans) {
            a *= m;
        }
        return {ans};
    }

    Poly& operator+=(const Poly& p) {
        if (sz(v) < sz(p.v)) {
            v.resize(sz(p.v));
        }
        for (int i = 0; i < sz(p.v); i++) {
            v[i] += p.v[i];
        }
        return *this;
    }
    Poly& operator-=(const Poly& p) {
        return *this += -1 * p;
    }

    Poly& operator*=(const Poly& p) {
        int n = sz(v), m = sz(p.v);
        vector<mint> ans(n + m - 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ans[i + j] += v[i] * p.v[j];
            }
        }
        v = ans;
        return *this;
    }

    friend Poly operator+(Poly a, const Poly& b) {
        return a += b;
    }
    friend Poly operator-(Poly a, const Poly& b) {
        return a -= b;
    }
    friend Poly operator*(Poly a, const Poly& b) {
        return a *= b;
    }

    static Poly c_const(mint x) {
        return {{x}};
    }

    static Poly c_linear(mint m, mint b) {
        return {{b, m}};
    }
};

struct P {
    static constexpr int maxn = 105;

    Poly ans[maxn];

    P() {
        ans[0] = Poly::c_linear(1, 0);
        Poly cpref = Poly::c_linear(1, 0);
        for (int i = 1; i < maxn; i++) {
            ans[i] = mint(1) / (i + 1) * cpref * Poly::c_linear(1, 1);
            for (int j = 0; j < i; j++) {
                ans[i] -= cpref.v[j] * ans[j];
            }
            cpref *= Poly::c_linear(1, -i);
        }
    }

    mint eval(int p, int n) {
        return ans[p](n);
    }
} P;

// # of ways to place the given rank when scores are 1..=u
mint solve1(int m, int u, int rank) {
    int above = rank - 1, below = m - rank;
    mint ans = 0;
    for (int i = 0; i <= above; i++) {
        ans += M.choose(above, i) * mint::pow(u, above - i) * mint::pow(-1, i) *
               P.eval(below + i, u);
    }
    //    for (int i = 1; i <= u; i++) {
    //        ans += mint::pow(i, below) * mint::pow(u - i, above);
    //    }
    return ans;
}

void solve() {
    int n, m, kv;
    cin >> m >> n >> kv;
    int arr[n];
    for (auto& a : arr) {
        cin >> a;
    }
    int ranks[n];
    for (auto& a : ranks) {
        cin >> a;
    }
    mint dp[n + 1][m] {};
    dp[n][kv] = 1;
    for (int i = n - 1; i >= 0; i--) {
        int rank = ranks[i], u = arr[i], below = m - rank;
        mint ways = solve1(m, u, rank);
        dbg(rank, below, ways);
        for (int j = 0; j < m; j++) {
            for (int k = 0; k <= below; k++) {
                dp[i][j] += dp[i + 1][k] * ways * M.choose1(j, k) *
                            M.choose1(m - j - 1, below - k);
            }
            dbg(i, j, dp[i][j]);
        }
    }
    cout << dp[0][m - 1] << endl;
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}