一个渐进意义下 的做法。

  • 代表集合 。

问题转化

考虑一个平凡的转化：考虑去计算所有不合法的方案数。

一个方案不合法当且仅当存在四元组中存在两个位置上的元素相等。

令 为所有位置 上的元素和位置 上的元素相等的四元组构成的集合。

那么我们只需要求出以下式子的值即可：

固定的分类讨论

考虑固定 。

的情况：

因为容斥系数为 所以直接枚举 的所有大小为 的子集即可。

的情况：

考虑 ， 按 分类讨论。

若 ,如果不考虑容斥系数直接枚举 的所有大小为 的子集即可。

考虑以下这里的容斥系数：对于任意一种 的大小为 的子集，考虑固定一个大小为 的子集，共 种方法，再钦定一个 共 种方法，因此容斥系数为 。

若 ，那么一定有 。

那么直接枚举 大小为 的子集再去处理子集的方案数相乘即可。

的情况：

考虑 ，按 分类讨论。

若 ，考虑其容斥系数，对于 的任意一种个大小为 的子集，其一定唯一对应一组唯一的 ，因此容斥系数即 ，同理枚举子集乘上即可。

若 ，其容斥系数的计算也是平凡的 ，简单处理即可。

的情况：

对于 ，其集族内包括的集合的指标并的大小一定是 ，因此其容斥系数一定是组合数，简单处理即可。

代码

#include <bits/stdc++.h>

#define int long long

int c[4][5005],n,s[4];

inline int count(int x){
    int res = 0;
    for (;x;x>>=1) 
        if (x&1) res++;
    return res;
}

inline int get(int state){
    int res = 0;
    for (int i = 1; i <= n; i++){
        bool ck = true;
        for (int j = 0; j < 4; j++)
                if (state >> j & 1 && c[j][i] == 0) ck = false;
        if (!ck) continue;
        res++;
    }
    return res;
}

inline int solve(int state){
    int res = 1; res *= get(state);
    for (int i = 0; i < 4; i++){
        if (state >> i & 1) continue;
        res *= s[i];
    }
    return res;
}

signed main(){
    std::cin >> n;
    for (int i = 0; i < 4; i++){
        char str[5005]; std::cin >> str;
        for (int j = 0; j < n; j++) c[i][j+1] = str[j] == '1' ? 1 : 0;
    }
    for (int i = 0; i < 4; i++)
        for (int j = 1; j <= n; j++) s[i] += c[i][j];
    int res = 0; int aa = 1;
    for (int i = 0; i < 4; i++) aa *= s[i];
    res += aa; int s1 = 0;
    for (int i = 0; i < 1 << 4; i++){
        if (count(i) != 2) continue;
        res -= solve(i);
    }

    for (int i = 0; i < 1 << 4; i++){
        if (count(i) != 3) continue;
        res += solve(i) * 2;
    }

    int sum = 0;
    for (int i = 0; i < 1 << 4; i++){
        if (count(i) != 2) continue;
        int newstate = 0;
        for (int j = 0; j < 4; j++)
                if (!(i >> j & 1)) newstate += 1 << j;
        sum += get(newstate) * get(i);
    }
    res += sum / 2;
    int ss = 0,s2 = 0;
    for (int i = 0; i < 1 << 4; i++) ss += 1 << i;
    res -= 6 * solve(ss);
    std::cout << res;
    return 0;
}