题解：P6521 [CEOI2010 day2] pin

Istruggle · 2024-12-12 20:42:59 · 题解

看到题目中被加粗的“恰好”，便想到可以用二项式反演将“至少”转化为“恰好”。

我们先将 D 改为 4-D，这样题目就转化为了求有多少对字符串的对应位置相同，接着令 g_k 表示至少 k 个位置相同的对数，令 f_k 表示恰好有 k 个位置对应的字符相同的对数。关于计算 g_k， 我们可以二进制枚举钦定哪些位上的字符相同，接着枚举所有字符串，求出对应位置上的哈希值，并将对应哈希值上的答案累加。

最后套上二项式反演的公式:

最终答案即为 f_D。

AC code:

#include<bits/stdc++.h>
using namespace std;
const int N =5e4+5;
#define int long long
const int mod=1e9+7;
int n,k,g[N],ans,fac[11];
string s[N];
int c(int x,int y){return fac[x]/fac[y]/fac[x-y];}
signed main(){
    scanf("%lld%lld",&n,&k); fac[0]=1; k=4-k;
    for(int i = 1;i<=7;i++) fac[i]=fac[i-1]*i;
    for(int i = 1;i<=n;i++) cin>>s[i];
    for(int S = 0;S<16;S++){
        map<unsigned long long,int> mp;
        for(int i = 1;i<=n;i++){
            unsigned long long hash=0;
            for(int j = 0;j<4;j++){
                if(S&(1<<j))
                hash=hash+s[i][j];
                hash=hash*13331;
            }
            g[__builtin_popcount(S)]+=mp[hash];
            mp[hash]++;
        }
    }
    for(int i = k;i<=4;i++){
        int x;
        if((i-k)%2==1) x=-1;
        else x=1;
        ans+=c(i,k)*g[i]*x;
    }
    printf("%lld",ans);
}