(Description)
(Snuke)放了(N)个一排彩色的球.从左起第(i)个球的颜色是(c_{i})重量是(w_{i})
她可以通过执行两种操作对这些球重新排序
操作(1):选择两个相同颜色的球,假如他们的重量和小于等于(X),交换两个球的位置
操作(2):选择两个不同颜色的球,假如他们的重量和小于等于(Y),交换两个球的位置
求我们总共可以得到多少种 不同的颜色序列?对答案取(10^9+7)的模
(Input)
(N) (X) (Y)
(c_{1}) (w_{1})
⋮
(c_{N}) (w_{N})
(Output)
输出答案。
(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) (1:)
2
(sample) (output) (2:)
1
(sample) (output) (3:)
129729600
(HINT)
(1≤N≤2×10^5)
(1≤X,Y≤10^9)
(1≤c_{i}≤N)
(1≤w_{i}≤10^9)
思路
因为里面的球是可以互相交换的，于是我们可以考虑最后利用排列组合来计算答案。
现在我们就要考虑什么样的情况下哪些球是可以交换的
我们考虑一个情况：如果(A)能转变到(B)，(B)能转变到(C)， 那么(A)一定能通过(B)到(C)
于是我们就可以将(A，B，C)缩在一个联通块里，最后再用组合计算答案
我们考虑：
如果球(x)不是全局最小值，那么它最优就是以全局最小值为中介进行交换
如果球(x)是全局最小值，那么它最优则是以全局次小值为中介进行交换
接着我们会有个小小的优化：
如果球(x)是可以和同色球最小值(y)互换的，那么就可以直接把同色最小值赋值给球(w[x])
我们就可以判断如果满足条件的球，就可以将它加入联通块中
最后用组合数计算就好了：(C^n_m=frac{m!}{(m-n)!n!})
我们就可以暴力处理出两个数组(fac[i],inv[i])分别表示(i!)和(frac{1}{i!})
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2*1e5+10,mod=1e9+7;;
int c[N],w[N];
int minn[N];
int numcol[N];
int cnt=0;
int n;
int fac[N],inv[N];
int poww(int x,int y)
{
int sum=1ll;
while(y)
{
if(y&1)sum=(sum*x)%mod;
x=(x*x)%mod;
y>>=1;
}
return sum;
}
void prec()
{
fac[0]=1;
for(int i=1;i<=n;i++)fac[i]=i*fac[i-1]%mod;
inv[n]=poww(fac[n],mod-2);//费马小定理
for(int i=n-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int x,int y)
{
return ((fac[y]*inv[y-x])%mod*inv[x])%mod;
}
signed main()
{
memset(minn,127,sizeof(minn));
int x,y;
scanf("%lld %lld %lld",&n,&x,&y);
for(int i=1;i<=n;i++)
{
scanf("%lld %lld",&c[i],&w[i]);
minn[c[i]]=min(minn[c[i]],w[i]);//同色最小值
}
int fir_min=0,sec_min=0;//全局最小值和全局次小值
for(int i=1;i<=n;i++)
{
if(minn[i]<minn[fir_min])
{
sec_min=fir_min;
fir_min=i;
}
else if(minn[i]<minn[sec_min])sec_min=i;
}
for(int i=1;i<=n;i++)
{
if(w[i]+minn[c[i]]<=x)w[i]=minn[c[i]];
if((c[i]==fir_min&&minn[sec_min]+w[i]<=y)||(c[i]!=fir_min&&minn[fir_min]+w[i]<=y))
{
numcol[c[i]]++;
cnt++;
}
}
//计算组合数
prec();
int ans=1;
for(int i=1;i<=n;i++)
{
if(numcol[i])
{
ans=(ans*C(numcol[i],cnt))%mod;
cnt-=numcol[i];
}
}
printf("%lld",ans);
return 0;
}