RainAir
My OI Blog
RainAir
「HDU4626」Jinkeloid

题目大意

多组数据:每组数据给你由前 $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(我什么时候才能会做这种题啊

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/817
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「HDU4626」Jinkeloid
题目大意 多组数据:每组数据给你由前 $20$ 个小写字母组成的长度为 $n$ 的字符串,询问 $m$ 次,每次询问给出不超过 $5$ 个字母,询问满足这些字母的出现次数为偶数的子区间的个数。 $n…
扫描二维码继续阅读
2019-08-28
标签
近期评论