题解：P6521 [CEOI2010 day2] pin

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

我们先将

D

改为

4-D

，这样题目就转化为了求有多少对字符串的对应位置相同，接着令

g_k

表示至少

k

个位置相同的对数，令

f_k

表示恰好有

k

个位置对应的字符相同的对数。关于计算

g_k

，我们可以二进制枚举钦定哪些位上的字符相同，接着枚举所有字符串，求出对应位置上的哈希值，并将对应哈希值上的答案累加。

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

f_k = \sum_{i=k}^{n}\binom{i}{k}(-1)^{i-k}g_i

最终答案即为

f_D

。

AC code:

CPP

#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);
}

题解：P6521 [CEOI2010 day2] pin

文章操作

AC code:

相关推荐

评论

题解：P6521 [CEOI2010 day2] pin