bzoj 3198 [Sdoi2013]spring

内容

Description

Input

Output

Sample Input

3 3

1 2 3 4 5 6

1 2 3 0 0 0

0 0 0 4 5 6

Sample Output

HINT

题解

容斥还是一样的，就是hash判下重。

#include <cstdio>
using namespace std;
const int N = 100010;
const int mod = 2150527;
struct edge {
int sum, next;
long long val;
}e[N];
int st[mod + 10], c[10][10], n, pw2[10], a[N][10], tot, vis[mod + 10], k, o;
long long ans;
void get_c() {
for (int i = 0; i <= 6; ++i) c[i][0] = c[i][i] = 1;
for (int i = 1; i <= 6; ++i)
for (int j = 1; j < i; ++j)
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}
long long work(int now) {
long long ans = 0, tot = 0;
for (int i = 1; i <= n; ++i) {
long long tmp = 0;
for (int j = 1; j <= 6; ++j)
if (now & pw2[j - 1])
tmp = tmp * 1000003 + a[i][j];
int p = tmp % mod, k; p < 0 ? p += mod : 1;
if (vis[p] != now) vis[p] = now, st[p] = 0;
for (k = st[p]; k; k = e[k].next)
if (e[k].val == tmp) {
ans += e[k].sum, e[k].sum++;
break;
}
if (!k) 
e[++tot].val = tmp, e[tot].sum = 1,
e[tot].next = st[p], st[p] = tot;
}
return ans;
}
main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= 6; ++j)
scanf("%d", &a[i][j]);
pw2[0] = 1; get_c();
for (int i = 1; i <= 9; ++i) pw2[i] = pw2[i - 1] << 1;
for (int i = 0; i < 64; ++i) {
int cnt = 0;
for (int j = 0; j < 6; ++j)
if (i & pw2[j]) cnt++;
if (cnt < k) continue;
long long t = work(i) * c[cnt][k];
//      o++;
//      printf("%lld\n", t);
if ((cnt - k) & 1) ans -= t;
else ans += t;
}
printf("%lld", ans);
}