首页 > 题解 > bzoj 3198 [Sdoi2013]spring

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

2

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);
}