[AT2364] [agc012_d] Colorful Balls

题目链接

AtCoder：https://agc012.contest.atcoder.jp/tasks/agc012_d

洛谷：https://www.luogu.org/problemnew/show/AT2364

Solution

首先很容易得到一个(O(n^2))的做法：

两个可以( m swap)的点连边，那么答案就是联通块大小的阶乘之积除以颜色相同的阶乘之积。

注意到如果按题目给出的条件，那么这些点一定会连成一个不同色的大块和零散的对答案无贡献的同色小块。

如果从小到大排一边序那么一定是前面一堆在加后面一些和前面有关的点。

那么我们直接开( m vector​)排序然后算答案就好了。

#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}

#define lf double
#define ll long long
#define pb push_back
#define iter vector<int > :: iterator 

const int maxn = 2e5+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int add(int x,int y) {return x+y>mod?x+y-mod:x+y;}
int del(int x,int y) {return x-y<0?x-y+mod:x-y;}
int mul(int x,int y) {return 1ll*x*y-1ll*x*y/mod*mod;}

int n,x,y,mn[maxn],fac[maxn],ifac[maxn],inv[maxn],mn1=1e9,mn2=1e9;
vector<int > v[maxn];

int main() {
    read(n),read(y),read(x);
    fac[0]=ifac[0]=inv[0]=inv[1]=1;
    for(int i=2;i<=n;i++) inv[i]=mul(mod-mod/i,inv[mod%i]);
    for(int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);
    for(int i=1;i<=n;i++) ifac[i]=mul(ifac[i-1],inv[i]);
    for(int i=1,a,b;i<=n;i++) read(a),read(b),v[a].pb(b);
    for(int i=1;i<=n;i++)
	if(v[i].size()) {
	    sort(v[i].begin(),v[i].end()),mn[i]=*v[i].begin();
	    mn2=min(mn2,mn[i]);
	    if(mn2<mn1) swap(mn1,mn2);
	}
    int ans=1,tot=0;
    for(int i=1;i<=n;i++) {
	if(!v[i].size()) continue;
	iter it=v[i].end();it--;int p,mm=mn[i]==mn1?mn2:mn1;
	if(it==v[i].begin()) {tot+=v[i][0]+mm<=x;continue;}
	while((*it)+mm>x&&(*it)+mn[i]>y) {it--;if(it==v[i].begin()) break;}
	if(mm+mn[i]<=x) p=it-v[i].begin()+1,tot+=p,ans=mul(ans,ifac[p]);
    }
    write(mul(ans,fac[tot]));
    return 0;
}