P2603 [ZJOI2008] 无序运动

这道题的关键在于如何处理两个粒子片段相似。设两粒子片段分别为 $(a_1, \cdots, a_k)$ 和 $(b_1, \cdots, b_k)$，设 $A_i = \overrightarrow{a_ia_{i + 1}}$，记 $f(a) = A$，$B_i$ 同理，得到两个向量序列 $A, B$。

容易得知，不考虑翻转时，$a$ 相似于 $b$ 当且仅当对于任意 $i\in [1, k - 2]$，有序对 $(A_i, A_{i + 1})$ 和 $(B_i, B_{i + 1})$ 相似，体现为它们的长度比相等 $\dfrac {|A_i|}{|A_{i + 1}|} = \dfrac {|B_i|}{|B_{i + 1}|}$，且 有向 夹角相等 $\lang A_i, A_{i + 1}\rang = \lang B_i, B_{i + 1}\rangle$。

用浮点数记录上述信息丢失精度，考虑记录向量长度的平方比，以及向量叉积与点积的比。一个细节，就是叉积比点积得到夹角正切值，但 $\tan$ 的周期是 $\pi$，无法唯一对应一个 $2\pi$ 范围内的角度。此时我们需要保留叉积的符号，即约分时最大公约数取绝对值。

考虑翻转只需将 $a_i$ 关于 $x$ 或 $y$ 轴对称，再做一遍上述判定即可。

因此，我们得到如下算法：用相邻向量之间的信息描述所有片段和粒子运动轨迹。类似字符串匹配，将信息离散化后容易使用 SA 或 AC 自动机求出每个片段在粒子运动轨迹和粒子运动轨迹关于 $y$ 轴对称得到的轨迹中出现次数之和。

注意点：

• 特判 $k = 2$。
• 当某个片段翻转后与它本身不考虑翻转相似时，它在原粒子运动轨迹中每出现一次均会在翻转后的粒子运动轨迹的对应位置出现，被重复计算。因此要除以 $2$。

