题解：AT_nikkei2019_2_final_h 逆にする関数

· · 题解

更好的阅读体验

这题，真厉害。这题可能可以帮助你发现，你并没有学懂 manacher 算法。

首先，我们回顾一下 manacher 算法的流程（仅考虑求奇回文串）：

事实上，维护回文信息只是 manacher 应用场景的一个特殊情况。观察以上算法的流程，我们发现：

我们来看这个题。容易发现本题中的信息满足以上两个条件。首先考虑找出所有的合法区间，则只需要解决“判断一个区间 [l, r] 能否扩展到 [l-1, r+1]”。我们这样判断：我们要新加入 a_{l-1} 这个数，如果 a_{l-1} 在 [l, r] 中未出现，则相当于多确定了 f 的一个点值，因此始终合法；若 a_{l-1} 在 [l, r] 中出现了，则要查看与它在 [l, r] 出现时匹配的元素，若这个元素 = a_{r+1}，则说明合法；否则不合法。加入 a_{r+1} 的判断也是完全相同的。则同样地，可以处理出 d_i 表示以 i 为中心的最长有解区间半径。

则考虑对于一个有解的区间 [l, r]，我们要如何求出满足条件的映射 f 的数量。这是容易的。假设 [l, r] 中不同数字有 c 个，则可以认为是已经确定了 f 的 c 个点值，而剩下 m - c 个是未确定的，因此方案数位 m^{m - c}。在此基础上我们考虑 dp：f_i 表示以 i 为中心的合法字符串的 m^{m - c} 之和，再假设 g_i 表示以 i 为中心的最长合法区间中，不同数字的个数。容易发现 f 和 d 的变化是同步的，而 d 有两种变化方式：逐步递增和继承某个位置的值。当 d_i 递增的时候，容易维护 g_i 的变化，进而计算出 f_i 的增量。接下来主要问题就在于，从 l + r - i 继承的情况。

我们回顾普通的 manacher 算法在继承一步时怎么做的：让 d_i 的初始值 = \min\{d_{l + r - i}, r - i + 1\}。此时如果 d_{l + r - i} \le r-i+1，则此时直接令 f_i := f_{l + r - i}, g_i := g_{l + r - i} 即可。但是如果 r - i + 1 < d_{l + r - i} 该怎么办？我们发现让 d_i 增加 1 和让 d_i 减少 1 的算法时完全相同的。因此我们考虑直接继承 l + r - i 位置的值，然后再逐一减小 d_i 直到 d_i = r - i + 1。

接下来说明这个算法仍然是线性时间。

原命题相当于证明，整个算法过程中，\max \{0, d_{l + r - i} - (r - i + 1)\} 之和为 O(n)。

假设 [l, r] 的回文中心为 x，则 l = 2x - r, l + r - i = 2x - i。

则由于 [l, r] 是目前最右的回文串，因此必然有 d_{2x - i} + 2x-i< d_x + x。

记 k = i - x。则 2x - i = x - k。代入上式有 d_{x - k} + x - k < d_x+ x, d_{x - k} < d_x + k。

接下来考虑需要进行回缩操作的条件：i + d_{2x - i} > x + d_x。

可以得到 d_{x - k} > d_x + x - i = d_x - k。因此 -k < d_{x - k} - d_x < k。

再考虑我们回缩的量，也就是 i + d_{2x - i} - (x + d_x) 的值。该式可以变形得到 k + d_{x - k} - d_x < 2k。而由于回缩后已经满足 d_i = r-i+1，因此此时 i + d_i - 1 已经成为了右端点最靠右的回文串之一（这个“之一”意味着，我们在回缩操作后，无论 d_i 是否再增加，都要把 i + d_i - 1 设置为新的 r，否则复杂度不正确）。因此我们使用了至多 2k 次移动的代价，使 r 增加了至少 k。

因此算法的复杂度仍为 O(n)。

问题在线性时间内得到解决。

#include<bits/stdc++.h>
#define endl '\n'
#define N 300006
#define MOD 998244353
using namespace std;
inline void add(int &x,int y) {x+=y,x-=x>=MOD?MOD:0;};
inline void dec(int &x,int y) {x+=MOD-y,x-=x>=MOD?MOD:0;}
int n,m,pw[N],a[N],buc[N],pre[N],nxt[N];
int d1[N],d2[N],f1[N],f2[N],g1[N],g2[N];
int refl(int l,int r,int x) {return r-(x-l+1)+1;}
int check(int l,int r)
{
  if(l>r)return 1;
  int ok=1;
  ok&=(pre[r+1]<l-1||a[refl(l-1,r+1,pre[r+1])]==a[l-1]);
  ok&=(nxt[l-1]>r+1||a[refl(l-1,r+1,nxt[l-1])]==a[r+1]);
  return ok;
}
void upd(int &fv,int &gv,int l,int r)
{
  if(nxt[l]>r-1)gv++; if(l!=r&&pre[r]<l)gv++;
  add(fv,pw[m-gv]);
}
void del(int &fv,int &gv,int l,int r)
{
  dec(fv,pw[m-gv]);
  if(nxt[l]>r)gv--; if(l!=r&&pre[r]<l+1)gv--;
}
void manacher()
{
  for(int i=1;i<=m;i++)buc[i]=0;
  for(int i=1;i<=n;i++)pre[i]=buc[a[i]],buc[a[i]]=i;
  for(int i=1;i<=m;i++)buc[i]=n+1;
  for(int i=n;i;i--)nxt[i]=buc[a[i]],buc[a[i]]=i;
  for(int i=1,l=0,r=-1;i<=n;i++)
  {
    int k;
    if(i>r)k=1,upd(f1[i],g1[i],i,i);
    else {
      k=d1[l+r-i],f1[i]=f1[l+r-i],g1[i]=g1[l+r-i];
      int re=l+r-i;
      while(k>r-i+1)del(f1[i],g1[i],re-k+1,re+k-1),k--;
    }
    while(1<=i-k&&i+k<=n&&check(i-k+1,i+k-1))k++,upd(f1[i],g1[i],i-k+1,i+k-1);
    d1[i]=k;
    if(i+k>=r)l=i-k+1,r=i+k-1;
  }
  for(int i=1,l=0,r=-1;i<=n;i++)
  {
    int k;
    if(i>r)k=0;
    else {
      k=d2[l+r-i+1],f2[i]=f2[l+r-i+1],g2[i]=g2[l+r-i+1];
      int re=l+r-i+1;
      while(k>r-i+1)del(f2[i],g2[i],re-k,re+k-1),k--;
    }
    while(1<=i-k-1&&i+k<=n&&check(i-k,i+k-1))k++,upd(f2[i],g2[i],i-k,i+k-1);
    d2[i]=k;
    if(i+k>=r)l=i-k,r=i+k-1;
  }
}
main()
{
  scanf("%d%d",&n,&m),pw[0]=1;
  for(int i=1;i<=m;i++)pw[i]=1ll*m*pw[i-1]%MOD;
  for(int i=1;i<=n;i++)scanf("%d",&a[i]);
  manacher(); int ans=0;
  for(int i=1;i<=n;i++)add(ans,f1[i]);
  for(int i=1;i<=n;i++)add(ans,f2[i]);
  printf("%d\n",ans);
  return 0;
}