[JLOI2016]成绩比较

第一行包含三个正整数N,M,K，分别表示G系的同学数量（包括B神），必修课的数量和被B神碾压的同学数量。

第二行包含M个正整数，依次表示每门课的最高分U_i。

第三行包含M个正整数，依次表示B神在每门课上的排名R_i。保证1 ≤ R_i≤ N。

数据保证至少有1种情况使得B神说的话成立。N ≤ 100,M ≤ 100,U_i ≤ 10^9

C++ 解法, 执行用时: 9ms, 内存消耗: 436K, 提交时间: 2022-04-12 10:17:34

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define _for(i, a, b) for (int i = (a); i < (int)(b); ++i)
const int NN = 104, P = 1e9 + 7;
LL pow_m(LL x, int k) {  // xᵏ
  LL r = 1;
  for (x %= P; k; k >>= 1, (x *= x) %= P)
    if (k & 1) (r *= x) %= P;
  return r;
}
int C[NN][NN];
int main() {
  _for(n, 0, NN) {
    C[n][0] = C[n][n] = 1;
    _for(j, 1, n) C[n][j] = (C[n - 1][j] + C[n - 1][j - 1]) % P;
  }
  int N, M, K;
  cin >> N >> M >> K;  
  vector<int> U(M), R(M);
  vector<LL> F(N + 1), G(N + 1);
  for (int& u : U) cin >> u;
  for (int& r : R) cin >> r;
  for (int i = N - 1; i; i--) {
    F[i] = C[N - 1][i];
    _for(j, 0, M)(F[i] *= C[N - i - 1][R[j] - 1]) %= P;
    _for(j, i + 1, N)(F[i] += -F[j] * C[j][i] % P + P) %= P;
  }
  LL Ans = F[K];
  _for(i, 0, M) {
    int u = U[i], r = R[i];
    G[0] = u % P;
    for (int j = 1; j <= N; j++) {
      LL x = 1 - pow_m(u + 1, j + 1);
      _for(k, 0, j)(x += G[k] * C[j + 1][k]) %= P;
      G[j] = x * pow_m(-1 - j, P - 2) % P;
    }
    LL x = 0;
    _for(K, 0, r) {
      LL sign = (r - K - 1) & 1 ? -1 : 1;
      (x += sign * C[r - 1][K] * pow_m(u, K) % P * G[N - K - 1] % P) %= P;
    }
    (Ans *= (x + P) % P) %= P;
  }
  cout << Ans << endl;
  return 0;
}

详情