题目大意

多组数据:每组数据给你由前 $20$ 个小写字母组成的长度为 $n$ 的字符串,询问 $m$ 次,每次询问给出不超过 $5$ 个字母,询问满足这些字母的出现次数为偶数的子区间的个数。
$n \leq 10^5,m \leq 3\times 10^4$

题解

题目英文名字是。。金坷垃?(大雾
首先一个显然的转化是将每个字母看成一个二进制数,满足它对应的那一位是 $1$ 其他都是 $0$。然后就是询问多少子区间的异或和在给出的位上是 $0$ 了。
然后做前缀和,变成了询问是否有两个值的异或在给出的位上是 $0$。
到这里我就不会做了。。因为如果直接容斥怎么看起来都会爆炸的样子
看了题解后再次认识到了自己的无知与弱小。。
题解继续提示我们:我们可以只考虑这几位,那么合法的对数肯定满足按位相等。然后我们可以考虑枚举他们相等于什么,然后就是求有多少个数满足这些位是你枚举的那个数,假设是 $cnt$,那么贡献就是 $\binom {cnt} 2$
暴力统计还是会超时。。我们就考虑如何快速统计。
直接容斥显然会爆炸,我们注意到我们实际上是枚举了所有的状态,我们不妨固定 $1$,只去容斥 $0$,现在只需要求一部分强制为 $1$ 其他部分随便填的方案数了,这又是个高维前缀和。
于是这个我不会的题就做完了 QAQ(我什么时候才能会做这种题啊

/*
 * Author: RainAir
 * Time: 2019-08-28 11:43:37
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e6 + 5;
const int MAXL = 1e5 + 5;
char str[MAXL];
int a[MAXN],f[MAXN],pc[MAXN],n;

inline void FMT(){
    FOR(i,0,19){
        FOR(S,0,(1<<20)-1){
            if(!(S&(1<<i))) f[S] += f[S|(1<<i)];
        }
    }
}

inline void Solve(){
    CLR(f,0);
    scanf("%s",str+1);n = strlen(str+1);
    FOR(i,1,n) a[i] = (1<<(str[i]-'a'));
    FOR(i,1,n) a[i] ^= a[i-1];
    f[0]++;FOR(i,1,n) f[a[i]]++;
    FMT();int q;scanf("%d",&q);
    while(q--){
        int s = 0,k;scanf("%d",&k);
        FOR(i,1,k){
            scanf("%s",str+1);
            s |= (1<<(str[1]-'a')); // 需要变成 0 的
        }
        int s1 = s;LL ans = 0;
        do{ //  s1 枚举哪些强制为 1
            int s2 = s^s1,s3 = s2,cnt = 0; // s2 哪些是要容斥掉的 0
            do{ // s3 枚举哪些强制为 1(0 = (unlimited-1))
                cnt += (pc[s3]&1?-1:1)*f[s1|s3]; // 其他无限制 超集和
                s3 = (s3-1)&s2;
            }while(s2 != s3);
            ans += 1ll*cnt*(cnt-1)/2;
            s1 = (s1-1)&s;
        }while(s1 != s);
        printf("%lld\n",ans);
    }
}

signed main(){
    int tt = sizeof(str)+sizeof(a)+sizeof(f)+sizeof(pc);
//    DEBUG(tt/1024/1024);
    FOR(i,1,MAXN-1) pc[i] = pc[i>>1]+(i&1);
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