codeforces 869C The Intriguing Obsession 组合数学，逆元

codeforces 869C The Intriguing Obsession

题意

在三种颜色的群岛之间建造桥梁，每一种颜色分别有a,b,c
限制条件
1 相同颜色的岛之间的距离 d >= 3

分析

1. 如果 <nobr> a−>b−>c−>a </nobr>, <nobr> d>=3 </nobr>,所以可以将问题拆分拆分成，两个群岛之间建造桥梁，使得相同颜色的岛之间 <nobr> d>=3 </nobr>

2. 假设两个群岛分别有a,b个岛屿，

   • 一个岛屿之上不会连接相同颜色的岛屿，
   • 同样不会连接两个颜色相同颜色的岛屿，
   • 桥的个数 有 0，1，2，3，… min(a,b) 种情况
   • 在每个颜色的岛屿中取出i个，连接他们
   • 于是
     <nobr> f(a,b)=∑i=0i=min(a,b)(ai)(bi)∗i ! </nobr>
3. <nobr> ans=f(a,b)∗f(b,a)∗f(a,c) </nobr>

参考代码

const int maxn = 1e5+100;
long long  inv[maxn];
long long f(long long a,long long b)
{
    long long ans = 0;
    int _min = min(a,b);
    long long tmp = 1;
    ans += 1;
    for(int i = 1; i <= _min; ++i)
    {
        tmp = tmp*(a-i+1)%mod * (b-i+1)%mod * inv[i] %mod;
        ans = (ans + tmp) % mod;
    }
    return ans;
}
int main(void)
{
    inv[1] = 1;
    for(int i = 2; i < maxn; ++i)
        inv[i] = (mod-mod/i) * inv[mod%i] % mod;
    LL a,b,c;
    cin>>a>>b>>c;
    long long ans = 1;
    ans *= f(a,b);
    ans %= mod;
    ans *= f(a,c);
    ans %= mod;
    ans *= f(b,c);
    cout<<ans%mod<<endl;
    return 0;
}