容斥是 ans= 至少 k 位置相等对数 C(k,k)- 至少 k+1 位置相等对数 C(k+1,k)+ 至少 k+2 位置相等对数 * C(k+2,k) ......
然后对数的话 2^6 枚举状态然后用 hash 表统计即可
至于为什么要乘上一个组合数, 详见 https://www.cnblogs.com/candy99/p/6616809.html
我理解的是, 因为是枚举状态统计, 所以会重复计算 C(k+i,k) 次
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- using namespace std;
- const int N=100005,mod=2150527;
- int n,m,a[N][10],h[N*30],vis[N*30],c[10][10];
- struct qwe
- {
- int ne,to,sm;
- long long va;
- }e[N*30];
- long long clc(int s)
- {
- long long ans=0,cnt=0;
- for(int i=1;i<=n;i++)
- {
- long long tmp=0;
- int j,k;
- for(j=1;j<=6;j++)
- if(s&(1<<(j-1)))
- tmp=tmp*1000003+a[i][j];
- j=(tmp%mod+mod)%mod;
- if(vis[j]!=s)
- {
- vis[j]=s;
- h[j]=0;
- }
- for(k=h[j];k;k=e[k].ne)
- if(e[k].va==tmp)
- {
- ans+=e[k].sm;
- e[k].sm++;
- break;
- }
- if(!k)
- {
- cnt++;
- e[cnt].va=tmp;
- e[cnt].sm=1;
- e[cnt].ne=h[j];
- h[j]=cnt;
- }
- }
- return ans;
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)
- for(int j=1;j<=6;j++)
- scanf("%d",&a[i][j]);
- c[0][0]=1;
- for(int i=1;i<=6;i++)
- {
- c[i][0]=1;
- for(int j=1;j<=i;j++)
- c[i][j]=c[i-1][j-1]+c[i-1][j];
- }
- long long ans=0;
- for(int i=0;i<64;i++)
- {
- int cnt=0;
- for(int j=0;j<6;j++)
- if(i&(1<<j))
- cnt++;
- if(cnt<m)
- continue;
- ans+=(((cnt-m)&1)?-1:1)*clc(i)*c[cnt][m];
- }
- printf("%lld\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2761797.html