BZOJ3160 万径人踪灭

题解
FFT, NTT, manacher

Description

给定一个字符串由 ‘a’ 或 ‘b’ 组成。求有多少个子序列满足字母和坐标都关于一条对称轴对称并且不是连续的

字符串长度 $=n \leq 10^5$

Solution

默认字符串为 $S$ 从 $0$ 开始标号。

答案等于所有的满足字母和坐标都关于一条对称轴对称的子序列数量 - 连续的满足这个性质的子序列数量

后面这个可以直接用 manacher算法 直接求出，只需要考虑前面怎么求

考虑怎么算出关于第 $i$ 个位置对称的子序列个数。设有 $k$ 组 $(x, y)$ 使得 $x + y = 2 i$ 且 $x, y \not= i$ 且 $S_x = S_y$ ，那么方案数就是 $2^{k+1}-1$ （k 组和 $i$ 这个位置选不选减去都不选的一种情况）

考虑怎么算出关于第 $i$ 到第 $i+1$ 个位置中间这个空隙（可以认为是 $i + \frac{1}{2}$）对称的子序列的个数。设有 $k$ 组 $(x,y)$ 满足 $S_x = S_y$ 且 $x+y = 2(i+\frac{1}{2}) = 2i + 1$ ，那么方案数就是 $2^k - 1$（和上面不一样的原因是自己这个位置不是整数不能被选所以不用考虑）

令 $ f_i = \sum\limits_{x+y=i} [S_x=S_y] $ ，那么 $f_i$ 和这个 $k$ 的关系是什么呢？

这里要想清楚。当 $i$ 是偶数的时候，$[S_{\frac{i}{2}}=S_{\frac{i}{2}}]$ 其实也被算了进去，所以应该是 $f_i = 2k + 1$；而 $i$ 是奇数的时候就没有这个问题，直接就是 $f_i = 2k$；综合一下其实就是 $k = \lfloor \frac{f_i}{2} \rfloor$

然后就是怎么求 $f_i$ 的问题了。这是一个卷积的形式，又显然字母之间是独立的。那么对于每一个字母 $x$，令 $g_i = [S_i = x]$，那么 $f$ 就是由两个 $g$ 卷积得到的。所以最后 f 就是对于两个字母分别做一遍卷积加起来就行。

具体的，这道题的做法是：

  1. 拿到字符串，跑 manacher 得到 s1
  2. 令 $f_i = [S_i = a]$，将 $f * f$ 加到多项式 $h$ 中
  3. 令 $g_i = [S_i = b]$，将 $g * g$ 加到多项式 $h$ 中
  4. 答案就相当于 $ \sum\limits_{i=0}^{2n - 2} (2^{\lfloor\frac{h_i}{2}\rfloor + [2|i]}-1)$ （可能有点复杂不过综合上面来看是显然的）

对于卷积，我用的是 NTT (FFT 我也写了，慢了 4 倍嘿嘿)

时间复杂度 $O(n \log n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/**
 * Author: AcFunction
 * Date:   2019-02-26 22:14:41
 * Email:  3486942970@qq.com
**/

#include <bits/stdc++.h>
#define ll long long
#define db double 
#define RG register 
#define rep(i, l, r) for(RG int i = l; i <= r; i++) 
#define per(i, r, l) for(RG int i = r; i >= l; i--)

using namespace std;

void INIT() {
  ios :: sync_with_stdio(false); cin.tie(0); 
}

const int N = 1001000;
const ll mod = (ll)1e9 + 7; 
const ll MOD = 998244353; 
const ll G = 3; 

int n, len[N], r[N], L; 
char S[N]; string s; 
ll f[N], g[N], tmp[N], Ans[N], invl;  

ll fpw(ll x, ll k, ll p) {
  ll ret = 1ll; 
  while(k) {
    if(k & 1) ret = ret * x % p; 
    x = x * x % p; k >>= 1; 
  } return ret; 
}

void NTT(ll *a, int op) {
  rep(i, 0, L - 1) tmp[i] = a[r[i]]; 
  rep(i, 0, L - 1) a[i] = tmp[i]; 
  for(int i = 1; i < L; i <<= 1) {
    ll w = fpw(G, (MOD - 1) / (i << 1), MOD);
    if(op == -1) w = fpw(w, MOD - 2, MOD); 
    for(int j = 0; j < L; j += i << 1) {
      ll wn = 1ll; 
      for(int k = j; k < i + j; k++) {
        ll t = a[i + k] * wn % MOD; 
        a[i + k] = (a[k] - t + MOD) % MOD; 
        a[k] = (a[k] + t) % MOD; wn = wn * w % MOD; 
      }
    }
  }
  if(op == -1) {
    rep(i, 0, L - 1) 
      a[i] *= invl, a[i] %= MOD; 
  }
}


int main() {
  INIT(); 
  cin >> (S + 1); n = strlen(S + 1);
  s = "^#"; 
  rep(i, 1, n) {
    s += S[i]; s += '#'; 
  } int mx = 0, id = 0; 
  rep(i, 1, 2 * n + 1) {
    len[i] = mx > i ? min(len[2 * id - i], mx - i) : 1; 
    while(s[i - len[i]] == s[i + len[i]]) len[i]++; 
    if(mx < i + len[i]) mx = i + len[i], id = i; 
  }
  ll ans = 0; 
  rep(i, 1, 2 * n + 1) ans += len[i] / 2, ans %= mod; 
  L = 1; while(L <= 2 * n) L <<= 1; 
  invl = fpw(L, MOD - 2, MOD); 
  for(int i = 1; i < L; i <<= 1)
    for(int j = 0; j < i; j++)
      r[i + j] = r[j] + L / (i * 2); 
  rep(i, 0, n - 1) f[i] = (S[i + 1] == 'a'); 
  rep(i, 0, n - 1) g[i] = f[i]; 
  NTT(f, 1), NTT(g, 1); 
  rep(i, 0, L - 1) Ans[i] = f[i] * g[i] % MOD; 
  rep(i, 0, n - 1) f[i] = (S[i + 1] == 'b'); 
  rep(i, 0, n - 1) g[i] = f[i];  
  rep(i, n, L - 1) f[i] = g[i] = 0; 
  NTT(f, 1), NTT(g, 1); 
  rep(i, 0, L - 1) Ans[i] += f[i] * g[i] % MOD, Ans[i] %= MOD;
  NTT(Ans, -1); ll anss = 0;
  rep(i, 0, 2 * n - 2) {
    int t = Ans[i]; 
    t = t / 2; 
    if(i & 1) {
      anss += (fpw(2, t, mod) - 1) % mod; anss %= mod; 
    } else anss += (fpw(2, t + 1, mod) - 1) % mod; anss %= mod; 
  }
  cout << ((anss - ans) % mod + mod) % mod << endl; 
  return 0; 
}