首页 > 其他分享 > [JLOI2016]成绩比较

[JLOI2016]成绩比较

时间:2023-06-25 20:33:51浏览次数:37  
标签:同学 JLOI2016 ch 分数 吊打 leq 成绩 我们 比较

题目描述

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

如果在每门课上 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\) 的余数就可以了。
\(1\leq N\leq 100\),\(1\leq M\leq 100\),\(1\leq U_i\leq 10^9\),\(1\leq R_i\leq N\)。

思路点拨

这篇题解是 \(O(n^2)\) ,没卡常直接最优解。相比于大多数题解的 \(O(n^3)\) 有绝对优势。

这道题目我们可以把答案算成三个部分。我们一个个讲:

第一部分

我们需要选出 \(k\) 个被吊打的学生,那么这个值显然是 \(C_{n}^k\) 。

第二部分

我们除了B神以外的学术的相对成绩,具体的说,就是每一个学生的成绩是在B神之上还是之下。其实这一点并不麻烦,但是烦人的是,题目要求被B神吊打的学生 恰好 只有 \(k\) 个。我们按照一般的分配方式,可能会出现多于 \(k\) 个学生被 B神吊打的情况。我们很容易想到二项式反演,这样就可以将 恰好 的问题转化为 不超过 的问题。

我们可以定义 \(f(x)\) 表示至多有 \(x\) 个学生没有被吊打的情况,那么

\[f(x)=\prod_{i=1}^m C_{x}^{r_i-1} \]

这 \(x\) 个学生没有被吊打就意味着对于每一个学科,在 \(r_i-1\) 个超过B神的位置中,一定是从 \(x\) 个学生中选择的。这样是符合我们定义的。接下来,我们可以二项式反演:

\[ans=\sum_{i=0}^{n-1-k}(-1)^{n-1-k-i}C_{n-1-k}^i f(i) \]

第三部分

我们需要给每一个学生分配分数。但是这个分数很大(怎么处理我们后面会讲到)
我们知道,对于每一个学科,成绩不超过B神的学生是有 \(n-r_i\) 个的,超过B神的学生有 \(r_i-1\) 个。这样我们恒容易知道答案就是:

\[\prod_{i=1}^{m} \sum_{j=1}^{U_i} j^{n-r_i} (U_i-j)^{r_i-1} \]

直接求会超时,并且超的很多。但是看到这种式子我们要引起警觉。 \(\sum_{i=1}^n i^k\) 一类的式子其实可以被表示为一个以 \(n\) 为自变量的 \(k+1\) 次多项式。但是这个式子比较特殊,它有两个变量。但是其中的每一个部分 \(j^{n-r_i}\) 和 \((U_i-j)^{r_i-1}\) 都是多项式表示的,那么这个式子就可以表示为这两个多项式的卷积,这显然还是一个多项式。这是一个以 \(U_i\) 为自变量的 \(n\) 次多项式,我们确定 \(n+1\) 个点就可以拉格朗日插值求出。应为我们带入的点横坐标是连续的,所以我们的插值算法可以被优化到 \(O(n)\) 。

如何获取答案

乘法原理,将三个部分的答案乘起来就可以了。这样子我们的时间复杂度就是每一个部分的时间复杂度 \(O(n+n^2+n^2)\) 。这样就可以吊打标算了。泰裤辣!

