可能很多人不会搞k阶的容斥,但C题可以偷鸡用5000×5000次循环混过去
思路:一共四个人,即4阶的容斥,但如果枚举前两个人的选择,前两个人的选择已经固定了,那只用处理后两个人,用这两个人的可选方案相乘,再减去第三人和第四人有几个位置数字相同(即可能选重复的)即一层容斥就可以了。
#include<stdio.h> char q[5][5005]; int n,count; int vis[5005]; int vis2[5005]; int vis3[5005]; int main() { scanf("%d",&n); for(int i=0;i<4;i++) { scanf("%s",q[i]); } long long count2=0,count3=0,chong=0; for(int i=0;i<n;i++) { if(q[2][i]=='1') vis2[i]=1,count2++; if(q[3][i]=='1') vis3[i]=1,count3++; if(q[2][i]=='1'&&q[3][i]=='1') { vis[i]=1; chong++; } } long long sum=0; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(i!=j&&q[0][i]=='1'&&q[1][j]=='1') { long long t1=count2,t2=count3; if(vis2[i]) t1--; if(vis2[j]) t1--; if(vis3[i]) t2--; if(vis3[j]) t2--; long long t3=chong; if(vis[i]) t3--; if(vis[j]) t3--; sum+=t1*t2-t3; } } } printf("%lld\n",sum); }