本文共 1430 字，大约阅读时间需要 4 分钟。

现在给出$n$个长度为三,由前$24$个字母组成的字符串

如果一个字符串包含至少一个元音我们说这个字符串是正确的

现在让你规定每个字母是否是元音

对于元音的$2^{24}$种组合,计算所有组合[ 正确单词平方 ]的异或和

把$n$个字符串压缩成$24$位的二进制数字,把元音的组合也这样压缩

那么预处理一个$a_x$表示二进制为$x$的字符有$a_x$个

当元音组合的二进制是$mask$时,需要知道所有与$mask$有交集的$x$的$f[mask]=\sum a_x$

这样答案就是$f[0{]}^2\oplus f[1{]}^2.......$

但是我们处理不出这样的$f$数组…

但是使用$SOSDP$可以快速处理$f[mask]$表示所有$mask$子集的$\sum a_x$

那么和$mask$没有交集的数目就是:$f[\sim mask]$

那么$n-f[\sim mask]$就是和$mask$有交集的数目

经过这个奇妙的转化,只需要用$sosdp$的模板即可快速得解

然后还有另一种理解思路,就是先求所有不正确的字符串个数

我们令$mask$为非元音字母的状态

也就是求$f[mask]$表示所有是$mask$子集的$\sum a_x$

那么这些$f[mask]$都是不正确的,因为都被非元音包括了

拿$n$减去即可

然后还有一种容斥的做法别问我为什么那么多做法你一个都不知道

正确单词=包含一个元音的个数-包含两个元音的个数+包含三个元音的个数

那么枚举每个单词的非空子集,根据子集中$1$个数的奇偶来给$f$数组加或者减

这样作为初始化,做一遍$sosdp$即可,

下面是我写的,第一种做法的代码

#include 
   
    using namespace std;const int mx = 1<<24;int f[mx],n;int main(){
   	scanf("%d",&n); getchar();	for(int i=1;i<=n;i++)	{
   		int temp = 0;		for(int j=1;j<=3;j++)		{
   			char w; scanf("%c",&w);			temp |= (1<<(w-'a'));		}	getchar();		f[temp]++;	}	for(int i=0;i<24;i++)	for(int j=mx-1;j>=0;j--)		if( j&(1<
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/112527967 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！