AtCoder：Colorful Balls（思维 & 数论）

D - Colorful Balls

Time limit : 2sec / Memory limit : 256MB

N X Y
c1 w1
:
cN wN

4 7 3
3 2
4 3
2 1
4 4

2

1 1 1
1 1

1

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 v
3 7
12 41
13 88
18 6
2 12
13 87
1 9
2 27
13 15

129729600

思路：对于不同颜色的三个球a,b,c，如果a和b能换，b和c能换，那么a和c一定能换，因为abc->acb->bca->cba，于是找到最小权值的球，建边，就变成有重复元素的组合数问题了，用乘法逆元可以解决。

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

typedef long long LL;
const LL mod = 1e9+7;
const int maxn = 2e5+3;

LL fac[maxn], inv[maxn];
int cnt, n, x, y, co[maxn], va[maxn], vis[maxn]={0}, ge[maxn]={0};
vector<int>v[maxn], tmp;
vector<pair<int, int> >r[maxn];
vector<pair<int, int> >p;

void dfs(int u)
{
    vis[u] = 1;
    ++cnt, ++ge[co[u]], tmp.push_back(co[u]);
    for(int i=0; i<v[u].size(); ++i)
    {
        int e = v[u][i];
        if(vis[e]) continue;
        dfs(e);
    }
}
int main()
{
    int c, w;
    scanf("%d%d%d",&n,&x,&y);
    cnt = 0;
    fac[0] = fac[1] = inv[0] = inv[1] = 1;
    for(LL i=2; i<=n; ++i)
    {
        fac[i] = fac[i-1]*i%mod;
        inv[i] = (mod-mod/i)*inv[mod%i]%mod;
    }
    for(int i=2; i<=n; ++i)
        inv[i] = inv[i-1]*inv[i]%mod;
    for(int i=1; i<=n; ++i)
    {
        scanf("%d%d",&c,&w);
        co[i] = c, va[i] = w;
        r[c].push_back(make_pair(w, i));
    }
    for(int i=1; i<=n; ++i)
    {
        if(r[i].size())
        {
            sort(r[i].begin(), r[i].end());
            p.push_back(r[i][0]);
            for(int j=1; j<r[i].size(); ++j)
                if(r[i][j].first+r[i][0].first <= x)
                    v[r[i][0].second].push_back(r[i][j].second),
                    v[r[i][j].second].push_back(r[i][0].second);
        }
    }
    sort(p.begin(), p.end());
    if(p.size())//用权值最小的球为中介建图。
    {
        int id = p[0].second;
        for(int i=1; i<=n; ++i)
        {
            if(co[i]==co[id] || va[i]+va[id]>y) continue;
            v[id].push_back(i), v[i].push_back(id);
        }
    }
    if(p.size()>1)//该颜色的其他球也要考虑进去。
    {
        int id = p[1].second, imin = co[p[0].second];
        for(auto it = r[imin].begin(); it!=r[imin].end(); ++it)
            if(it->first + va[id]<=y)
                v[it->second].push_back(id), v[id].push_back(it->second);
    }
    dfs(p[0].second);
    LL ans = fac[cnt];
    for(int i=0; i<tmp.size(); ++i)
    {
        int num = ge[tmp[i]];
        ans = (ans*inv[num])%mod;
        ge[tmp[i]] = 0;
    }
    printf("%lldn",ans);
    return 0;
}

最后

以上就是现实纸鹤为你收集整理的AtCoder：Colorful Balls（思维 & 数论）的全部内容，希望文章能够帮你解决AtCoder：Colorful Balls（思维 & 数论）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。