https://www.hackerrank.com/contests/hourrank-15/challenges/taras-beautiful-permutations
题意是说，给定一个数组，里面的数字最多出现两次，求所有的合法排列，合法排列定义为没有相同的数字排在一起。
首先先统计一下个数为2的数字的个数。
用all表示。
然后先不理题目要求，总排列数是A(n, n) / (2! * 2! * 2! .... * 2!)，就是(2!)^all
下面蹦一波容斥。
暴力枚举i表示有i对东西是放在一起的，就是违反了规矩的，
然后这i对和身下的n - 2 * i个东西组合一起的情况有A(n - 2 * i + i) / (2!)^(all - i)种情况，容斥即可。
奇减偶加
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int MOD = 1e9 + ;
LL quick_pow(LL a, LL b, LL MOD) { //求解 a^b%MOD的值
LL base = a % MOD;
LL ans = ; //相乘，所以这里是1
while (b) {
if (b & ) {
ans = (ans * base) % MOD; //如果这里是很大的数据，就要用quick_mul
}
base = (base * base) % MOD; //notice。注意这里,每次的base是自己base倍
b >>= ;
}
return ans;
} LL C(LL n, LL m, LL MOD) {
if (n < m) return ; //防止sb地在循环，在lucas的时候
if (n == m) return ;
LL ans1 = ;
LL ans2 = ;
LL mx = max(n - m, m); //这个也是必要的。能约就约最大的那个
LL mi = n - mx;
for (int i = ; i <= mi; ++i) {
ans1 = ans1 * (mx + i) %MOD;
ans2 = ans2 * i % MOD;
}
return (ans1 * quick_pow(ans2, MOD - , MOD) % MOD); //这里放到最后进行,不然会很慢
}
const int maxn = + ;
int a[maxn];
map<int, int>book;
LL A(int n, int has, int MOD) {
LL ans1 = ;
LL ans2 = ;
for (int i = ; i <= n; ++i) {
ans1 = ans1 * i % MOD;
}
for (int i = ; i <= has; ++i) {
ans2 = ans2 * % MOD;
}
return (ans1 * quick_pow(ans2, MOD - , MOD) % MOD);
}
void work() {
book.clear();
int n;
scanf("%d", &n);
for (int i = ; i <= n; ++i) {
scanf("%d", &a[i]);
book[a[i]]++;
}
int all = ;
for (map<int, int> :: iterator it = book.begin(); it != book.end(); it++) {
if (it->second == ) {
all++;
}
}
// cout << all << endl;
LL ans = A(n, all, MOD);
if (all == ) {
cout << ans << endl;
return;
}
// cout << ans << endl;
for (int i = ; i <= all; ++i) {
if (i & ) {
ans = (ans + MOD - C(all, i, MOD) * A(n - i, all - i, MOD) % MOD) % MOD;
} else {
ans = (ans + C(all, i, MOD) * A(n - i, all - i, MOD) % MOD) % MOD;
}
}
cout << ans << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}