noip2019集训测试赛(二十一)Problem A: Colorful Balls
程序员文章站
2022-07-01 23:30:34
Problem A: Colorful Balls Description Snuke放了N个一排彩色的球.从左起第i个球的颜色是ci重量是wi她可以通过执行两种操作对这些球重新排序操作1:选择两个相同颜色的球,假如他们的重量和小于等于X,交换两个球的位置操作2:选择两个不同颜色的球,假如他们的重量 ......
problem a: colorful balls
description
snuke放了n个一排彩色的球.从左起第i个球的颜色是ci重量是wi
她可以通过执行两种操作对这些球重新排序
操作1:选择两个相同颜色的球,假如他们的重量和小于等于x,交换两个球的位置
操作2:选择两个不同颜色的球,假如他们的重量和小于等于y,交换两个球的位置
求我们总共可以得到多少种 不同的颜色序列?对答案取109+7的模
她可以通过执行两种操作对这些球重新排序
操作1:选择两个相同颜色的球,假如他们的重量和小于等于x,交换两个球的位置
操作2:选择两个不同颜色的球,假如他们的重量和小于等于y,交换两个球的位置
求我们总共可以得到多少种 不同的颜色序列?对答案取109+7的模
input
n x y
c1 w1
.
c1 w1
.
.
.
cn wn
cn wn
output
输出答案。
sample input
sample input 1: 4 7 3 3 2 4 3 2 1 4 4 sample input 2: 1 1 1 1 1 sample input 3: 21 77 68 16 73 16 99 19 66 2 87 2 16 7 17 10 36 10 68 2 38 10 74 13 55 21 21 3 7 12 41 13 88 18 6 2 12 13 87 1 9 2 27 13 15
sample output
sample output 1: 2 sample output 2: 1 sample output 3: 129729600
hint
1≤n≤2×105
1≤x,y≤109
1≤ci≤n
1≤wi≤109
分析
首先,如果球a可以和球b交换,球b也可以和球c交换,那么肯定可以通过球b将球a与球c交换。
所以只需要将可以交换的任意两个球之间连一条边,找出每个联通块中每种球颜色的个数,因为每个联通块内无论怎么排都行,所以就能用组合数求出当前那个联通块中合法排列的方案数,最后再将所有的联通块的方案数乘起来就能得到答案了。
但这种方法的时间复杂度是o(n2)的。
但我们可以设:
球a是全部球中重量最小的球。
球b是全部球中与球a不同色且重量最小的球。
若找不出球b,则只有一种颜色的球,故只有1种方案
若球a与球b不在同一个联通块内,则不可能出现两种不同颜色的球在同一个联通块内,故只有1种方案
而对于每一个球来说,如果它既不能连到球a,也不能连到球b,那么它不可能再连到其他异色的球。
所以只可能有1个联通块对答案做出贡献。
所以我们只需要求出所有可以连到球a或球b或连到一个与它同色且能连到球a或球b的球即可。
时间复杂度为o(n)
o(n)的时间求组合数详见欧拉定理
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct data{ long long x,y; }t[300001]; long long n,s1,s2,k1,k2,f[300001],k[300001],m=1000000007,s[300001],cnt,id[300001],sum,ans=1,col[300001],colmax[300001]; bool d[300001],r[300001]; bool cmp(data a,data b){ return a.y<b.y; } long long get_pow(long long a,long long b){ long long p=1; while(b){ if(b%2)p=(p*a)%m; a=(a*a)%m; b=b/2; } return p; } long long c(long long a,long long b){ return (((k[a]*f[b])%m)*f[a-b])%m; } void add(long long a){ long long p=a; while(t[col[p]].y+t[a].y<=s1){ if(!col[p])break; s[t[a].x]++; sum++; p=col[p]; r[p]=1; } } int main(){ scanf("%lld%lld%lld",&n,&s1,&s2); k[0]=1; for(long long i=1;i<=n;i++)k[i]=(k[i-1]*i)%m; f[n]=get_pow(k[n],m-2); for(long long i=n-1;i>1;i--)f[i]=(f[i+1]*(i+1))%m; f[0]=1; f[1]=1; for(long long i=1;i<=n;i++)scanf("%lld%lld",&t[i].x,&t[i].y); sort(t+1,t+n+1,cmp); for(long long i=1;i<=n;i++){ col[colmax[t[i].x]]=i; colmax[t[i].x]=i; } k1=1; k2=2; while(k2<=n&&t[k2].x==t[k1].x)k2++; if(k2!=n+1){ if(t[k1].y+t[k2].y<=s2){ for(long long i=1;i<=n;i++){ if((t[i].x!=t[k1].x&&t[k1].y+t[i].y<=s2)||(t[i].x!=t[k2].x&&t[k2].y+t[i].y<=s2)){ if(!d[t[i].x]){ d[t[i].x]=1; r[i]=1; cnt++; id[cnt]=t[i].x; s[t[i].x]++; sum++; add(i); }else if(!r[i]){ s[t[i].x]++; r[i]=1; sum++; } } } for(long long i=1;i<=cnt;i++){ ans=(ans*c(sum,s[id[i]]))%m; sum=sum-s[id[i]]; } } } printf("%lld\n",ans); }