╰(￣▽￣)╭

济南市“泉历史研究小组”依据济南特有的泉脉关系将济南的泉水分为六个区域，分别是市中区、历下区、天桥区、槐荫区、历城区、长清区。

作为光荣的济南泉历史研究小组中的一员，铭铭收集了历史上N 个不同年份时不同泉区的泉水流量指数，这个指数是一个小于2^30 的非负整数。第i 个年份时六个泉区的泉水流量指数分别为A(i,1)，A(i,2)，A(i,3)，A(i,4)，A(i,5)与A(i,6)。

现在铭铭希望知道有多少对不同的年份：i 和j，满足这两年恰好有K 个泉区的泉水流量指数对应相同。

对于100%的数据，N<=100000，A<=2^30

0<=K<=6，且所有数据中K 是等概率出现的，即对于任意的0<=x<=6，都有大约1/7 的数据中K=x。

(⊙ ▽ ⊙)

首先计算出f[i]，其中i∈[0,26)：

例如f[0110012]表示，满足第2、3、6位相同的年份有多少对。

这个可以通过Hash，O(6∗n)求出。

考虑容斥原理，

设g[k]表示，当题目所给的K=k时的答案。

对于所有的f[i]，设num为i中1的个数（选了多少位相同）。

g[k]+=f[i]∗Cknum∗(−1)num−k (k∈[0,num])

答案即为g[K]。

(￣～￣)

#include<iostream>

#include<algorithm>

#include<stdio.h>

#include<math.h>

#include<string.h>

#define ll long long

using namespace std;

const char* fin="ex3295.in";

const char* fout="ex3295.out";

const ll inf=0x7fffffff;

const ll maxn=100007,maxh=9999997,maxH=7394895,hh=137,HH=37;

ll n,m,i,j,k;

ll a[maxn][6],bz[6],c[10][10],f[7];

ll id;

struct node{

    ll y,z,cnt;

    bool ok(){

        return z==id;

    }

}h[maxh];

ll hash(ll v,ll v1){

    ll k=v%maxh,l=0;

    while (h[k].ok() && h[k].y!=v1){

        k=(k+1)%maxh;

    }

    return k;

}

void dfs(ll l,ll num){

    ll i,j,k;

    if (l==6){

        ll ans=0;

        id++;

        for (i=1;i<=n;i++){

            ll tmp=0,tmd=0;

            for (j=0;j<6;j++)

                if (bz[j]){

                    tmp=(tmp*hh+(a[i][j]%maxh))%maxh;

                    tmd=(tmd*HH+(a[i][j]%maxH))%maxH;

                }

            k=hash(tmp,tmd);

            if (h[k].z<id){

                h[k].cnt=0;

                h[k].z=id;

            }

            h[k].y=tmd;

            ans+=h[k].cnt;

            h[k].cnt++;

        }

        for (i=num;i>=0;i--) f[i]+=c[num][i]*ans*((num-i)%2?-1:1);

        return;

    }

    bz[l]=1;

    dfs(l+1,num+1);

    bz[l]=0;

    dfs(l+1,num);

}

int main(){

    scanf("%lld%lld",&n,&m);

    for (i=0;i<10;i++){

        c[i][0]=1;

        for (j=1;j<=i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1];

    }

    for (i=1;i<=n;i++) for (j=0;j<6;j++) scanf("%lld",&a[i][j]);

    dfs(0,0);

    printf("%lld",f[m]);

    return 0;

}

(⊙v⊙)

1.hh要取质数，并且尽量浮夸一点。

2.看到恰好二字，就可以考虑容斥原理。