题链：“https://nanti.jisuanke.com/t/15500”
本来希望通过找循环节然后套KMP来通过后面题的，可是只过了B题，可能循环节不一定是存在的。
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
#define inf 1000000000000000LL
#define mod 1000000007
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;
}
const int N=1e6+10;
int vis[N];
int w[N],f[N];
char s[N],t[N];
void getnext()
{
int i=0,j=-1,l=strlen(t);
f[0]=-1;
while(i<l)
if(j==-1||t[i]==t[j])
f[++i]=++j;
else
j=f[j];
}
int kmp(char *s)
{
int i=0,j=0,k=0,len=strlen(s),l=strlen(t);
while(i<len)
{
if(j==-1|s[i]==t[j])
i+=1,j++;
else
j=f[j];
if(j==l)
k++,j=f[j];
}
return k;
}
int main(){
int n=read(),a=read(),b=read(),l=read(),r=read();
scanf("%s",t);
getnext();
int tmp=b,top=0;
while(!vis[tmp]){
vis[tmp]=1;
w[top++]=tmp;
tmp=(tmp+a)%n;
}
for(int i=0;i<top;i++){
if(w[i]<=r&&w[i]>=l){
s[i]=(w[i]%2==0?'A':'T');
}else{
s[i]=(w[i]%2==0?'G':'C');
}
}
int m=n/top,stop=0;
if(n%top!=0) stop=n-m*top;
ll ans1=kmp(s);
s[stop]=' ';
ll ans2=kmp(s);
printf("%lld
",ans1*m+ans2);
return 0;
}