[數論] 2017 計蒜之道 初賽 第一場 阿裡天池的新任務

我們令子串 Ss,t 對應的 ws 為這個子串的 b

因為互質 是以b是互不相同的 轉為求有幾個 b 滿足條件

然後每一位看作一個限制 把所有限制離散化取交即可 注意處理奇偶性

還有一個細節 s≤n−m+1 我們還要倒着把最後 m−1 個 b <script type="math/tex" id="MathJax-Element-280">b</script>中合法的減掉

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#define pb push_back
using namespace std;
typedef long long ll;

const int N=;

int n,a,b,L,R;
int m; char t[N];

int tot;
int l[N<<],r[N<<]; bool e[N<<];

inline void add(ll _L,ll _R,ll ax,int t){
  if (_L>_R) return;
  ll L=(_L+n-ax%n)%n,R=(_R+n-ax%n)%n;
  if (L<=R){
    l[++tot]=L,r[tot]=R;
    e[tot]=t^((L&)^(_L&));
  }else{
    l[++tot]=,r[tot]=R;
    e[tot]=t^((R&)^(_R&));
    l[++tot]=L,r[tot]=n-;
    e[tot]=t^((L&)^(_L&));
  }
}

int sx[N<<],icnt;
int idx[N<<],cnt;
int T[N<<][];

inline bool cmp(int x,int y){
  return (x>?l[x]:r[-x])<(y>?l[y]:r[-y]);
}

inline int calc(int l,int r,int t){
  if (t==){
    if (~l&) l++;
    if (r&) r++;
    return (r-l+)>>;
  }else{
    if (l&) l++;
    if (~r&) r++;
    return (r-l+)>>;
  }
}

int main(){
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  scanf("%d%d%d%d%d",&n,&a,&b,&L,&R);
  scanf("%s",t+); m=strlen(t+);
  for (int i=;i<=m;i++)
    if (t[i]=='A'){
      add(L,R,(ll)a*(i-)%n,);
    }else if (t[i]=='T'){
      add(L,R,(ll)a*(i-)%n,);
    }
    else if (t[i]=='G'){
      add(,L-,(ll)a*(i-)%n,);
      add(R+,n-,(ll)a*(i-)%n,);
    }else if (t[i]=='C'){
      add(,L-,(ll)a*(i-)%n,);
      add(R+,n-,(ll)a*(i-)%n,);
    }
  sx[++icnt]=; sx[++icnt]=n;
  for (int i=;i<=tot;i++){
    sx[++icnt]=l[i],sx[++icnt]=r[i]+;
  }
  sort(sx+,sx+icnt+); icnt=unique(sx+,sx+icnt+)-sx-;
  for (int i=;i<=tot;i++){
    l[i]=lower_bound(sx+,sx+icnt+,l[i])-sx;
    r[i]=lower_bound(sx+,sx+icnt+,r[i]+)-sx;
    idx[++cnt]=i,idx[++cnt]=-i;
  }
  sort(idx+,idx+cnt+,cmp);
  ll t[]={,}; int pnt=;
  ll ans=;
  for (int i=;i<icnt;i++){
    while (pnt<=cnt && (idx[pnt]>?l[idx[pnt]]:r[-idx[pnt]])==i)
      if (idx[pnt]>)
    t[e[idx[pnt]]]++,pnt++;
      else
    t[e[-idx[pnt]]]--,pnt++;
    T[i][]=t[]; T[i][]=t[];
    if (t[]==m)
      ans+=calc(sx[i],sx[i+]-,);
    if (t[]==m)
      ans+=calc(sx[i],sx[i+]-,);
  }
  for (int i=;i<m;i++){
    b=(b+n-a)%n;
    int it=upper_bound(sx+,sx+icnt+,b)-sx-;
    if (T[it][b&]==m)
      ans--;
  }
  printf("%lld\n",ans);
  return ;
}