题面
题意：
给出ｎ个五元组(一个五元组的五个数互不相同)，我们称两个五元组不和谐，当且仅当任意元素都不相同，求有多少对五元组不和谐。
(Solution:)
很容易想到 Ans = 总共对数－和谐对数
而和谐对数包括５种：
- 一个数相同
- 二个数相同
- ...
- 五个数相同
所以我们就可以容斥了。
对于每次读进来的一组，我们计算它与之前读进来的和谐的个数。
于是我们就 (2^5) 枚举状态，然后 + (容斥系数) * (之前状态个数), 状态可以用map记因为状态有多个数, 所以用字符串作状态。
(Source)
#include <map>
#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <assert.h>
#include <algorithm>
using namespace std;
#define fir first
#define sec second
#define pb push_back
#define mp make_pair
#define LL long long
#define INF (0x3f3f3f3f)
#define mem(a, b) memset(a, b, sizeof (a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(x) cout << #x << " = " << x << endl
#define tralve(i, x) for (register int i = head[x]; i; i = nxt[i])
#define For(i, a, b) for (register int (i) = (a); (i) <= (b); ++ (i))
#define Forr(i, a, b) for (register int (i) = (a); (i) >= (b); -- (i))
#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define ____ debug("go
")
namespace io {
static char buf[1<<21], *pos = buf, *end = buf;
inline char getc()
{ return pos == end && (end = (pos = buf) + fread(buf, 1, 1<<21, stdin), pos == end) ? EOF : *pos ++; }
inline int rint() {
register int x = 0, f = 1;register char c;
while (!isdigit(c = getc())) if (c == '-') f = -1;
while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getc()));
return x * f;
}
inline LL rLL() {
register LL x = 0, f = 1; register char c;
while (!isdigit(c = getc())) if (c == '-') f = -1;
while (x = (x << 1ll) + (x << 3ll) + (c ^ 48), isdigit(c = getc()));
return x * f;
}
inline void rstr(char *str) {
while (isspace(*str = getc()));
while (!isspace(*++str = getc()))
if (*str == EOF) break;
*str = ' ';
}
template<typename T>
inline bool chkmin(T &x, T y) { return x > y ? (x = y, 1) : 0; }
template<typename T>
inline bool chkmax(T &x, T y) { return x < y ? (x = y, 1) : 0; }
}
const int N = 4e5 + 1;
map<string, long long> M;
LL n;
int main() {
#ifndef ONLINE_JUDGE
file("Cowpatibility");
#endif
string a[6];
cin >> n;
LL ans = n * (n - 1) / 2;
For (i, 1, n) {
For (j, 1, 5) cin >> a[j];
sort(a + 1, a + 6);
LL res = 0;
for (int s = 1; s < (1<<5); ++ s) {
string str = ""; int ou = 0;
for (int j = 1; j < 6; ++ j) {
if (s & (1 << j - 1)) {
ou ++;
str += "," + a[j];
}
}
if (ou & 1) res += M[str] ++;
else res -= M[str] ++;
}
ans -= res;
}
cout << ans << endl;
}
然后因为bitset常数过于优秀, 总复杂度(O(frac{1}{32} imes n^2)), 虽然不是正解但也能过，而且跑的飞快。
#include <bitset>
#include <tr1/unordered_map>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <assert.h>
#include <algorithm>
using namespace std;
#define fir first
#define sec second
#define pb push_back
#define mp make_pair
#define LL long long
#define INF (0x3f3f3f3f)
#define mem(a, b) memset(a, b, sizeof (a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(x) cout << #x << " = " << x << endl
#define tralve(i, x) for (register int i = head[x]; i; i = nxt[i])
#define For(i, a, b) for (register int (i) = (a); (i) <= (b); ++ (i))
#define Forr(i, a, b) for (register int (i) = (a); (i) >= (b); -- (i))
#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define ____ debug("go
")
namespace io {
static char buf[1<<21], *pos = buf, *end = buf;
inline char getc()
{ return pos == end && (end = (pos = buf) + fread(buf, 1, 1<<21, stdin), pos == end) ? EOF : *pos ++; }
inline int rint() {
register int x = 0, f = 1;register char c;
while (!isdigit(c = getc())) if (c == '-') f = -1;
while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getc()));
return x * f;
}
inline LL rLL() {
register LL x = 0, f = 1; register char c;
while (!isdigit(c = getc())) if (c == '-') f = -1;
while (x = (x << 1ll) + (x << 3ll) + (c ^ 48), isdigit(c = getc()));
return x * f;
}
inline void rstr(char *str) {
while (isspace(*str = getc()));
while (!isspace(*++str = getc()))
if (*str == EOF) break;
*str = ' ';
}
template<typename T>
inline bool chkmin(T &x, T y) { return x > y ? (x = y, 1) : 0; }
template<typename T>
inline bool chkmax(T &x, T y) { return x < y ? (x = y, 1) : 0; }
}using namespace io;
const int N = 5e4 + 1;
tr1::unordered_map<int, bitset<N> > buc;
int n, a[N][6];
int main() {
#ifndef ONLINE_JUDGE
file("Cowpatibility");
#endif
n = rint();
For (i, 1, n) {
For (j, 1, 5)
buc[ a[i][j] = rint() ].set(i);
}
bitset<N> tmp;
int ans = 0;
For (i, 1, n) {
tmp.reset();
For (j, 1, 5)
tmp |= buc[a[i][j]];
ans += n - tmp.count();
}
cout << ans / 2 << endl;
}