时间复杂度 $\mathcal{O}((N + L) \log (n + L))$。

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
using ll = long long;
using pii = pair<int, int>;
inline int read() {
  int x = 0, sgn = 0;
  char s = getchar();
  while(!isdigit(s)) sgn |= s == '-', s = getchar();
  while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
  return sgn ? -x : x;
}
bool Mbe;
constexpr int N = 1e5 + 5;
constexpr int L = 2e6 + 5;
int len, s[L];
int sa[L], rk[L], ork[L], buc[L], id[L], ht[L];
bool cmp(int a, int b, int w) {return ork[a] == ork[b] && ork[a + w] == ork[b + w];}
void build(int n) {
  int m = N - 1, p = 0;
  for(int i = 1; i <= n; i++) buc[rk[i] = s[i]]++;
  for(int i = 1; i <= m; i++) buc[i] += buc[i - 1];
  for(int i = n; i; i--) sa[buc[rk[i]]--] = i;
  for(int w = 1; ; w <<= 1, m = p, p = 0) {
    for(int i = n - w + 1; i <= n; i++) id[++p] = i;
    for(int i = 1; i <= n; i++) if(sa[i] > w) id[++p] = sa[i] - w;
    memset(buc, 0, sizeof(buc));
    memcpy(ork, rk, sizeof(rk));
    p = 0;
    for(int i = 1; i <= n; i++) buc[rk[i]]++;
    for(int i = 1; i <= m; i++) buc[i] += buc[i - 1];
    for(int i = n; i; i--) sa[buc[rk[id[i]]]--] = id[i];
    for(int i = 1; i <= n; i++) rk[sa[i]] = cmp(sa[i - 1], sa[i], w) ? p : ++p;
    if(p == n) break;
  }
  for(int i = 1, k = 0; i <= n; i++) {
    if(k) k--;
    while(s[i + k] == s[sa[rk[i] - 1] + k]) k++;
    ht[rk[i]] = k;
  }
}
struct dat {
  int L1, L2;
  ll cross, dot;
  void form(pii a, pii b) {
    int ax = a.fi, ay = a.se, bx = b.fi, by = b.se;
    L1 = ax * ax + ay * ay;
    L2 = bx * bx + by * by;
    cross = ax * by - ay * bx;
    dot = ax * bx + ay * by;
    ll d = __gcd(L1, L2);
    L1 /= d, L2 /= d;
    d = abs(__gcd(cross, dot));
    cross /= d, dot /= d;
  }
  bool operator < (const dat &rhs) const {
    if(L1 != rhs.L1) return L1 < rhs.L1;
    if(L2 != rhs.L2) return L2 < rhs.L2;
    if(cross != rhs.cross) return cross < rhs.cross;
    return dot < rhs.dot;
  }
  bool operator == (const dat &rhs) const {
    return L1 == rhs.L1 && L2 == rhs.L2 && cross == rhs.cross && dot == rhs.dot;
  }
} d[L];
int n, m, cnt;
int fa[L], val[L];
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
void merge(int u, int v) {val[u = find(u)] += val[v = find(v)], fa[v] = u;}
int pos[N], ans[N], sym[N];
vector<dat> seq[N];
bool Med;
int main() {
  fprintf(stderr, "%.4lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
  #endif
  cin >> n >> m;
  assert(n > 2);
  for(int i = 1; i <= m + 1; i++) {
    int k = i <= m ? read() : n;
    assert(k > 1);
    vector<pii> pt;
    pt.reserve(k);
    int lx = read(), ly = read();
    for(int j = 1; j < k; j++) {
      int cx = read(), cy = read();
      pt.push_back((pii) {cx - lx, cy - ly});
      lx = cx, ly = cy;
    }
    if(k == 2 && i <= m) {
      ans[i] = n - 1;
      continue;
    }
    vector<dat> norm, refl;
    for(int p = 1; p < pt.size(); p++) {
      dat res;
      res.form(pt[p - 1], pt[p]);
      norm.push_back(d[++cnt] = res);
    }
    for(pii &it : pt) it.fi = -it.fi;
    for(int p = 1; p < pt.size(); p++) {
      dat res;
      res.form(pt[p - 1], pt[p]);
      refl.push_back(res);
    }
    seq[i] = norm, sym[i] = norm == refl;
    if(i == m + 1) {
      for(dat it : refl) d[++cnt] = it;
      seq[i + 1] = refl;
    }
  }
  sort(d + 1, d + cnt + 1);
  cnt = unique(d + 1, d + cnt + 1) - d - 1;
  for(int i = 1; i <= m + 2; i++) {
    pos[i] = len + 1;
    for(dat it : seq[i]) s[++len] = lower_bound(d + 1, d + cnt + 1, it) - d;
    s[++len] = cnt + i;
  }
  build(len);
  static int p[L], q[N];
  for(int i = 1; i <= m; i++) q[i] = i;
  for(int i = 1; i <= len; i++) val[i] = sa[i] >= pos[m + 1], fa[i] = p[i] = i;
  sort(p + 1, p + len + 1, [&](int u, int v) {return ht[u] > ht[v];});
  sort(q + 1, q + m + 1, [&](int u, int v) {return seq[u].size() > seq[v].size();});
  for(int i = N - 1, ppt = 1, qpt = 1; i; i--) {
    while(ppt <= len && ht[p[ppt]] == i) merge(p[ppt], p[ppt] - 1), ppt++;
    while(qpt <= m && seq[q[qpt]].size() == i) ans[q[qpt]] = val[find(rk[pos[q[qpt]]])], qpt++;
  }
  for(int i = 1; i <= m; i++) printf("%d\n", ans[i] / (sym[i] ? 2 : 1));
  return cerr << "Time: " << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n", 0;
}
/*
2022/7/13
start coding at 13:13
finish debugging at 20:02
*/

https://blog.csdn.net/tenkuo/article/details/153035761