[AGC012D] Colorful Balls
只要两个球可以交换位置，那么它们必定可以改变相对顺序，而且可以传递。
Part 1
首先考虑暴力做法：每两个球之间暴力建边，然后每个连通块内的情况都是独立的，根据乘法原理即可，每个块内的方案数是 \(\dfrac{(\sum s_i)!}{\prod s_i!}\)，其中 \(s_i\) 表示第 \(i\) 种颜色的球在这个连通块中的个数。复杂度 \(O(n^2)\)。
Part 2
考虑到有很多边是冗余的，所以可以考虑优化建边。下面记所有球中重量最小的球为 \(m1\)，次小的 \(m2\)。（\(w,c\) 分别表示它们的重量与颜色）。
-
对于同种颜色的点，将其他点与这种颜色中重量最小的点连边。
-
对于不同颜色的点，只连 \(m1\) 与除 \(m1\) 的颜色外每种颜色中重量最小的点。而对于 \(m1\) 这种颜色的其他点，则考虑与 \(m2\) 连。
由 Part 1 可知，一个连通块中至少要有两种颜色才有贡献，即一种颜色无法与 \(m1\) 的颜色连边就没有贡献。
计算时可以枚举每种颜色，然后先看它们这种颜色的最轻的点 \(w_i\) 和 \(m1\) 能不能连边，如果能，看看它们内部的点能跟 \(w_i\) 连边的个数，累加起来，除掉一个数。
这样枚举的话计算的答案的点够能与 \(m1\) 间接相连，所以可以直接轻松统计答案。
#include<cstdio>
#include <cstdlib>
#include<vector>
#include<algorithm>
using namespace std;
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
const int N=200010,mod=1e9+7;
int n,w[N],X,Y,fac[N],caf[N];
vector<int>g[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
#endif
// Insert Code Here
scanf("%d%d%d",&n,&X,&Y);
fac[0]=1;
E(i, n)fac[i]=fac[i-1]*1ll*i%mod;
int bs=fac[n],res=1,p=mod-2;
while(p){
if(p&1)res=1ll*res*bs%mod;
bs=1ll*bs*bs%mod;
p>>=1;
}
caf[n]=res;
Re(i, n-1, 0)caf[i]=caf[i+1]*(i+1ll)%mod;//阶乘逆元递推公式
E(i, n){
int tc,tw;
scanf("%d%d",&tc,&tw);
if(g[tc].empty())w[tc]=tw;
else w[tc]=min(w[tc],tw);
g[tc].push_back(tw);
}//统计每组的 min
int m1=0,m2=0;
E(i, n)
if(!g[i].empty()&&(!m1||w[i]<w[m1]))m1=i;
E(i, n)
if(!g[i].empty()&&i!=m1&&(!m2||w[i]<w[m2]))m2=i;
if(!m2||w[m1]+w[m2]>Y)return puts("1"),0;//获取m1,m2，并判断如果没有 m2（只有一种颜色），w[m1]+w[m2]>Y（即不同颜色之间不能连边），那颜色序列就是唯一的了。
int res1=0,res2=1;
E(i, n){
if(g[i].empty()||w[i]+w[m1]>Y)continue;
int cnt=0;
for(int v:g[i])cnt+=v+w[m1==i?m2:m1]<=Y||w[i]+v<=X;
res1+=cnt;
res2=res2*1ll*caf[cnt]%mod;
// (res2*=1ll*caf[cnt])%=mod;//注意这样写会导致溢出，因为等价于 res2*=1ll,res2*=caf[cnt]（GPT的见解）。
}
printf("%d",1ll*fac[res1]*res2%mod);
return 0;
}