题解 P3298 【[SDOI2013]泉】

# 哈希&&容斥 因为题目里面的 恰好有K个泉区的泉水流S指数对应相同 恰好两字暗示我们此题需要用容斥原理来做 ## 思路~~（参考网上部分博客）~~ 由于先处理再哈希会TLE，所以这里我们直接先处理出状态然后再拿一个哈希搞一搞 关于容斥原理 （~~不会的自行百度~~），其实就是我们计算出大于等于k个的组别，然后再减去k+1，再加上k+2……这样一直下去，然后再拿个组合数搞一搞就出来了 ``` #include<bits/stdc++.h> #define ll long long using namespace std; const int N=100010,mod1=233,mod2=1e7+33; int n,m,cnt,a[N][7],c[7][7],head[mod2+10],to[N],nxt[N]; ll ans,sm[N]; inline int read() { int x=0; char c=getchar(); bool flag=0; while(c<'0'||c>'9') {if(c=='-')flag=1;c=getchar();} while(c>='0'&&c<='9'){x=(x+(x<<2)<<1)+ c-'0';c=getchar();} return flag?-x:x; } inline bool check(int x,int y,int k) { for(int i=1;i<=6;++i) if (k&(1<<(i-1)) && a[x][i]!=a[y][i]) return 0; return 1; } inline ll calc(int k) { ll res=0,cnt=0,p; memset(head,0,sizeof(head)); for(int i=1;i<=n;++i) { ll x=0; for(int j=1;j<=6;++j) if (k&(1<<(j-1))) x=(x*mod1+a[i][j])%mod2; for (p=head[x];p;p=nxt[p]) if(check(to[p],i,k)) {res+=sm[p]++;break;} if (!p) to[++cnt]=i,sm[cnt]=1,nxt[cnt]=head[x],head[x]=cnt; } return res; } int main() { n=read(),m=read(); for(int i=1;i<=n;++i) for(int j=1;j<=6;++j) a[i][j]=read(); c[0][0]=1; for(int i=1;i<=6;++i){c[i][0]=1;for(int j=1;j<=6;++j) c[i][j]=c[i-1][j-1]+c[i-1][j]; } for(int S=0;S<=63;++S) { int cnt=0; for(int i=0;i<=5;++i) if(S&(1<<i)) cnt++; if(cnt<m) continue; ll t=calc(S)*c[cnt][m]; ans+=(cnt-m)&1?-t:t; } printf("%lld\n",ans); } ``` 另外，这题有一个神奇的坑点，就是关于mod2 ~~为什么我用19260817就会T6个点啊~~ ~~一定是这题不允许膜蛤~~