[SDOI2013]泉(容斥)

佚名 5年前 (2019-04-09) 随笔 1545人围观抢沙发百度已收录

/*
容斥加上哈希

首先我们可以2 ^ 6枚举相同情况， 然后对于这些确定的位置哈希一下统计方案数
这样我们就统计出了这些不同方案的情况， 然后容斥一下就好了 

*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#define ll unsigned long long 
#define M 101010
#define mmp make_pair
using namespace std;
int read()
{
    int nm = 0, f = 1;
    char c = getchar();
    for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
    return nm * f;
}
const int mod = 100007, base = 17171;
int n, k, a[M][7], c[7][7], cnt[131];

struct Mp
{
    vector<pair<ll, int> > hs[M];
    void init()
    {
        for(int i = 0; i < mod; i++) vector<pair<ll, int> >().swap(hs[i]);
    }
    
    void insert(ll x)
    {
        int op = x % mod;
        bool f = false;
        for(int i = 0; i < hs[op].size(); i++)
        {
            if(x == hs[op][i].first)
            {
                hs[op][i].second++;
                f = true;
                break;
            }
        }
        if(!f) hs[op].push_back(mmp(x, 1));
    }
    
    ll calc()
    {
        ll ans = 0;
        for(int i = 0; i < mod; i++)
        {
            for(int j = 0; j < hs[i].size(); j++)
            {
                int x = hs[i][j].second;
                ans += 1ll * x * (x - 1) / 2;
            }
        }
        return ans;
    }
}mp;

ll work(int x)
{
    mp.init();
    for(int i = 1; i <= n; i++)
    {
        ll v = 0;
        for(int j = 1; j <= 6; j++)
        {
            v *= base;
            if(x & (1 << (j - 1))) v += a[i][j] + 1;
        }
        mp.insert(v);
    }
    return mp.calc();
}

int main()
{
    n = read(), k = read();
    for(int i = 1; i <= n; i++) for(int j = 1; j <= 6; j++) a[i][j] = read();
    c[0][0] = 1;
    for(int i = 1; i <= 6; i++)
    {
        c[i][0] = 1;
        for(int j = 1; j <= i; j++) c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
    for(int i = 1; i < 64; i++) cnt[i] = cnt[i >> 1] + (i & 1);
    long long ans = 0;
    for(int i = 0; i < 64; i++)
    {
        if(cnt[i] >= k)
        {
            long long t = work(i);
            t = t * c[cnt[i]][k];
            if((cnt[i] - k) & 1) ans -= t;
            else ans += t;
        }
    }
    cout << ans << "\n";
    return 0;
}