P3270 [JLOI2016] 成绩比较

· · 题解

或许更好的阅读体验。

题意：

王哥班上有 n 个人，m 门课，每位同学在第 i 门课上的分数是 [1, U_i] 之间的一个整数。已知王哥每门课的排名，第 i 门课的排名为 R_i。

其中排名的定义为：有且仅有 R_i - 1 位同学这门课的分数大于王哥的分数，有且仅有 n - R_i 位同学这门课的分数小于等于王哥（不包括他自己）。

此外，还知道恰好有 k 位同学每门课成绩都小于等于王哥的成绩（称这 k 位同学被王哥碾压），求合法的得分情况的方案数 \bmod (10^9 + 7)。

其中 n, m \leq 100，U_i \leq 10^9。

思路：

思路比较顺，首先想到先选 k 个同学被王哥碾压，方案数为 \binom{n - 1}{k}。

然后考虑其它 n - k - 1 个同学，其在每门课中与王哥排名的相对大小，因为需要存在至少一门课使得其排名比王哥高，容易想到这个式子：

\prod_{i = 1}^m \binom{n - k - 1}{R_i - 1}

即在剩下的同学中，对于每个科目都选 R_i - 1 人排在王哥前面；但是这样会出现一个人在每个科目都没有选的情况，会多算一些情况，于是考虑容斥。

设集合 A_i 表示第 i 个人在每个科目都没有选的情况集合，我们要算 |\overline{A_1} \cap \cdots \overline{A_{n - k - 1}}|，容斥后我们相当于要算钦定某 j 个人都不选的方案数，显然是 \prod\limits_{i = 1}^m \binom{n - k - j - 1}{R_i - 1}，于是可以得到式子：

\sum_{j = 0}^{n - k - 1} (-1)^j \binom{n - k - 1}{j} \prod_{i = 1}^m \binom{n - k - j - 1}{R_i - 1}

此时我们求出来的方案数是王哥每门课前面和后面的总不同集合个数，现在我们来考虑分数；对于每门课 i，尝试枚举王哥的分数 j 去计数：

LHS &=\prod_{i = 1}^m \sum_{j = 1}^{U_i} j^{n - R_i} (U_i - j)^{R_i - 1} \\ &= \prod_{i = 1}^m \sum_{j = 1}^{U_i} j^{n - R_i} \sum_{k = 0}^{R_i - 1} \binom{R_i - 1}{k} U_i^k (-j)^{R_i - k - 1} \\ &= \prod_{i = 1}^m \sum_{k = 0}^{R_i - 1} (-1)^{R_i - k - 1} \binom{R_i - 1}{k} U_i^k \sum_{j = 1}^{U_i} j^{n - k - 1} \end{aligned}

后面的是自然数幂和，可以拉格朗日插值解决。

最后将三部分相乘即可，时间复杂度为 O(mn^2)。

完整代码：

 #include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define add(x, y) ((x + y >= mod) ? (x + y - mod) : (x + y))
#define dec(x, y) ((x - y < 0) ? (x - y + mod) : (x - y))
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 105, mod = 1e9 + 7; 
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
namespace Lacha{
    const int N = 105, mod =  1e9 + 7;
    inline int qpow(int a, int b){
        int ans = 1;
        while(b){
            if(b & 1)
              ans = 1ll * ans * a % mod;
            a = 1ll * a * a % mod;
            b >>= 1; 
        }
        return ans;
    }
    inline int getf(int n, int x[], int y[], int k){
        int sum = 0;
        for(int i = 1; i <= n; ++i){
            int a = 1, b = 1;
            for(int j = 1; j <= n; ++j){
                if(i == j)
                  continue;
                a = 1ll * (k - x[j] + mod) % mod * a % mod;
                b = 1ll * (x[i] - x[j] + mod) % mod * b % mod;
            }
            sum = (sum + 1ll * y[i] * a % mod * qpow(b, mod - 2) % mod) % mod; 
        }
        return sum;
    }
    int pre[N], suf[N], fac[N], ifac[N];
    inline void init(int n){
        fac[0] = fac[1] = 1;
        for(int i = 2; i <= n; ++i)
          fac[i] = 1ll * i * fac[i - 1] % mod;
        ifac[n] = qpow(fac[n], mod - 2);
        for(int i = n - 1; i >= 0; --i)
          ifac[i] = 1ll * (i + 1) * ifac[i + 1] % mod;
    }
    inline int getf(int n, int k){
       pre[0] = 1;
       for(int i = 1; i <= n; ++i)
         pre[i] = 1ll * (k - i + mod) % mod * pre[i - 1] % mod;
       suf[n + 1] = 1;
       for(int i = n; i >= 0; --i)
         suf[i] = 1ll * (k - i + mod) % mod * suf[i + 1] % mod;
       int ans = 0, now = 0;
        for(int i = 1; i <= n; ++i){
            now = (now + qpow(i, n - 2)) % mod;
           int sum = 1ll * pre[i - 1] * suf[i + 1] % mod * ifac[i - 1] % mod * ifac[n - i] % mod * now % mod;
           if((n - i) & 1)
             ans = (ans - sum + mod) % mod;
           else
             ans = (ans + sum) % mod;
       }
       return ans;
    }
};
int n, m, k, s1, s2;
int u[N], r[N];
inline int binom(int n, int m){
    if(n < m)
      return 0;
    return 1ll * Lacha::fac[n] * Lacha::ifac[m] % mod * Lacha::ifac[n - m] % mod;
}
bool End;
int main(){
    n = read(), m = read(), k = read();
    Lacha::init(n);
    for(int i = 1; i <= m; ++i)
      u[i] = read();
    for(int i = 1; i <= m; ++i)
      r[i] = read();
    for(int j = 0; j <= n - k - 1; ++j){
        int sum = binom(n - k - 1, j);
        for(int i = 1; i <= m; ++i)
          sum = 1ll * sum * binom(n - k - j - 1, r[i] - 1) % mod;
        if(j & 1)
          s1 = (s1 - sum + mod) % mod;
        else
          s1 = (s1 + sum) % mod;
    }
    s2 = 1;
    for(int i = 1; i <= m; ++i){
        int sum = 0;
        for(int k = 0; k <= r[i] - 1; ++k){
            int s = 1ll * binom(r[i] - 1, k) * Lacha::qpow(u[i], k) % mod * Lacha::getf(n - k + 1, u[i]) % mod;
            if((r[i] - k - 1) & 1)
              sum = (sum - s + mod) % mod;
            else
              sum = (sum + s) % mod;
        }
        s2 = 1ll * s2 * sum % mod;
    }
    write(1ll * s1 * s2 % mod * binom(n - 1, k) % mod);
    //cerr << '\n' << abs(&Begin - &End) / 1048576 << "MB";
    return 0;
}