BZOJ3198[Sdoi2013]spring

本文主要是介绍BZOJ3198[Sdoi2013]spring，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

懒惰的人不想复制题面了~
给出n（n<10 0000）个六元组，再给出一个k
求有多少对六元组中有恰好k个相同（对应的位置相同）

Sample Input

5 8 2
1 2 5 8
2 5 9 9
5 1 6 2
5 1 1 8
1 2 8 7
2 5 4 9
1 2 1 1
1 4 2 1

Sample Output

13 19

---

Solution

显然，我们可以枚举哪几位相同，然后使用hash判断相同的个数。
同时，因为要求的是恰好k个相同，所以要减去k+1个相同，加上k+2个相同……
而且，因为一对有n个相同的六元组，对答案贡献会是$C_{n}^{k}$ 倍的，所以要乘上去。
我就是因为c[0][0]没有赋初值，调了超级久，然后被大佬一眼看出（%ymw），惨兮兮(╥╯^╰╥)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<bitset>
using namespace std;#define N 150010
#define P1 1000007
#define P2 998244353
#define LL long longbitset<6> b;int hash[N][3],last[P1],next[N],t[N],a[N][6];
LL ans[7],c[10][10];
int n,m,tot,cnt;int find(int num)
{int x=0;for (int i=0;i<=5;i++)
    if (b[i]==1) x=((LL)x*233+(LL)a[num][i])%P1;int y=0;for (int i=0;i<=5;i++)if (b[i]==1) y=((LL)y*1221+(LL)a[num][i])%P2;for (int i=last[x];i!=0;i=next[i])if (hash[i][1]==y) {hash[i][2]++; return i;}if (last[x]==0) t[++tot]=x;next[++cnt]=last[x];last[x]=cnt;hash[cnt][2]=1;hash[cnt][0]=x; hash[cnt][1]=y;return cnt;
}int main()
{memset(hash,0,sizeof(hash));memset(last,0,sizeof(last));scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)for (int j=0;j<=5;j++)scanf("%d",&a[i][j]);c[1][1]=1; c[1][0]=c[0][0]=1;for (int i=2;i<=6;i++){c[i][0]=1;for (int j=1;j<=i;j++)c[i][j]=c[i-1][j]+c[i-1][j-1];}for (int ii=0;ii<=(1<<6)-1;ii++){b=ii;int s=b.count();if (s<m) continue;for (int l=1;l<=n;l++){int pos=find(l);int t=hash[pos][2];ans[s]+=t-1;}for (int l=1;l<=tot;l++)last[t[l]]=0;tot=0; cnt=0;}LL ss=0;for (int i=m;i<=6;i++)if ((i-m)%2==0) ss+=ans[i]*c[i][m];else ss-=ans[i]*c[i][m];printf("%lld\n",ss);return 0;
}

这篇关于BZOJ3198[Sdoi2013]spring的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---