题目大概是这个样子的:
给定 n 和长度为 n 的序列 x 和 y,需要求出满足条件的 i,j,k(1≤i,j,k≤n)(i=j=k) 的个数满足 i,j,k 的 x 和 y 至少有一个不同。
现在有了一个容斥思路,但是没有具体的容斥方案。求助。
为了更好的理解题意,放上暴力代码:
#include<bits/stdc++.h>
#define MAXN 200002
using namespace std;
int x[MAXN],y[MAXN];
inline bool unsame(int i,int j,int k){
return x[i]!=x[j]&&x[j]!=x[k]&&x[k]!=x[i]||y[i]!=y[j]&&y[j]!=y[k]&&y[k]!=y[i];
}
int main(){
freopen("problem.in","r",stdin);
freopen("problem.out","w",stdout);
int t;
scanf("%d",&t);
while(t--){
int n,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d %d",&x[i],&y[i]);
}
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
for(int k=j+1;k<=n;++k){
if(unsame(i,j,k)){
++ans;
}
}
}
}
printf("%d\n",ans);
}
return 0;
}