OI Problems   关于

80 分做法：动态规划

假设我们知道所有人的获奖情况，则不妨令 金牌的选手都取最高分，铜牌的选手都取最低分。那么我们只需要枚举金牌最后一名和铜牌的第一名就可以确定奖牌分数线（此时分数线是 金牌最后一名能获得的最高分 和 铜牌第一名能获得的最低分）。

考虑动态规划，记 fi,j,kf_{i,j,k} 表示前 ii 个人中有 jj 人取得金牌，kk 人取得银牌时获奖方案数。又因为已知分数线，所以我们可以轻松地得到状态转移方程，时间复杂度 Θ(n3)\Theta(n^3)。

我们只需要 Θ(n5m2)\Theta(n^5m^2) 预处理，再 Θ(1)\Theta(1) 回答询问即可。


100 分做法：分类讨论 & 组合数

对于每一次询问（时间复杂度 Θ(q)\Theta(q)），我们同样地需要枚举金牌最后一名和铜牌的第一名（时间复杂度 Θ(n2)\Theta(n^2)）。接着容易计算出剩下的 n−2n-2 个人能否取得金牌、取得银牌以及取得铜牌，而根据这三个信息，可以将每个人都赋予一个状态，且一共有 23−1=72^3-1=7 种状态。

此时问题已经被转化为给定 77 种状态的人数以及金牌、银牌和铜牌的总数，求可能的得奖情况数。容易发现我们可以将只能取得单种奖牌的人都直接从奖牌总数中直接去掉。

接着考虑枚举 只能得金牌和银牌的 ss 人 中得到金牌的数目 xx 以及 只能得金牌和铜牌的 tt 人 中得到金牌的数目 yy（时间复杂度 Θ(n2)\Theta(n^2)），这时有 (sx)(ty)\dbinom sx\dbinom ty 种方案。

这时候因为只能取得金牌的已经被删去，所以我们可以求出 能取得金银铜的 mm 人 中取得金牌的数目，要从这 mm 人中选出 G−x−yG-x-y（其中 GG 为总金牌人数）人取得金牌，有 (mg−x−y)\dbinom m{g-x-y} 种方案。

此时我们已经确定取得金牌的人，那么剩下的人全部分配银牌和铜牌。而 只能得金牌和银牌的 ss 人 中已经有了 s−xs-x 个银牌，故我们要从剩下 n+(s−x)n+(s-x)（其中 nn 为只能得银牌和铜牌的人数）人中选出 S−(s−x)S-(s-x)（其中 SS 为总银牌人数）人作为银牌，共 (n+s−xS−s+x)\dbinom{n+s-x}{S-s+x} 种方案。

综上，我们可以求得总方案数（四个组合数相乘）。时间复杂度 Θ(n4q)\Theta(n^4q)。

  代码
// 2023.07.22

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int CAN_GET_GOLD=1<<0,
          CAN_GET_SILVER=1<<1,
          CAN_GET_BRONZE=1<<2;

int n,m,q,cnt[81][10001],maxScore[81],minScore[81];

int C[101][101];
void initC(int n){
    for(int i=0;i<=n;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
}

int main(){
    initC(100);
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++){
        minScore[i]=10000;
        for(int j=1;j<=m;j++){
            int x; scanf("%d",&x);
            cnt[i][x]=true;
            maxScore[i]=max(maxScore[i],x);
            minScore[i]=min(minScore[i],x);
        }
        for(int j=1;j<=10000;j++)
            cnt[i][j]+=cnt[i][j-1];
    }
    while(q--){
        int gold_sum,silver_sum,bronze_sum;
        scanf("%d%d%d",&gold_sum,&silver_sum,&bronze_sum);
        long long answer=0;
        gold_sum--,bronze_sum--; // 排除枚举的 i 和 j
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                // 枚举 i 作为金牌最低分，j 作为铜牌最高分
                if(i==j)continue;
                if(maxScore[i]<minScore[j]
                    ||(maxScore[i]==minScore[j]&&j>=i))continue;
                int cntStatus[1<<3]={};
                for(int k=1;k<=n;k++){
                    if(k==i||k==j)continue;
                    int status=0;
                    if(maxScore[k]>maxScore[i]
                        ||(maxScore[k]==maxScore[i]&&k>i))
                        status|=CAN_GET_GOLD;
                    if(minScore[k]<minScore[j]
                        ||(minScore[k]==minScore[j]&&k<j))
                        status|=CAN_GET_BRONZE;
                    int silver_max=maxScore[i],
                        silver_min=minScore[j];
                    if(k>i)silver_max--;
                    if(k<j)silver_min++;
                    if(cnt[k][silver_max]-cnt[k][silver_min-1]>0)
                        status|=CAN_GET_SILVER;
                    cntStatus[status]++;
                }

                int gold=gold_sum-cntStatus[CAN_GET_GOLD],
                    silver=silver_sum-cntStatus[CAN_GET_SILVER],
                    bronze=bronze_sum-cntStatus[CAN_GET_BRONZE];
                if(gold<0||silver<0||bronze<0)continue;
                int can_gold_silver=cntStatus[CAN_GET_GOLD|CAN_GET_SILVER],
                    can_gold_bronze=cntStatus[CAN_GET_GOLD|CAN_GET_BRONZE],
                    can_silver_bronze=cntStatus[CAN_GET_SILVER|CAN_GET_BRONZE],
                    can_all=cntStatus[CAN_GET_GOLD|CAN_GET_SILVER|CAN_GET_BRONZE];
                for(int x=0;x<=gold;x++){
                    // 枚举能拿金银的人拿金的数量
                    if(!(can_gold_silver-x<=silver))continue;
                    if(x>can_gold_silver)break;
                    for(int y=0;x+y<=gold;y++){
                        // 枚举能拿金铜的人拿金的数量
                        if(!(can_gold_bronze-y<=bronze))continue;
                        if(y>can_gold_bronze)break;
                        int needGold=gold-x-y,
                            needSilver=silver-(can_gold_silver-x);
                        if(needGold>can_all)continue;
                        answer+=1ll*C[can_gold_silver][x]
                            *C[can_gold_bronze][y]%mod
                            *C[can_all][needGold]%mod
                            *C[can_silver_bronze+(can_all-needGold)][needSilver]%mod;
                    }
                }
            }
        printf("%lld\n",answer%mod);
    }
    return 0;
}