题解 | C题 牛客推荐系统开发之选飞行棋子

可能很多人不会搞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);
}