- #include
- #include
- #include
- #include
- #include using namespace std;
- #defineL 6#defineU 63#defineB 233#defineP 1234567#definell long longconst intMAXK=L+2;
- const intMAXP=P+2;
- const intMAXN=666666+2;
- inta[MAXN][MAXK],Com[MAXK][MAXK],N,K,Cnt[MAXK*MAXK],q[MAXP],f[MAXP],Mark[MAXP],s;
- ll Ans;
- boolCheck(intx,inty,int t){
- for(inti=1;i<=L;i++)
- if((t&(1<<(i-1))) && a[x][i]!=a[y][i])return 0;
- return 1;
- }
- voidInsert(intt,intp,int x){
- while(Mark[t] && !Check(Mark[t],p,x)) t=(t+1)%P;
- if(!Mark[t]) q[++s]=t,Mark[t]=p;
- f[t]++;
- }
- ll CalcHash(ll x,int p){
- ll Hash=0;
- for(inti=1;i<=L;i++){
- Hash=Hash*B%P;
- if((1<<(i-1))&x) Hash=(Hash+a[p][i]+1)%P;
- }
- return Hash;
- }
- int main(){
- cin >> N >> K;
- for(inti=1;i<=N;i++)
- for(intj=1;j<=L;j++)
- scanf("%d",a[i]+j);
- Com[0][0]=1;
- for(inti=1;i<=L;i++){
- Com[i][0]=1;
- for(intj=1;j<=i;j++) Com[i][j]=Com[i-1][j-1]+Com[i-1][j];
- }
- for(inti=1;i<=U;i++) Cnt[i]=Cnt[i>>1]+(i&1);
- for(inti=0;i<=U;i++)
- if(Cnt[i]>=K){
- ll t=0,o=((Cnt[i]-K)&1)?-1:1;
- for(intj=1;j<=N;j++) Insert(CalcHash(i,j),j,i);
- for(intj=1;j<=s;j++) t+=(ll)f[q[j]]*(f[q[j]]-1)/2,f[q[j]]=Mark[q[j]]=0;
- Ans+=o*t*Com[Cnt[i]][K],s=0;
- }
- cout << Ans << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-1986101.html