题目概述

HDU6320

解题报告

暴力想法：枚举 $L$ 开始的回文串 $A$ ，和 $R$ 结尾的回文串 $B$ ，如果 $|A|+|B|=R-L+1$ 则找到一个满足的位置。

由于是枚举结尾回文串，因此可以考虑Palindrome Series优化。构建两个PAM（一正一反），然后分别枚举 $L$ 开始和 $R$ 结尾的等差链，考虑两个等差链 $[L_1,R_1],d_1$ 和 $[L_2,R_2],d_2$ ，则：

$$ R_1-d_1x+R_2-d_2y=R-L+1(R_1-d_1x\ge L_1,R_2-d_2y\ge L_2) $$

显然是一个二元方程，用exgcd求解即可。

虽然复杂度是 $O(n\log_2^3n)$ ，但是Palindrome Series常数很小跑得飞快。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000,maxi=26;

int te,n,Q,pre[maxn+5],suf[maxn+5],ans;char s[maxn+5],t[maxn+5];
struct PAM{
    int pl,son[maxn+5][maxi],len[maxn+5],fai[maxn+5];
    int dif[maxn+5],anc[maxn+5],sum[maxn+5];
    inline int newnode() {pl++;for (int i=0;i<maxi;i++) son[pl][i]=0;return pl;}
    void clear(){
        pl=-1;newnode();newnode();
        fai[0]=fai[1]=1;len[0]=0;len[1]=-1;
    }
    PAM() {clear();}
    int Extend(int p,char *s,int i){
        while (s[i]!=s[i-len[p]-1]) p=fai[p];
        if (!son[p][s[i]-'a']){
            int u=newnode(),k=fai[p];len[u]=len[p]+2;
            while (s[i]!=s[i-len[k]-1]) k=fai[k];
            fai[u]=son[k][s[i]-'a'];son[p][s[i]-'a']=u;
            dif[u]=len[u]-len[fai[u]];
            anc[u]=(dif[u]==dif[fai[u]]?anc[fai[u]]:fai[u]);
        }
        p=son[p][s[i]-'a'];
        return p;
    }
}A,B;

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[1<<16],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,1<<16,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
char getlwr() {char ch=readc();while (!islower(ch)) ch=readc();return ch;}
struct fastO{
    int si;char buf[1<<16];
    fastO() {si=0;}
    void putc(char ch){
        if (si==(1<<16)) fwrite(buf,1,si,stdout),si=0;
        buf[si++]=ch;
    }
    ~fastO() {fwrite(buf,1,si,stdout);}
}fo;
template<typename T> void writei(T x,char ch='\n'){
    static int len=0,buf[100];
    if (x<0) fo.putc('-'),x=-x;
    do buf[len++]=x%10,x/=10; while (x);
    while (len) fo.putc(buf[--len]+48);
    if (ch) fo.putc(ch);
}
int exgcd(int a,int b,LL &x,LL &y){
    if (!b) {x=1;y=0;return a;}
    int r=exgcd(b,a%b,y,x);y-=a/b*x;
    return r;
}
int Count(int i,int j,int len){
    if (A.len[i]+B.len[j]<len) return 0;
    int a=A.dif[i],b=B.dif[j];
    if (A.len[A.anc[i]]+a+B.len[B.anc[j]]+b>len) return 0;
    int ma=(A.len[i]-A.len[A.anc[i]])/a-1,mb=(B.len[j]-B.len[B.anc[j]])/b-1;
    int c=A.len[i]+B.len[j]-len,r;
    LL x,y,tx,ty,t;r=exgcd(a,b,x,y);
    if (c%r) return 0;
    x*=c/r;y*=c/r;tx=b/r;ty=a/r;
    if (x<0) t=(-x+tx-1)/tx,x+=t*tx,y-=t*ty;
    else t=x/tx,x-=t*tx,y+=t*ty;
    if (y>mb) t=(y-mb+ty-1)/ty,y-=t*ty,x+=t*tx;
    if (y<0 || x>ma) return 0;
    return min((ma-x)/tx,y/ty)+1;
}
int main(){
    for (readi(te);te;te--){
        readi(n);readi(Q);
        for (int i=1;i<=n;i++) s[i]=getlwr(),t[n-i+1]=s[i];s[n+1]=t[n+1]=0;
        A.clear();B.clear();
        for (int i=1,p=0;i<=n;i++) p=A.Extend(p,s,i),pre[i]=p;
        for (int i=1,p=0;i<=n;i++) p=B.Extend(p,t,i),suf[n-i+1]=p;
        for (int t=1,L,R;t<=Q;t++){
            readi(L);readi(R);
            ans=0;
            for (int i=pre[R];i>1;i=A.anc[i])
                for (int j=suf[L];j>1;j=B.anc[j])
                    ans+=Count(i,j,R-L+1);
            writei(ans);
        }
    }
    return 0;
}