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判下重。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#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); } |