AT2364 Colorful Balls

DP 思维

题面

$n$个球排成一排，第$i$个球有颜色$c_i$和重量$w_i$。
每次可以选择两个颜色相同，且重量之和不超过$X$的球，交换他们的位置。
每次可以选择两个颜色不同，且重量之和不超过$Y$的球，交换他们的位置。
可以得到多少种不同的颜色序列？

• $n,c_i,w_i\leq2*10^5$

解析

首先应该有个想法。
如果两球之间可以交换，那么就在它们间连一条边。
那么一个联通块中所有球都可以互换位置。

然后答案是能换位置的球的总数的阶乘，除以其中同颜色的个数的阶乘。
但是这样复杂度是$O(n^2)$的。

优化连边关系。
一个球能换位置的条件是：

• 与同色重量最小球的重量和小于等于$X$
• 与异色重量最小球的重量和小于等于$Y$

本来第二条还要讨论下同色重量最小球和异色重量最小球和必须小于等于$Y$。但因为有了前提，在这里是没有必要的。

显然，一种颜色中，满足二条件之一的球一定构成一个前缀。
这样就很好算答案了。

注意一下一种颜色所有球都不能换位置的情况。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
#define re register
#define il inline
#define pb push_back
#define fp(i,a,b) for(re int i=a;i<=b;++i)
#define fq(i,a,b) for(re int i=a;i>=b;--i)
using namespace std;
const int N=2e5+100,mod=1e9+7;
int n,x,X,Y,mn[N],mn1=mod,mn2=mod,ans=1,inv[N],tot;
vector<int>V[N];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) x=x*10+ch-48,ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=gi();X=gi();Y=gi();
  inv[0]=inv[1]=1;
  fp(i,1,n) x=gi(),V[x].pb(gi());
  fp(i,2,n) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
  fp(i,2,n) inv[i]=1ll*inv[i]*inv[i-1]%mod;
  fp(i,1,n)
    if(V[i].size())
      {
    sort(V[i].begin(),V[i].end());
        mn2=min(mn2,mn[i]=V[i][0]);
    if(mn2<mn1) swap(mn1,mn2);
      }
    else mn[i]=mod;
  fp(i,1,n)
    {
      re int mm=(mn[i]==mn1?mn2:mn1),sz=V[i].size();
      while(sz>1&&V[i][sz-1]+mm>Y&&V[i][sz-1]+mn[i]>X) --sz;
      if(mm+mn[i]<=Y) ans=1ll*ans*inv[sz]%mod,tot+=sz;
    }
  fp(i,1,tot) ans=1ll*ans*i%mod;
  printf("%d\n",ans);
  return 0;
}