数据包洛谷自建题目

题目

题目描述

小 Z 毕业后去了 H 中学教书，他带的班级有 $n$ 个学生，对于每个学生 $i$ 可以用一个正整数 $A_i$ 来衡量其学习能力（$i=1,2,3,\cdots,n$）。有一天，小 Z 捡到了 $k$ 本神奇教材，如果给一个学生学习了这本教材，他的学习能力就会变成原来的 $t$ 倍。小 Z 决定将这本书随机且等概率地发放给班上的 $n$ 个同学，每个学生最多只能得到一本书，也就是说班上会有 $k$ 名同学被分配到书，学习能力变成 $t$ 倍，而剩下 $n-k$ 名同学没有书，学习能力不变。现在小 Z 想知道，在所有的分配方案中，对于班上的每个同学来说排名保持不变的情况分别有多少种。

在这里，排名是指学习能力比他高的人的数目加 $1$，比方说有 $5$ 个同学，学习能力为 $\langle3,2,2,1,1\rangle$，他们的排名即 $\langle1,2,2,4,4\rangle$。

输入格式

第一行输入 $3$ 个整数 $n,k,t$，分别代表学生的数目、神奇教材的数目以及学习能力翻的倍数。第二行输入 $n$ 个整数，代表每个学生的学习能力，编号从 $1$ 到 $n$。

输出格式

输出 $n$ 行，第 $i$ 行输出一个整数代表第 $i$ 位同学在 Z 老师发完书后学习能力排名保持不变的所有可能的情况数目。由于这些数可能非常大，请输出其对 $10^9+7$ 取模后的结果。

输入输出样例

输入 #1

4 2 2
1 2 3 4

输出 #1

说明/提示

对于 $10\%$ 的数据，有 $1\leq n\leq10$。

对于 $30\%$ 的数据，有 $1\leq n\leq10^3$。

对于另外 $10\%$ 的数据，有 $1\leq n\leq10^5$ 且 $k=1$。

对于 $100\%$ 的数据，有 $1\leq k\leq n\leq10^5,2\leq t\leq10^3,1\leq A_i\leq10^9$。

rankSample.zip

题解

设一个人的 $A$ 值为 $i$，考虑其答案。

记 $\vert >i\vert$ 表示所有 $A$ 值大于 $i$ 的人的个数。同理，有 $\vert \leq i\vert,\cdots$。

记 $\left\vert[l,r]\right\vert=\vert\geq l\vert-\vert\geq r+1\vert$ 表示所有 $A$ 值在 $[l,r]$ 中的人的个数。

分两类讨论：

$i$ 不会翻倍。

因为其排名不变，$A$ 值大于 $i$ 的人翻倍显然不影响，这一部分人的数量为 $\vert>i\vert$。

而对于 $\left\vert\leq\dfrac{i}{t}\right\vert$ 这一部分的人，其翻倍后的 $A$ 值仍然小于等于 $i$，不影响 $i$ 的排名。

从这两部分的人中选择 $k$ 个即可，此部分答案为：
\[\begin{pmatrix} \vert>i\vert+\left\vert\leq\dfrac it\right\vert\\ k \end{pmatrix}\]
$i$ 会翻倍。

则 $i$ 的 $A$ 值会从 $i$ 变为 $ti$，则 $\vert[i+1,ti]\vert$ 这一部分的人必须都要翻倍，这样才能保证 $i$ 的排名不变。

记 $pl=\vert[i+1,ti]\vert+1$ 表示必须翻倍的人数。

则只有当 $pl\leq k$ 的时候，才符合题意。
- 对于 $\vert>ti\vert$ 这一部分人，随便翻倍都不影响 $i$ 的排名。
- 对于 $\vert\leq i\vert-1$ 这一部分人，翻倍依然不影响 $i$ 的排名，因为其翻倍后小于等于 $ti$。（减一是为了去除当前讨论的 $i$，可能会存在多个 $A$ 值相等。）
此部分的答案为：
\[\binom{\vert>ti\vert+\vert\leq i\vert-1}{k-pl}\]

对于诸如 $\vert>i\vert$ 的求法，只需要排序后二分即可。

AC 代码

//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=1e5,P=1e9+7;
struct student{
	int a,id,ans;
}a[N+1];
int n,k,t,fact[N+1];
void C_pre(int n){
	fact[0]=1;
	for(int i=1;i<=n;i++){
		fact[i]=1ll*fact[i-1]*i%P;
	}
}
int qpow(int a,int n){
	int base=a,ans=1;
	while(n){
		if(n&1){
			ans=1ll*ans*base%P;
		}
		base=1ll*base*base%P;
		n>>=1;
	}
	return ans;
}
int C(int n,int m){
	if(n<m||m<0||n<0){
		return 0;
	}
	return 1ll*fact[n]*qpow(1ll*fact[m]*fact[n-m]%P,P-2)%P;
}
//≤x的数量 
int leq(ll x){
	int l=1,r=n+1;
	while(l<r){
		int mid=l+r>>1;
		if(a[mid].a>x){
			l=mid+1;
		}else{
			r=mid;
		}
	}
	return n-r+1;
}
//≥x的数量
int geq(ll x){
	return n-leq(x-1);
} 
int main(){
	/*freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);*/
	
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>n>>k>>t;
	C_pre(n);
	for(int i=1;i<=n;i++){
		cin>>a[i].a;
		a[i].id=i;
	}
	//单调不增 
	sort(a+1,a+n+1,[](student a,student b){
		return a.a>b.a;
	});
	for(int i=1;i<=n;i++){
		a[i].ans=C(geq(a[i].a+1)+leq(a[i].a/t),k);
		int pl=leq(1ll*a[i].a*t)-leq(a[i].a)+1;
		if(pl<=k){
			a[i].ans=(a[i].ans + C(geq(1ll*a[i].a*t+1)+leq(a[i].a)-1,k-pl))%P;
		}
	}
	sort(a+1,a+n+1,[](student a,student b){
		return a.id<b.id;
	});
	for(int i=1;i<=n;i++){
		cout<<a[i].ans<<'\n';
	}
	
	cout.flush();
	
	/*fclose(stdin);
	fclose(stdout);*/
	return 0;
}

题解：成绩排名

题目见正文

题目