\(code\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const int MAXN=1e2+10;
const int mod=1e9+7;
int qpow(int a,int b){
	int ans=1,base=a;
	while(b){
		if(b&1) ans=ans*base%mod;
		base=base*base%mod;
		b>>=1;
	}
	return ans;
}
namespace Cmath{
	int sum[MAXN],inv[MAXN];
	void prepare(){
		sum[0]=inv[0]=1;
		for(int i=1;i<MAXN;i++){
			sum[i]=sum[i-1]*i%mod;
			inv[i]=qpow(sum[i],mod-2);
		}
	} 
	int C(int n,int m){
		if(m>n||m<0) return 0; 
		return sum[n]*inv[m]%mod*inv[n-m]%mod;
	}
	int A(int n,int m){
		return sum[n]*inv[n-m]%mod; 
	}
}
using namespace Cmath;
namespace Lagrange{
	int pre[MAXN],suc[MAXN]; 
	int lagrange(int *x,int *y,int n,int k){
		int ans=0;
		pre[0]=suc[n+1]=1;
		for(int i=1;i<=n;i++) pre[i]=pre[i-1]*(k-x[i]+mod)%mod;
		for(int i=n;i;i--) suc[i]=suc[i+1]*(k-x[i]+mod)%mod;
		for(int i=1;i<=n;i++){
			int top=pre[i-1]*suc[i+1]%mod;
			int down=sum[x[i]-x[1]]*sum[x[n]-x[i]]%mod;
			if((n-i)&1) down=(-down+mod)%mod;
			ans=(ans+top*qpow(down,mod-2)%mod*y[i])%mod;
		}
		return ans;
	}
}
using namespace Lagrange;
int n,m,k;
int U[MAXN],r[MAXN];
int x[MAXN],y[MAXN];
int fun(int p){
	int ans=1;
	for(int i=1;i<=m;i++)
		ans=ans*C(p,r[i]-1)%mod;
	return ans;
}
int run(int id){
	for(int i=1;i<=n+1;i++){
		x[i]=i;
		y[i]=(y[i-1]+qpow(i,n-r[id])*qpow(U[id]-i,r[id]-1))%mod;
	}
	return lagrange(x,y,n+1,U[id]);
}
signed main(){
	n=read(),m=read(),k=read();
	for(int i=1;i<=m;i++) U[i]=read();
	for(int i=1;i<=m;i++) r[i]=read();
	Cmath:prepare();
	int ans=0;
	for(int i=0;i<=n-k-1;i++){
		int cnt=(qpow(-1,n-k-1-i)+mod)*C(n-k-1,i)%mod*fun(i)%mod;
		ans=(ans+cnt)%mod;
	}
	ans=ans*C(n-1,k)%mod;
	for(int i=1;i<=m;i++) ans=ans*run(i)%mod;
	cout<<ans<<endl;
	return 0;
}

标签:同学,JLOI2016,ch,分数,吊打,leq,成绩,我们,比较
From: https://www.cnblogs.com/Diavolo/p/17503880.html

相关文章

  • 学生成绩系统
    学生分数系统(文章目录)前言本文介绍一个ifelse的小案例,帮助大家理解ifelse。一、学生成绩系统#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>intmain(void){ intscore; while(1) { printf("请输入学生分数\n"); scanf("%d",&score); if(score<0||......
  • python学习日志,五大容器的比较
    列表的使用:列表.append(元素):向列表中追加一个元素列表.extend(容器):将数据容器的内容依次取出,追加到列表尾部列表.insert(下标,元素):在指定下标处,插入指定的元素del列表[下标]:删除列表指定下标元素列表.pop(下标):删除列表指定下标元素列表.remove(元素):从前向后,翻除此......
  • shell脚本双中括号比较数字踩坑
    shell的双中括号中,由于可以直接使用大于和小于号,便自作聪明认为可以直接判断两个数字的大小,直到遇到了以下的情况[core@localhost~]$a=5;b=3;if[[$a>$b]];thenechoaisbigger;elseechobisbigger;fi#结果输出aisbigger,结果是正确的#但是如果两个数字不是......
  • 【web开发】PHP之字符串比较
    前言字符串的比较或者说字符串的判断是任何一门编程语言的字符串处理功能中的非常重要的特性之一。同时也是在实际开发中最常使用的字符串判断方式,在PHP中,除了可以使用比较运算符号(“==”或者<以及>)来进行比较操作,还提供了一个系列的比较函数,使得PHP可以进行更加复杂的字符串比较......
  • PTA第6-8次成绩系统分析
    PTA第6~8次题目分析前言:第6-8次的成绩系统和之前菜单系统的结构和逻辑都有很多相似的地方,包括信息第二部分的处理判断都需要建立在第一部分上,以及排序输出等。不过这次的排序输出有点新东西,要按中英文的首字母顺序排,我也是搜过之后才学会这点。这次成绩系统还存在不简单的错误提......
  • 课程成绩统计程序1-3
    课程成绩统计程序系列分析博客采取总——分模式总体分析:1.最终设计类图:2.最终设计圈复杂度:3.最终设计代码:点击查看代码importjava.util.*;importjava.text.Collator;importjava.util.TreeMap;publicclassMain{publicstaticvoidmain(String[]args)......
  • PTA6-8次题目集(成绩计算系列)总结
    1.前言6-8次作业题量不大,难度较菜单计价较小,但实现过程依旧繁琐知识点输入和输出处理:你需要从用户或文件中读取输入数据(课程信息和学生成绩),然后相应地进行处理。你可以使用诸如读取控制台输入(Scanner 类)或从文件读取技术。字符串操作和解析:你需要将输入的字符串分割后提......
  • delphi 字符串比较函数
    字符串比较函数列表方法说明大小写System.SysUtils.TStringHelper.StartsWith返回是否以给定的字符串开头。区分大小写System.SysUtils.TStringHelper.StartsText返回是否以给定的字符串开头。不区分大小写System.SysUtils.TStringHelper.EndsWith返回是否......
  • 广州app开发公司哪家比较好呢?
    广州作为中国乃至全球的科技创新中心,拥有众多优秀的科技企业和技术人才。在这个蓬勃发展的创业环境中,有许多优秀的app开发公司涌现出来。那么,在众多选择中,广州的app开发公司哪家比较好呢?以下是一些在选择时可以考虑的因素:1.专业经验和技术实力:一家优秀的APP开发公司应该具备丰富的......
  • pta-成绩管理系统分析
    一、前言(1).知识点:我觉得用到的最多的就是HashMap,包括的HashMap的基本用法还有比如怎么排序的问题,都是比较陌生的点,需要课外的补充学习。(2).难度:难度本身还可以,难度降低的原因主要是类图以及类的设计方面老师在上课时整体分析了一遍,还有一个难点是HashMap的使用,由......