没有啊,AC呀
by kexiye @ 2024-01-29 16:30:39
不对啊，我这里提交好多次都TLE了
by hjfjwl @ 2024-01-29 16:31:36
@[hjfjwl](/user/374715) 这份代码是WA
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 51123987;
const int N = 4e6 + 5;
int p[N];
int l[N];
int r[N];
signed main()
{
int n;
scanf("%lld",&n);
char t[4000005];
scanf("%s",t);
char s[4000005];
s[0]='@';
s[1]='#';
int cur=1;
int sb=strlen(t);
for(register int i = 0;i < sb;i++)
{
s[++cur]=t[i];
s[++cur]='#';
}
int m = strlen(s)-1;
int mid = 0,rr = 0;
int tot = 0;
for(register int i = 1;i <= m;i++)
{
int j = mid * 2 -i;
if(i <= rr)p[i] = min(p[j],rr - i+1);
else p[i] = 1;
while(s[i + p[i]] == s[i - p[i]])
{
p[i]++;
}
int len = p[i] ;
l[i - len + 1]++;
l[i + 1]--;
r[i]++;
r[i + len]--;
if(i + p[i] - 1 > rr)
{
rr = i + p[i]-1;
mid =i;
}
tot += p[i] >> 1;
tot %= mod;
}
for(register int i = 1;i <= m;i++)
{
l[i] += l[i - 1];
r[i] += r[i - 1];
l[i] %= mod;
r[i] %= mod;
}
int sum = 0;
int ans = 0;
for(register int i = 2;i <= m - 2;i+=2)
{
sum += r[i];
sum %= mod;
ans += sum * l[i+2];
ans %= mod;
}
printf("%lld\n",((tot * (tot - 1) >> 1 )% mod - ans + mod) % mod);
return 0;
}
by pig1121 @ 2024-01-29 16:47:27
@[hjfjwl](/user/374715) AC代码
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 51123987;
const int N = 4e6 + 5;
int p[N];
int l[N];
int r[N];
signed main()
{
int n;
scanf("%lld",&n);
char t[4000005];
scanf("%s",t);
char s[4000005];
s[0]='@';
s[1]='#';
int cur=1;
int sb=strlen(t);
for(register int i = 0;i < sb;i++)
{
s[++cur]=t[i];
s[++cur]='#';
}
s[++cur]='&';
int m = strlen(s)-2;
int mid = 0,rr = 0;
int tot = 0;
for(register int i = 1;i <= m;i++)
{
int j = mid * 2 -i;
if(i <= rr)p[i] = min(p[j],rr - i+1);
else p[i] = 1;
while(s[i + p[i]] == s[i - p[i]])
{
p[i]++;
}
int len = p[i] ;
l[i - len + 1]++;
l[i + 1]--;
r[i]++;
r[i + len]--;
if(i + p[i] - 1 > rr)
{
rr = i + p[i]-1;
mid =i;
}
tot += p[i] >> 1;
tot %= mod;
}
for(register int i = 1;i <= m;i++)
{
l[i] += l[i - 1];
r[i] += r[i - 1];
l[i] %= mod;
r[i] %= mod;
}
int sum = 0;
int ans = 0;
for(register int i = 2;i <= m - 2;i+=2)
{
sum += r[i];
sum %= mod;
ans += sum * l[i+2];
ans %= mod;
}
printf("%lld\n",((tot * (tot - 1) >> 1 )% mod - ans + mod) % mod);
return 0;
}
by pig1121 @ 2024-01-29 16:50:37
@[hjfjwl](/user/374715) std::string常数很大
by pig1121 @ 2024-01-29 16:51:10