【bzoj2084】[Poi2010]Antisymmetry

2015.04.16 09:14 Thu | 20次阅读 | 旧日oi | 固定链接 | 源码

Description

对于一个01字符串,如果将这个字符串0和1取反后,再将整个串反过来和原串一样,就称作“反对称”字符串。比如00001111和010101就是反对称的,1001就不是。
现在给出一个长度为N的01字符串,求它有多少个子串是反对称的。

Input

第一行一个正整数N (N <= 500,000)。第二行一个长度为N的01字符串。

Output

一个正整数,表示反对称子串的个数。

Sample Input

8
11001011

Sample Output

7
hint
7个反对称子串分别是:01(出现两次), 10(出现两次), 0101, 1100和001011

题解

正着哈希一遍,反着异或哈希一遍。枚举中点,二分check即可,这里的回文串的长度一定都是偶数,所以check的时候不用考虑中间点重合的情况

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 500010
#define ull unsigned long long
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define base 13131
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
ll ans=0;
char s[maxn];
ull hash1[maxn],hash2[maxn],b[maxn];
ull get_hash1(int st,int ed)
{
    return hash1[ed]-hash1[st-1]*b[ed-st+1];
}
ull get_hash2(int st,int ed)
{
    return hash2[ed]-hash2[st+1]*b[st-ed+1];
}
int check(int x)
{
    int l=1,r=min(x,n-x),mid,tmp=0;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(get_hash1(x-mid+1,x)==get_hash2(x+mid,x+1))
        {
            tmp=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    return tmp;
}
int main()
{
    n=read();b[0]=1;
    for(int i=1;i<=n;i++) b[i]=b[i-1]*base;
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    hash1[i]=hash1[i-1]*base+s[i]-'0';
    for(int i=n;i;i--)
    hash2[i]=hash2[i+1]*base+((s[i]-'0')^1);
    for(int i=1;i<=n;i++)
    ans+=check(i);
    printf("%lld\n",ans);
}```