[Str记录]HDU6320 Cut The String

· · 个人记录

题意 : 定义串 t 的回文切分为二元串组 (a,b)，其中 t=ab ，且 a,b 均为回文串。

给出一个字符串 s ，每次询问一个子串的回分切分方案数。

多组数据，T\leq 10,n,m\leq 10^5 ，时限\texttt{3s}。

Problem B. Cut The String

对原串正反跑两次 \rm PAM ，求出在每个位置 开始/结尾 的回文串长度集合。

对于询问 s[l,r] ，取出在 l 开头的长度集合 L_1 ，在 r 结尾的长度集合 L_2。

现在要选出 t_1\in L_1,t_2\in L_2 且使得 t_1+t_2=r-l+1。

直接暴力是不行的，利用回文 \rm Border 理论，在某点 开始/结尾 的回文串长度集合可以被划分成 O(\log n) 个等差数列。

现在就是要对 O(\log^2n) 对等差数列，计算有多少种方案各选一数和为定值。不难转化为等差序列求交集。

又能发现，由于 \rm Border 的长度区间可以按照 [2^k,2^{k+1}] 划分，实际上每个等差序列只能对应到 O(1) 个，所以只需要求 O(\log n) 次交。

等差序列求交集相当于求同余方程在一定范围内的解的个数，需要动用扩展中国剩余定理。

复杂度 O(n\log^2n) ，且常数较小，可以通过。

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define ll long long
#define pb push_back
#define MaxN 100500
using namespace std;
struct Data{int l,r,d;};
struct PAM
{
  struct Node
  {int t[26],len,f,tf,d;}a[MaxN];
  int tn,las,tp[MaxN];
  void Init(){
    memset(a,0,sizeof(Node)*(tn+1));
    a[1].f=a[2].f=1;a[1].len=-1;las=tn=2;
  }
  void linkd(int u)
  {
    int fa=a[u].f;
    a[u].d=a[u].len-a[fa].len;
    a[u].tf=(a[u].d==a[fa].d) ? a[fa].tf : u;
  }
  void ins(int k,int c,char *str)
  {
    int p=las;
    while(str[k-a[p].len-1]!=c)p=a[p].f;
    if (!a[p].t[c]){
      int np=las=++tn,v;
      for (v=a[p].f;str[k-a[v].len-1]!=c;v=a[v].f);
      if (!a[v].t[c])a[np].f=2;
      else a[np].f=a[v].t[c];
      a[a[p].t[c]=np].len=a[p].len+2;
      linkd(np);
    }else las=a[p].t[c];
    tp[k]=las;
  }
  void get(int p,vector<Data> &b){
    for (int u=tp[p];u>2;u=a[a[u].tf].f)
      b.pb((Data){a[a[u].tf].len,a[u].len,a[u].d});
  }
}TL,TR;
ll gcd(ll a,ll b){return b==0 ? a : gcd(b,a%b);}
inline ll pre(ll x,ll c,ll m){return (x-c+m)/m;}
void exgcd(ll a,ll b,ll &x,ll &y){
  if (b==0){x=1;y=0;return ;}
  exgcd(b,a%b,y,x);y-=(a/b)*x;
}
ll inv(ll a,ll m){
  ll x,y;exgcd(a,m,x,y);
  return (x%m+m)%m;
}
int calc(Data A,Data B)
{
  if (A.l<B.l)swap(A,B);
  A.l-=B.l;A.r-=B.l;B.r-=B.l;B.l=0;
  ll p1=A.d,p2=B.d,x=(A.l%p1+p1)%p1,pd=gcd(p1,p2);
  if (x%pd)return 0;
  ll p=p1*(p2/pd);
  x=(x/pd)*p2%p*inv(p2,p1)%p;
  ll tl=max(A.l,B.l),tr=min(A.r,B.r),det=-min(tl,tr)/p*p+p*2;
  tl+=det;tr+=det;
  return max(0ll,pre(tr,x,p)-pre(tl-1,x,p));
}
int n,m;
char str[MaxN];
void solve()
{
  scanf("%d%d%s",&n,&m,str+1);
  str[0]=-1;TL.Init();TR.Init();
  for (int i=1;i<=n;i++)TL.ins(i,str[i]-='a',str);
  reverse(str+1,str+n+1);
  for (int i=1;i<=n;i++)TR.ins(i,str[i],str);
  vector<Data> b1,b2;
  while(m--){
    int l,r,len,ans=0;
    scanf("%d%d",&l,&r);
    len=r-l+1;
    b1.clear();b2.clear();
    TL.get(r,b1);TR.get(n-l+1,b2);
    for (int i=0;i<b2.size();i++){
      b2[i].l=len-b2[i].l;b2[i].r=len-b2[i].r;
      swap(b2[i].l,b2[i].r);
    }
    for (int i=0;i<b1.size();i++)
      for (int j=0;j<b2.size();j++){
        if (b1[i].r<b2[j].l||b2[j].r<b1[i].l)continue;
        ans+=calc(b1[i],b2[j]);
      }
    printf("%d\n",ans);
  }
}
int main()
{
  int T;scanf("%d",&T);
  while(T--)solve();
  return 0;
}