link:http://agc012.contest.atcoder.jp/tasks/agc012_d

题意:

给你n个球

每个球有一个颜色(c)和一个权值(w)

如果两个同色球的权值和<=X可以交换它们

如果两个异色球的权值和<=Y可以交换它们

问:你最多可以交换出多少种颜色排列?

例如:三个同色球,不管X,Y,w是多少答案都是1,

1<=c<=n

n<=200000

解法:

如果a和b可以交换,a和c可以交换

那么a和c也可以交换

a b c --> b a c --> c a b --> c b a

那么就好了么..

每个球,和同色的w最小值可不可以互换?

和异色的w最小值可不可以互换?

如果都不可以你就呆那边吧.......

如果可以和同色换,同色最小值和异色可不可以互换?

如果不可以也呆那边吧,这个颜色没啥意义.....

然后就是...不同颜色之间互相换....实际上就是个组合数的问题了..

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int c[200005];
int w[200005];
int min_num[200005];
int sum[200005];
const int modo=1000000007;
int fact[200005];
int anti_fact[200005];
int c_(int x,int y)
{
    return (long long)fact[x]*anti_fact[y]%modo*anti_fact[x-y]%modo;
}
int power(int x,int y)
{
    if (y==0) return 1;
    int t=power(x,y/2);
    t=(long long)t*t%modo;
    if (y%2==1) t=(long long)t*x%modo;
    return t;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,x,y;
    scanf("%d%d%d",&n,&x,&y);
    int i;
    for (i=0;i<n;i++)
    {
        min_num[i]=1099999999;
    }
    fact[0]=1;
    anti_fact[0]=1;
    for (i=1;i<=200000;i++)
    {
        fact[i]=(long long)fact[i-1]*i%modo;
        anti_fact[i]=power(fact[i],modo-2);
    }
    for (i=0;i<n;i++)
    {
        scanf("%d%d",&c[i],&w[i]);
        c[i]--;
        min_num[c[i]]=min(min_num[c[i]],w[i]);
    }
    int min1=0,min2=0;
    for (i=0;i<n;i++)
    {
        if (min_num[min1]>min_num[i])
        {
            min1=i;
        }
    }
    if (min1==0) min2=1;
    for (i=0;i<n;i++)
    {
        if (i==min1) continue;
        if (min_num[min2]>min_num[i])
        {
            min2=i;
        }
    }
    int tot=0;
    for (i=0;i<n;i++)
    {
        if (c[i]==min1)
        {
            if (w[i]+min_num[min2]<=y)
            {
                tot++;
                sum[c[i]]++;
                continue;
            }
            else if (w[i]+min_num[min1]<=x)
            {
                tot++;
                sum[c[i]]++;
                continue;
            }
        }
        else
        {
            if (w[i]+min_num[min1]<=y)
            {
                tot++;
                sum[c[i]]++;
                continue;
            }
            else if ((w[i]+min_num[c[i]]<=x)&&(min_num[c[i]]+min_num[min1]<=y))
            {
                tot++;
                sum[c[i]]++;
                continue;
            }
        }
    }
    int p=1;
    for (i=0;i<n;i++)
    {
        p=(long long)p*c_(tot,sum[i])%modo;
        tot-=sum[i];
    }
    printf("%d\n",p);
    return 0;
}