[??记录]AT2364 [AGC012D] Colorful Balls
command_block
2021-02-28 19:35:48
**题意** ： $n$ 个球排成一排，第 $i$ 个球有颜色 $c_i$ 和重量 $w_i$。
可以执行下列两种操作 ：
- 选择两个颜色相同，且重量之和不超过 $x$ 的球，交换他们的位置。
- 选择两个颜色不同，且重量之和不超过 $y$ 的球，交换他们的位置。
求可以得到多少种不同的**颜色**序列。答案对 $10^9+7$ 取模。
$n\leq 2\times 10^5,\ w,x,y\leq 10^9$ ，时限$\texttt{2s}$。
------------
对于两个能够交换的球，连一条无向边。
对于一个联通块内的球，可以随便交换顺序，最终方案数即为颜色的多重排列。
这能得到一个显然的 $O(n^2)$ 做法。
考虑简化连边。
考虑最终形成联通块的形态，不难发现是一个大多色块和若干（没有贡献）的单色块。
（若有两个多色块，则必然能合成一个）
大多色块是由若干颜色的（按重量排序的）前缀组成的。
于是，最轻的球一定在大多色块中。
对于同色的球，只需要考虑最轻的球连出的边。
对于异色球，只需要考虑全局最轻的球连出的边，以及全局最轻球所在颜色能连出的最容易的边（即除掉这个颜色后的最轻球）。
这样，所需的边就是 $O(n)$ 的了。
适当地思考性质可以简化代码实现。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 200500
using namespace std;
const int mod=1000000007;
ll powM(ll a,int t=mod-2){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
ll fac[MaxN],ifac[MaxN];
void Init(int n)
{
fac[0]=1;
for (int i=1;i<=n;i++)
fac[i]=fac[i-1]*i%mod;
ifac[n]=powM(fac[n]);
for (int i=n;i;i--)
ifac[i-1]=ifac[i]*i%mod;
}
int n,X,Y,c[MaxN],w[MaxN],pc[MaxN],o[MaxN];
int main()
{
scanf("%d%d%d",&n,&X,&Y);
Init(n);
w[0]=mod;
for (int i=1;i<=n;i++){
scanf("%d%d",&c[i],&w[i]);
if (w[pc[c[i]]]>w[i])pc[c[i]]=i;
}
int p1=0,p2=0;
for (int i=1;i<=n;i++){
if (w[pc[i]]<w[p1]){
p2=p1;p1=pc[i];
}else if (w[pc[i]]<w[p2])
p2=pc[i];
}
if (w[p1]+w[p2]>Y){puts("1");return 0;}
//不同颜色之间无边，则方案数为 1
int m=0;
for (int i=1;i<=n;i++)
if (w[c[i]==c[p1] ? p2 : p1]+w[i]<=Y
||(w[i]+w[pc[c[i]]]<=X&&w[pc[c[i]]]+w[p1]<=Y))
{m++;o[c[i]]++;}
//否则，任意有向外出边的球都在大多色块中
ll ans=fac[m];
for (int i=1;i<=n;i++)
ans=ans*ifac[o[i]]%mod;
printf("%lld",ans);
return 0;
}
```