HS
AFO
HS的博客
P3270 [JLOI2016]成绩比较

题目链接

洛谷

题目描述

G系共有n位同学,M门必修课。这N位同学的编号为0到N-1的整数,其中B神的编号为0号。这M门必修课编号为0到M-1的整数。一位同学在必修课上可以获得的分数是1到Ui中的一个整数。

如果在每门课上A获得的成绩均小于等于B获得的成绩,则称A被B碾压。在B神的说法中,G系共有K位同学被他碾压(不包括他自己),而其他N-K-1位同学则没有被他碾压。D神查到了B神每门必修课的排名。

这里的排名是指:如果B神某门课的排名为R,则表示有且仅有R-1位同学这门课的分数大于B神的分数,有且仅有N-R位同学这门课的分数小于等于B神(不包括他自己)。

我们需要求出全系所有同学每门必修课得分的情况数,使其既能满足B神的说法,也能符合D神查到的排名。这里两种情况不同当且仅当有任意一位同学在任意一门课上获得的分数不同。

你不需要像D神那么厉害,你只需要计算出情况数模10^9+7的余数就可以了。

输入格式

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

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

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

数据保证至少有1种情况使得B神说的话成立。

输出格式

仅一行一个正整数,表示满足条件的情况数模10^9+7的余数。

输入输出样例

输入 #1

3 2 1
2 2
1 2

输出 #1

10

说明/提示

N<=100,M<=100,Ui<=10^9

分析

考虑$DP$,设$f_{i,j}$表示考虑到第$i$门课程,已经有$j$个人无法碾压。

转移时枚举当前又有那些人无法碾压,那么有转移
$$
\sum_x f_{i+1,j+x}=\binom{n-j-1}{x}\binom{j}{r-x-1}f_{i,j} \ \times \ F(U,r)
$$

其中$F(U,r)$表示分数上限为$U$,排名为$r$的方案数。

第一个组合数表示从$n-j-1$个当前可以碾压的人中选出$x$个之后无法碾压的人。

第二个组合数表示从$j$个人中选择$r-x-1$个人,使得B神的排名为$r$。

考虑$F(U,r)$怎么求
$$
F(U,r)=\sum_x^Ux^{n-r}(U-x)^{r-1}
$$
意思是枚举B神的分数$x$,比他差的人有$n-r$个,每个人有$x$个分数可以选择,比他好的人有$r-1$个,每个人有$U-x$个分数可以选择。

由于$U$太大,直接求的话,复杂度无法承受。

观察到$x$的最高次为$n-r+r-1=n-1$,可以使用二项式定理化为连续自然数的幂之和,根据定理,前$n$个连续自然数的$k$次幂和一定能表示为关于$n$的$k+1$次多项式,那么这个多项式的次数就是$n-1+1=n$次,之后就直接上拉格朗日插值就可以求了(如果想看具体的化简步骤,请移步洛谷题解,各位巨佬写的很详细)。

似乎将$U$看作自变量也行?如果错了请不要打我。

一些对我而言的坑

  • 组合数打错了。
  • 插点少插了几个。
  • 快速幂写错了。
  • 拉格朗日插值写在循环,导致复杂度直接变成了$O(n^5)$。

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 110
const int p=1e9+7;
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
    read(b...);
}
int n,m,K,f[maxn][maxn],g[maxn],r[maxn],U[maxn],inv[maxn],C[maxn][maxn];
int add(int x,int y)
{
    x+=y;
    return x>=p? x-p:x;
}
int mul(int x,int y)
{
    return 1ll*x*y%p;
}
int fpow(int x,int y)
{
    if(x==0)
        return y==0;
    int res=1;
    while(y)
    {
        if(y&1)
            res=mul(res,x);
        x=mul(x,x);
        y>>=1;
    }
    return res;
}
int Lagrange(int x)
{
    int ans=0;
    for(int i=1;i<=n+1;i++)
    {
        int res=g[i];
        for(int j=1;j<i;j++)
            res=mul(res,mul(x-j,inv[i-j]));
        for(int j=i+1;j<=n+1;j++)
            res=mul(res,mul(x-j,inv[j-i]));
        if((n-i+1)&1)
            res=p-res;
        ans=add(ans,res);
    }
    return ans;
}
int Get(int r,int lim)
{
    if(lim<=n+1)
    {
        for(int i=1;i<=lim;i++)
            g[i]=add(g[i-1],mul(fpow(i,n-r),fpow(lim-i,r-1)));
        return g[lim];
    }
    for(int i=1;i<=n+1;i++)
        g[i]=add(g[i-1],mul(fpow(i,n-r),fpow(lim-i,r-1)));
    return Lagrange(lim);
}
int main()
{
    read(n,m,K);
    for(int i=1;i<=m;i++)
        read(U[i]);
    for(int i=1;i<=m;i++)
        read(r[i]);
    inv[0]=inv[1]=1;
    for(int i=2;i<=n;i++)
        inv[i]=mul(p-p/i,inv[p%i]);
    C[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        C[i][0]=1;
        for(int j=1;j<=n;j++)
            C[i][j]=add(C[i-1][j],C[i-1][j-1]);
    }
    f[0][0]=1;
    for(int i=0;i<m;i++)
    {
        int t=Get(r[i+1],U[i+1]);
        for(int j=0;j<=n-K-1;j++)
        {
            if(!f[i][j])
                continue;
            int o=mul(t,f[i][j]);
            for(int x=max(0,r[i+1]-j-1);j+x<=n-K-1&&x<r[i+1];x++)
                f[i+1][j+x]=add(f[i+1][j+x],mul(mul(C[n-j-1][x],C[j][r[i+1]-x-1]),o));
        }
    }
    printf("%d\n",f[m][n-K-1]);
    return 0;
}

Gluttony

文章作者

发表评论

textsms
account_circle
email

HS的博客

P3270 [JLOI2016]成绩比较
拉格朗日插值+DP
扫描二维码继续阅读
2020-01-09