CCA的小球

题目链接：nowcoder 217043

到主站看：https://blog.csdn.net/weixin_43346722/article/details/115337248

题目大意

有 n 个球，每个球有颜色，最多两个球同一个颜色，你要把它们排成一列。
求有多少个方案满足相邻的球颜色都不同。
方案不同当且仅当某个位置两个方案摆在这里的球颜色不同。

思路

我们考虑从同一个颜色最多两个小球下手。

那对于两个同颜色的小球，就有相邻和不相邻两种。

而且我们想到看有多少个是相邻的。
但是恰好又不好搞，我们看至少有多少个相邻。

那就好弄了，先排列弄选哪 个颜色捆在一起，然后就是：
（ 是一共有多少种颜色有两个球，下同）

那我们可以想到用容斥来去重，至少零个减至少一个加至少两个……，以此类推。

那我们可以总结出完整的式子：

然后把一些东西预处理一下算这个式子就好了。

代码

#include<cstdio>
#include<algorithm>
#define ll long long
#define mo 1000000007

using namespace std;

int n, a[1000001];
int two;
ll ans, two_times[1000001], inv[1000001], fac[1000001], zf = 1;

ll ksm(ll x, ll y) {//用来算逆元的
    ll re = 1;
    while (y) {
        if (y & 1) re = (re * x) % mo;
        x = (x * x) % mo;
        y >>= 1;
    }
    return re;
}

void init() {//预处理
    two_times[0] = inv[0] = fac[0] = 1;
    for (int i = 1; i <= 1000000; i++) two_times[i] = (two_times[i - 1] * 2) % mo;
    for (int i = 1; i <= 1000000; i++) fac[i] = (fac[i - 1] * i) % mo;
    inv[1000000] = ksm(fac[1000000], mo - 2);
    for (int i = 1000000 - 1; i >= 0; i--) inv[i] = (inv[i + 1] * (i + 1)) % mo;
}

int main() {
    init();

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }

    sort(a + 1, a + n + 1); 

    for (int i = 2; i <= n; i++)
        if (a[i] == a[i - 1]) {
            two++;
        }

    for (int i = 0; i <= two; i++) {//根据式子容斥
        ans = (ans + zf * (fac[two] * inv[i] % mo * inv[two - i] % mo * fac[n - i] % mo * ksm(two_times[two - i], mo - 2)) % mo) % mo;
        if (ans < 0) ans += mo;
        zf = -zf;
    }

    printf("%lld", ans);

    return 0;
}