AT2364 Colorful Balls

题意翻译

N个球排成一排，第i个球有颜色ci和重量wi。 Snuke每次可以选择两个颜色相同，且重量之和不超过X的球，交换他们的位置。 Snuke每次可以选择两个颜色不同，且重量之和不超过Y的球，交换他们的位置。问，可以得到多少种不同的颜色序列？答案取膜1000000007

输入输出样例

输入样例#1：

输出样例#1：

输入样例#2：

1 1 1
1 1

输出样例#2：

输入样例#3：

输出样例#3：

129729600

sol：较容易的，可以发现如果a和b可以交换，b和c可以交换，那么a和c一定可以交换。

于是可以缩成一个个连通块，把每个连通块中的方案数乘起来就是答案了。对于每个块，令块大小为B，每种颜色的个数分别为b1,b2,b3,...bn，那么答案就是B! / b1! / b2! / ... / bn!

实现恶心的一匹，我用了并查集（应该可以用别的）码量感觉挺大的，但是有些人打的超短，不知道为什么qaq（我太菜菜菜菜菜菜菜菜菜菜菜菜菜了）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0');    return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const ll Mod=1000000007;
const int N=200005;
int n,A,B;
ll Jiec[N];
int Father[N];
int Min[N],CMin[N];
int Cnt[N];
struct Record
{
    int Cor,W,Id;
}Xins[N];
inline int Get_Father(int x)
{
    return (Father[x]==x)?(x):(Father[x]=Get_Father(Father[x]));
}
inline void Merge(int x,int y)
{
    Father[Get_Father(x)]=Get_Father(y);
}
vector<int>Liantong[N];
inline ll Ksm(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y&1) ans=ans*x%Mod;
        x=x*x%Mod;
        y>>=1;
    }
    return ans;
}
int main()
{
    int i,j;
    R(n); R(A); R(B);
    Jiec[0]=1; for(i=1;i<=n;i++) Jiec[i]=1ll*Jiec[i-1]*i%Mod;
    Xins[0].W=0x3f3f3f3f;
    for(i=1;i<=n;i++)
    {
        Father[i]=i;
        R(Xins[i].Cor); R(Xins[i].W); Xins[i].Id=i;
        if(Xins[i].W<=Xins[Min[Xins[i].Cor]].W)
        {
            CMin[Xins[i].Cor]=Min[Xins[i].Cor];
            Min[Xins[i].Cor]=i;
        }
        else if(Xins[i].W<Xins[CMin[Xins[i].Cor]].W)
        {
            CMin[Xins[i].Cor]=i;
        }
    }
    int Fir=0,Sec=0;
    for(i=1;i<=n;i++)
    {
        if(Fir==0||Xins[i].W<Xins[Min[Fir]].W) {Sec=Fir; Fir=Xins[i].Cor;}
        else if(Sec==0||Xins[i].W<Xins[Min[Sec]].W) Sec=Xins[i].Cor;
    }
    for(i=1;i<=n;i++)
    {
        if(Xins[i].W+Xins[Min[Xins[i].Cor]].W<=A)
        {
            if(i!=Min[Xins[i].Cor]) Merge(i,Min[Xins[i].Cor]);
        }
        if(Xins[i].Cor==Fir)
        {
            if(Xins[i].W+Xins[Min[Sec]].W<=B) Merge(i,Min[Sec]);
        }
        else
        {
            if(Xins[i].W+Xins[Min[Fir]].W<=B) Merge(i,Min[Fir]);
        }
    }
    for(i=1;i<=n;i++) Liantong[Get_Father(i)].push_back(i);
//    for(i=1;i<=n;i++) if(Liantong[i].size())
//    {
//        for(j=0;j<Liantong[i].size();j++) W(Liantong[i][j]);
//        puts("");
//    }
    ll ans=1;
    for(i=1;i<=n;i++) if(Liantong[i].size())
    {
        for(j=0;j<Liantong[i].size();j++)
        {
            Cnt[Xins[Liantong[i][j]].Cor]++;
        }
        ll tmp=Jiec[Liantong[i].size()];
        for(j=0;j<Liantong[i].size();j++) if(Cnt[Xins[Liantong[i][j]].Cor])
        {
            tmp=1ll*tmp*Ksm(Jiec[Cnt[Xins[Liantong[i][j]].Cor]],Mod-2)%Mod;
            Cnt[Xins[Liantong[i][j]].Cor]=0;
        }
        ans=1ll*ans*tmp%Mod;
    }
    Wl(ans);
    return 0;
}
/*
input
4 7 3
3 2
4 3
2 1
4 4
output
2

input
5 99 100
5 91
2 42
3 63
3 35
4 21
output
12

input
21 77 68
16 73
16 99
19 66
2 87
2 16
7 17
10 36
10 68
2 38
10 74
13 55
21 21
3 7
12 41
13 88
18 6
2 12
13 87
1 9
2 27
13 15
output
129729600
*/

View Code