题目链接:https://codeforces.ml/contest/1735/problem/D
大意是,给出n个卡片,每个卡片有k个元素,每个元素有 0 1 2三种取值。
存在三个卡片,卡片上的对应元素要么全部相等,要么全部不相等。求存在多少个这样的集合。
%3的规律,全部相等值为 0 3 6,不相等,一定为 3 的值。
存在多少个这样的集合?利用数组存储起来,这样就可以知道每个卡片存在于多少个这样的集合。
如果取 i,j,k ,那么存在相同的i,从其他的元素中取出两个就是Csi ^ 2,这里的jk看做一个,然后除以2可以这么理解。
大观上来看,这是个数论问题。每个元素存在三个不同的值 0 1 2 ,相同或互相不同的值和为 3的倍数。
存在集合数,为组合上的整体选2,因为固定1.
code:
#include<cstdio> #include<algorithm> using namespace std; const int N=1005; int n,s,a[N][25],num[N],d[3]; long long ans; inline bool check(int x,int y,int z) { for (int i=1;i<=s;i++) if ((a[x][i]+a[y][i]+a[z][i])%3) return 0; return 1; } int main() { //freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout); int i,j,k; scanf("%d%d",&n,&s); for (i=1;i<=n;++i) for (j=1;j<=s;++j) scanf("%d",&a[i][j]); for (i=1;i<=n;i++) for (j=i+1;j<=n;j++) for (k=j+1;k<=n;k++) if (check(i,j,k)) num[i]++,num[j]++,num[k]++; for(int i=1;i<=n;i++) printf("%d ",num[i]); printf("\n"); for (i=1;i<=n;i++) ans+=1LL*num[i]*(num[i]-1)/2LL; return printf("%lld",ans),0; }