【CEOI2015】pin

· · 题解

  传送门

  今天机房T3出了这道题，纪念第一次机房模拟赛AK

  这道题一下想到容斥的都是数学神仙吧。

  一步步分析。当 15% 的暴力打完以后，我们发现其实 D 只有四种，所以自然想到分类讨论 D。既然第一个给的是 D=1，自然是有他的道理的。

  "有一个不同"的关系和"有三个相同"是一一对应的。考虑计算三个字符相同的密码的数，枚举这三个字符的位置，只有 C_4^3=4 种。此时我们可以用一个三维数组去记录这三个字符出现的所有次数，最后枚举所有的三个字符的情况对应的次数 k，C_{k}^2 就是贡献。但是我们可以用哈希的思想把给定的三个字符转成一个三十六进制数（机房考试没有十六进制的部分分，我也感觉没必要）：

inline int hash3(char a,char b,char c){
    return hash1(a)*36*36+hash1(b)*36+hash1(c);
}

  相应的我们写出了这样的代码：

//3位相同
for(int i=1;i<=4;i++){
    for(int j=i+1;j<=4;j++){
        for(int k=j+1;k<=4;k++){
            clearmemory();
            for(int l=1;l<=n;l++){
                size[hash3(pins[l][i],pins[l][j],pins[l][k])]++;
            }
            for(int l=0;l<=LIM;l++){
                cnt[3] = cnt[3] + size[l] * (size[l]-1)/2; 
            }
        }
    }
}

  这个 clearmemory() 是memset。i,j,k 代表计算的是哪三位相同的字符串关系数量。l 则枚举的是对应的字符串，把每个字符串对应的这三位转成一个唯一的 36 进制数（上界用计算器可算出小于5e4），然后统计每个数出现的次数，从中选出两个数的对数就是这三位相同的字符串关系数量。

  两位和一位的哈希函数同理，完整代码会在文末给出。

  这个时候不是输出 cnt(4-d) 就完事的。题目要求的是恰好 4-D 位相同的关系。考虑两个密码0001，0002，如果 D=2，答案是0，然而它们两确实是有两位相同的，而且还不知一个，第一位&第二位，第一位&第三位，第二位&第三位这三种情况下这个三位相同的都会被加进两位相同的去算）。考试的时候我卡在这里卡了很久

  题目中的一句话点醒了我:“任意两个字符串都有多于一个位置不相同” ，再想一下第一个是 D=1，当我们计算出 cnt(3) 的时候，其实是没有多算的，因为没有什么字符串是四位全部相同的，最多也就三位相同，所以当 D=1 的时候输出 cnt(3) 即可。

  顺着下去推 D=2（记作 ans(2)），显然每个 ans(3)（根据上文我们已经知道就是 cnt(3)) 会在两个字符相同计数时被算三次，这实际上是 C_3^2 = 3的缘故.所以 ans(2) = cnt(2)-ans(3)*3，这是容斥（补集）的思想

  接下来是 D=3，每一个 ans(2) 会算两次，ans(3) 是3次，因为C_2^1 = 2,C_3^1=3 的缘故。所以 ans(1) = cnt(1)-ans(2)*2-ans(3)*3

  最后 D=4 即没有相同字符关系的密码的数量，显然一共有 \frac{n(n-1)}{2} 对关系，减去 (ans(1)+ans(2)+ans(3)) 即可。即 ans(0) = C_n^2-ans(1)-ans(2)-ans(3)

  最后输出 ans(4-D) 就是答案啦QwQ

//CEOI,2010
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=6e4+10,LIM=5e4;
int n,d;
char pins[MAXN][10];
long long size[MAXN],cnt[10],ans[10];
inline void clearmemory(){
    memset(size,0,sizeof size);
}
inline int hash1(char a){
    if(a>='0'&&a<='9'){
        return a-'0';
    }else{
        return a-'a'+10;
    }
}
inline int hash2(char a,char b){
    return hash1(a)*36+hash1(b);
}
inline int hash3(char a,char b,char c){
    return hash1(a)*36*36+hash1(b)*36+hash1(c);
}
int main(){
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;i++){
        scanf("%s",pins[i]+1);
    }
    //1位相同 
    for(int i=1;i<=4;i++){
        clearmemory();
        for(int j=1;j<=n;j++){
            size[hash1(pins[j][i])]++;
        }
        for(int j=0;j<=LIM;j++){
            cnt[1] = cnt[1] + size[j] * (size[j]-1)/2;
        }
    }
    //2位相同
    for(int i=1;i<=4;i++){
        for(int j=i+1;j<=4;j++){
            clearmemory();
            for(int k=1;k<=n;k++){
                size[hash2(pins[k][i],pins[k][j])]++;
            }
            for(int k=0;k<=LIM;k++){
                cnt[2] = cnt[2] + size[k] * (size[k]-1)/2;
            }
        }
    } 
    //3位相同
    for(int i=1;i<=4;i++){
        for(int j=i+1;j<=4;j++){
            for(int k=j+1;k<=4;k++){
                clearmemory();
                for(int l=1;l<=n;l++){
                    size[hash3(pins[l][i],pins[l][j],pins[l][k])]++;
                }
                for(int l=0;l<=LIM;l++){
                    cnt[3] = cnt[3] + size[l] * (size[l]-1)/2; 
                }
            }
        }
    } 
    ans[3] = cnt[3];
    ans[2] = cnt[2]-ans[3]*3;
    ans[1] = cnt[1]-ans[2]*2-ans[3]*3;
    ans[0] = (long long)n*(n-1)/2 - ans[1]-ans[2]-ans[3];
    printf("%lld",ans[4-d]); 
    return 0;
}