[CF1800F] Dasha and Nightmares 题解

如果拼接后字符串满足最后两个条件，那这个串的长度必然是奇数，于是可以忽略第一个条件。

每个字母出现次数的奇偶性显然可以压成一个

26

位的二进制数，设这个二进制数为

a_i

。那么本质上是求满足

a_i\oplus a_j=(2^{26}-1)\oplus 2^x

的

i,j

对数，注意到至多存在一个

x

使得

i,j

满足条件，于是不妨直接枚举

x

，然后把

(2^{26}-1)\oplus 2^x\oplus a_i

扔进桶里面匹配。

时间复杂度

\mathcal{O}(L+n|\Sigma|)

，空间复杂度

\mathcal{O}(2^{|\Sigma|})

，注意使用 long long 会爆炸。扔进 std::map 里面会 T 飞。

code

CPP

#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
using namespace std;
typedef unsigned long long ll;
typedef __int128 LL;
const ll maxn=200007,ee=1e18;
ll n,ans,buc[26];
int b2[1<<26];
string s;
vector<ll> vec[26];
string op(ll x){
	string res;
	for(ll i=0;i<26;i++) res.push_back('0'+(x>>i&1));
	reverse(res.begin(),res.end());
	return res;
}
ll gts(string &s){
	ll res=0;
	for(ll i=0;i<26;i++) buc[i]=0;
	for(auto x:s) res^=(1ll<<(x-'a')),buc[x-'a']++;
	return res;
}
ll calc(ll x,ll z){
	ll V=(1ll<<26)-1;
	V^=(1ll<<z);
	//cout<<op(V)<<"\n";
	return x^V;
}
int main(void){
	//freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n,ans=0;
	for(ll i=1,x;i<=n;i++){
		cin>>s,x=gts(s);
		//cout<<op(x)<<" "<<x<<endl;
		for(ll j=0;j<26;j++)if(!buc[j]) vec[j].pb(x);
	}
	for(ll i=0;i<26;i++){
		for(auto x:vec[i]) b2[x]++;
		for(auto x:vec[i]) ans+=b2[calc(x,i)];
		for(auto x:vec[i]) b2[x]--;
	}
	cout<<ans/2<<"\n";
	return 0;
}

[CF1800F] Dasha and Nightmares 题解

文章操作

相关推荐

评论

[CF1800F] Dasha and Nightmares 题解