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

题意

给定一个字符串，求有多少对区间有至少一个相同的字符

其中$n<=100000$

暴力枚举不适合

但是如果把一段区间包含的状态看成一个$16$位的二进制数

总共的状态就是$2^{16}$

这样转化有一个好处,设当前区间的状态为$mask$,那么所有$mask$的子集都是和$mask$有交集

那么首先预处理$a[mask]$表示状态为$mask$的有$a[mask]$个区间

那么显而易见使用$SOSDP$求出$f[mask]=\sum _{i\&mask==i}{a}_i$

然后因为所有的方案有$n^2\ast (n-1{)}^2/4$种方案,减去所有不相交方案数即可

也就是$cnt[i]\ast f[\sim i]$

其中$cnt[i]$为状态为$i$的区间,$f[\sim i]$是和$i$无交集的区间

于是所有问题变成了预处理$a[mask]$,这个只需要使用查找下一个字母的手法就可以求解了

#include 
   
    using namespace std;#define int long longconst int mod = 1e9+7;const int maxn = 1e5+10;const int mx = 1<<16;const int inf = 1e9;int t,n,ans,nxt[maxn][17],f[mx],a[maxn],cnt[mx];char s[maxn];int is(char w){
   	if( w>='0'&&w<='9' )	return w-'0';	return w-'A'+10;}signed main(){
   	cin >> t;	while( t-- )	{
   		scanf("%s",s+1); n = strlen( s+1 );		for(int i=1;i<=n;i++)	a[i] = is(s[i]);		for(int i=0;i<=15;i++)	nxt[n+1][i] = inf;		for(int i=0;i
    
     =1;i--)		{
   			for(int j=0;j<=15;j++)	nxt[i][j] = nxt[i+1][j];			nxt[i][a[i+1]] = i+1;		}		for(int i=1;i<=n;i++)		{
   			int temp = 1<
    
   

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