bzoj 3198 [Sdoi2013]spring（容斥原理+Hash）

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

HINT

【思路】

容斥原理+Hash

恰有k个元素相同的对数=至少k+1个相同*C(k+1,k) - 至少k+2个相同*C(k+2,k) + ……

枚举状态i，如果是101表示至少1和3两个相同，把n个年份关于i构造一个hash，然后放入hash中统计。这里只是关于位是1的构造hash，其他位都忽略了，所以得到的是至少有多少个相同的数目。

学了个hash表的写法，新姿势get :)

【代码】

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 typedef unsigned long long ull;

 typedef long long ll;

 const int N = ;

 const int B = ;

 namespace Hash_set

 {

     struct node {

         node* nxt;

         ull H; int v;

         node(){}

         node(node* _,ull __) :

             nxt(_),H(__),v() {}

     }*head[N],mempool[N],*C=mempool;

     int vis[N],kase;

     void init() {

         kase++; C=mempool;

     }

     int& insert(ull st) {

         int pos=st%;

         if(vis[pos]!=kase) {

             vis[pos]=kase; head[pos]=0x0;

         }

         for(node* p=head[pos];p;p=p->nxt)

             if(p->H==st) return p->v;

         head[pos]=new (C++) node(head[pos],st);

         return head[pos]->v;

     }

 }

 int n,K,a[N][],C[][];

 ll calc(int st)

 {

     using namespace Hash_set;

     ll ans=;

     init();

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

         ull hash=;

         for(int j=;j<;j++)

             if( st&(<<j) )

                 hash=(hash*B+a[i][j]);

         int& val=insert(hash);

         ans+=(val++);

     }

     return ans;

 }

 void get_C()

 {

     for(int i=;i<=;i++) {

         C[i][]=C[i][i]=;

         for(int j=;j<i;j++)

             C[i][j]=C[i-][j-]+C[i-][j];

     }

 }

 void read(int& x) {

     char c=getchar(); int f=; x=;

     while(!isdigit(c)){if(c=='-')f=-; c=getchar();}

     while(isdigit(c)) x=x*+c-'',c=getchar();

 }

 int main()

 {

     get_C();

     read(n),read(K);

     for(int i=;i<n;i++)

         for(int j=;j<;j++) read(a[i][j]);

     ll ans=;

     for(int i=;i<;i++) {

         int cnt=;

         for(int j=;j<;j++)

             if(i&(<<j)) cnt++;

         if(cnt>=K) ans+=((cnt-K)&?-:)*calc(i)*C[cnt][K];

     }

     printf("%lld",ans);

     return ;

 }

巴特西