首页 > 代码库 > BZOJ3198 SDOI2013 spring HASH+容斥原理

BZOJ3198 SDOI2013 spring HASH+容斥原理

2024-09-09 07:16:47   218人阅读

题意：给定6个长度为n的数列，求有多少个数对(i,j)（(i,j)≡(j,i)）使得i和j位置恰好有K个数相同，其中0≤K≤6

题解：

设fi=至少有K个数相同的位置对的数量，用2^6枚举每一种可能，根据容斥原理，答案就是\[\sum\limits_{i = K}^N {{f_i}C_i^K{{\left( { - 1} \right)}^{i - K}}} \]

至于多乘一个组合数，是因为当前枚举到有x个数相同，一个位置对有i个相同的数，那么累计的时候就会算成$C_x^i$，因此实际上这个位置对对答案的贡献为$\sum\limits_{j = K}^i {C_i^jC_j^K} $

技术分享
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define L 6#define U 63#define B 233#define P 1234567#define ll long longconst int MAXK=L+2;const int MAXP=P+2;const int MAXN=666666+2;int a[MAXN][MAXK],Com[MAXK][MAXK],N,K,Cnt[MAXK*MAXK],q[MAXP],f[MAXP],Mark[MAXP],s;ll Ans;bool Check(int x,int y,int t){    for(int i=1;i<=L;i++)        if((t&(1<<(i-1))) && a[x][i]!=a[y][i]) return 0;    return 1;}void Insert(int t,int p,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(int i=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(int i=1;i<=N;i++)        for(int j=1;j<=L;j++)            scanf("%d",a[i]+j);    Com[0][0]=1;    for(int i=1;i<=L;i++){        Com[i][0]=1;        for(int j=1;j<=i;j++) Com[i][j]=Com[i-1][j-1]+Com[i-1][j];    }    for(int i=1;i<=U;i++) Cnt[i]=Cnt[i>>1]+(i&1);    for(int i=0;i<=U;i++)        if(Cnt[i]>=K){            ll t=0,o=((Cnt[i]-K)&1)?-1:1;            for(int j=1;j<=N;j++) Insert(CalcHash(i,j),j,i);            for(int j=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;}
View Code

 

BZOJ3198 SDOI2013 spring HASH+容斥原理


联系
我们