agc012d

题意：一行n个球，第i个球有颜色ci和重量wi，两个球如果同色且重量和不超过X 或 不同色且重量和不超过y 就可以交换，求最终可以得到多少不同的颜色序列

如果a,b可以交换， a,c可以交换，那么b,c可以交换。
abc->bac->bca->acb
那么可以交换的一定构成一些团，最多有一个团由不同的颜色的一些重量最小的组成。求出这个团，然后组合数

#include <bits/stdc++.h>
using namespace std;
#define N 210000
#define mod 1000000007
#define ll long long
int n,X,Y,cnt;
int c[N],w[N],a[N],pos[N],num[N],jc[N],njc[N];
vector<int>v1[N],v2[N];
int cmp(int x,int y){return v1[x][0]<v1[y][0];}
int qpow(int x,int y)
{
    int ret=1;
    while(y)
    {
        if(y&1)ret=(ll)ret*x%mod;
        x=(ll)x*x%mod;y>>=1;
    }
    return ret;
}
void init()
{
    jc[0]=njc[0]=1;
    for(int i=1;i<=n;i++)jc[i]=(ll)jc[i-1]*i%mod;
    njc[n]=qpow(jc[n],mod-2);
    for(int i=n-1;i>=1;i--)njc[i]=(ll)njc[i+1]*(i+1)%mod;
}
int C(int x,int y){return (ll)jc[x]*njc[y]%mod*njc[x-y]%mod;}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d%d",&n,&X,&Y);
    init();
    for(int i=1;i<=n;i++)
        scanf("%d%d",&c[i],&w[i]),a[++cnt]=c[i];
    sort(a+1,a+1+cnt);
    cnt=unique(a+1,a+1+cnt)-a-1;
    for(int i=1;i<=n;i++)
    {
        c[i]=lower_bound(a+1,a+1+cnt,c[i])-a;
        v1[c[i]].push_back(w[i]);
    }
    for(int i=1;i<=cnt;i++)
    {
        sort(v1[i].begin(),v1[i].end());
        pos[i]=i;
    }
    sort(pos+1,pos+1+cnt,cmp);
    for(int i=1;i<=cnt;i++)
        v2[i]=v1[pos[i]];
    num[1]=upper_bound(v2[1].begin(),v2[1].end(),X-v2[1][0])-v2[1].begin();
    if(cnt>1)num[1]=max(num[1],
    (int)(upper_bound(v2[1].begin(),v2[1].end(),Y-v2[2][0])-v2[1].begin()));

    for(int i=2;i<=cnt;i++)
    {
        num[i]=upper_bound(v2[i].begin(),v2[i].end(),X-v2[i][0])-v2[i].begin();
        num[i]=max(num[i],
        (int)(upper_bound(v2[i].begin(),v2[i].end(),Y-v2[1][0])-v2[i].begin()));
    }
    int sum=num[1],ans=1;
    for(int i=2;i<=cnt;i++)
    {
        if(v2[i][0]+v2[1][0]>Y)break;
        ans=(ll)ans*C(sum+num[i],sum)%mod;
        sum+=num[i];
    }
    printf("%d\n",ans);
    return 0;
}