P6521数学容斥

· · 题解

随机跳了一题，就跳到了这一道。

这是我在准备离开机房的时候看的，在回家路上想到的，所以写一篇题解纪念一下。

正难则反，我们难以求出不同的，求相同的好了，我们可以进行这样子的转化：D 位不同等价于 4-D 位相同。我才不会告诉你是我在车上忘记题目才想到的。

我们发现可以利用进制（75\% 的数据也在提示这一点），把一个字符串转成一个进制的数。

因为我需要一个留空的位，所以我选择了 37 进制。

把 1/2/3/4 位相同的存到桶里，接着我们就可以统计出相同位大于等于 x 的数量，我记作 mor_x。

为什么是大于等于 x 呢？因为我们发现，相同位大于等于 x 的数也符合要求，而且不仅符合一次，就是说，会重复计算大于 x 位相同的字符串。

我们想一想，两个恰有 a 位相同的字符串在大于等于 b(b<a) 位相同的统计中出现了几次？

考虑组合数，把 a 位中选出 b 位当作相同的，并统计进去，有 C_a^b 种可能。

在程序中，我把恰有 x 位相同的字符串对数记作 jus_x，就可以根据上面的分析写出这样的代码：

jus[4] = mor[4];
jus[3] = mor[3] - jus[4] * 4;
jus[2] = mor[2] - jus[3] * 3 - jus[4] * 6;
jus[1] = mor[1] - jus[2] * 2 - jus[3] * 3 - jus[4] * 4;
jus[0] = n * (n - 1) / 2 - jus[1] - jus[2] - jus[3];

说一句，我没有计算 mor_0，原因是所有的都有大于等于 0 位相同，所以直接用 \dfrac{n \times (n-1)}{2} 代替就可以了。

jus[4] 是因为我没看题，略去。

同时注意到 1 \le D \le 4，所以不要忘记 jus_0。

我还有一个神奇的错误就是我开始写成 36 进制了，所以导致 75pts。希望大家不要犯。

接下来放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 5, maxn = 1874160;
int n, a[N][5], mor[5], jus[5], tong[maxn + 5], base[5], D, tem;
string s;
inline int Str(char c){
    if('0' <= c && c <= '9') return c - '0' + 1;
    return c - 'a' + 11; 
}
inline int calc(int x){
    int res = 0;
    while(x){
        if(x % 37 != 0) res++;
        x /= 37;
    }
    return res;
}
signed main(){
//  freopen("1.in", "r", stdin);
    base[1] = 1;
    for(int i = 2; i <= 4; i++) base[i] = base[i - 1] * 37;
    scanf("%lld%lld", &n, &D);
    for(int i = 1; i <= n; i++){
        cin>>s;
        a[i][1] = Str(s[0]), a[i][2] = Str(s[1]), a[i][3] = Str(s[2]), a[i][4] = Str(s[3]);
    }
    for(int i = 1; i <= n; i++){
        for(int _1 = 0; _1 <= 1; _1++){
            for(int _2 = 0; _2 <= 1; _2++){
                for(int _3 = 0; _3 <= 1; _3++){
                    for(int _4 = 0; _4 <= 1; _4++){
                        tem = a[i][1] * base[1] * _1 + a[i][2] * _2 * base[2] + a[i][3] * _3 * base[3] + a[i][4] * _4 * base[4];
                        tong[tem]++; 
                    }
                }
            }
        }
    }
    for(int i = 1; i <= maxn; i++) mor[calc(i)] += tong[i] * (tong[i] - 1) / 2;
    jus[4] = mor[4];
    jus[3] = mor[3] - jus[4] * 4;
    jus[2] = mor[2] - jus[3] * 3 - jus[4] * 6;
    jus[1] = mor[1] - jus[2] * 2 - jus[3] * 3 - jus[4] * 4;
    jus[0] = n * (n - 1) / 2 - jus[1] - jus[2] - jus[3];
    printf("%lld", jus[4 - D]);
    return 0;
}

我才不会告诉你 freopen 是我 RE 之后下的数据呢。

后记：

如何想到容斥呢？

看标签。

我们可以很容易求出 mor_4,mor_3,mor_2,mor_1,mor_0，然后我们发现 jus_i 与 mor_i 有一定的关系，就可以发现容斥可以做了。

反正我是看标签的。