[LOJ 2026] [JLOI2016]成绩比较

Posted on | In , | Views:

题目链接

LOJ 2026

做法

非常自然的就想到dp，以$f_{i,j}$表示前$i$门课，目前碾压了$j$人的方案数。
枚举我这门课的分数$a$，前$i-1$门中有$k$个人被碾压。
$u_i$表示这门课的最高分，$r_i$表示B神这门课的排名。
转移如下

实际上就是强行钦定j个人的分数仍然小于等于我，k-j个人的分数都大于我。
分数小于等于我的实际人数为$n-r_i$个，已经钦定了$j$个，所以还剩$n-r_i-j$个在除了k个被钦定过的人之外选。后面这个求和就是计算有不同分数的方案数。
以上做法可以获得40分。
主要原始是在$u_i$大的时候枚举的复杂度无法接受。
发现后面一个求和显然是个关于$u_i$的n次函数(由于有求和，所以再加一次)，我们用拉格朗日插值就可以在$O(n)$的时间复杂度内计算出。
预处理快速幂，时间复杂度$O(n^4)$
LOJ太快了，不预处理快速幂都能过

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (105)
using namespace std;
int n,m,op;
int f[N][N],a[N],rnk[N],C[N][N],y[N],w[N],mi[N][N]; 
const int P=1000000007;
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
int ksm(int a,int b){
    int ret=1;
    for (;b;b>>=1,a=1ll*a*a%P) if (b&1) ret=1ll*ret*a%P;
    return ret;
}
inline int Inc(int a,int b){
    return (a+b>=P)?(a+b-P):(a+b);
} 
int main(){
    read(n),read(m),read(op);
    for (int i=1;i<=m;i++) read(a[i]);
    for (int i=1;i<=m;i++) read(rnk[i]);
    C[0][0]=1;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=i;j++) C[i][j]=Inc(C[i-1][j-1],C[i-1][j]);
        C[i][0]=1;
    }
    f[0][n-1]=1;
    for (int i=0;i<=n;i++){
        for (int j=0;j<=n;j++) mi[i][j]=ksm(i,j);
    }
    for (int i=1;i<=m;i++){
        for (int j=0;j<=n-rnk[i];j++){
            for (int x=0;x<=n;x++){
                y[x]=0;
                for (int num=1;num<=x;num++) y[x]=Inc(y[x],1ll*mi[x-num][rnk[i]-1]*mi[num][n-rnk[i]]%P);
            }
            for (int x=0;x<=n;x++){
                w[x]=1;
                for (int l=0;l<=n;l++){
                    if (x!=l) w[x]=1ll*w[x]*(x-l+P)%P;
                }
                w[x]=ksm(w[x],P-2);
            }
            int l=1;
            for (int x=0;x<=n;x++) l=1ll*l*(a[i]-x+P)%P;
            int t=0;
            if (a[i]<=n){
                t=y[a[i]];
            }
            else{
                for (int x=0;x<=n;x++){
                    t=Inc(t,1ll*y[x]*w[x]%P*l%P*ksm(a[i]-x,P-2)%P);
                }
            }
            for (int k=j;k<n;k++){
                f[i][j]=Inc(f[i][j],1ll*f[i-1][k]*C[k][j]%P*t%P*C[n-1-k][n-rnk[i]-j]%P);
            }
            //printf("%d %d %d\n",i,j,f[i][j]);
        }
    }
    printf("%d",f[m][op]);
    return 0;
}