[CF1800F] Dasha and Nightmares 题解

aeiouaoeiu · 2025-11-12 14:49:15 · 题解

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

每个字母出现次数的奇偶性显然可以压成一个 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 飞。

::::info[code]

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

::::