代码

// NOI2017 蚯蚓排队 (noi17b)
// k<=50 hash tables (unified, key = (k, base-6 value mod 2^128)), open addressing, power-of-2.
#include <sys/auxv.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned __int128 u128;

struct DuckInfo {
  uint64_t abi_version;
  const char *stdin_ptr; uint64_t stdin_size;
  char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size;
  char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size;
  const char *IB_ptr; uint64_t IB_limit;
  char *OB_ptr; uint64_t OB_limit;
  uint64_t tsc_frequency;
} __attribute__((packed));

// ---- worm linked list ----
static int n, m;
static int *prv, *nxt, *dg;   // dg = length-1 (0..5)

// ---- hash table ----
struct Slot {
  uint64_t lo, hi;
  uint32_t cnt;
  uint8_t k, state;   // state: 0 empty, 1 occupied, 2 tombstone
};
#define TABSZ (1u<<22)
#define TABMASK (TABSZ-1)
static Slot tbl[TABSZ];

static uint64_t kc[51];       // k*CONST, precomputed
static u128 pow6[50];         // 6^0 .. 6^49

static const uint64_t H1 = 0x9E3779B97F4A7C15ull;

static inline uint32_t hash_idx(uint64_t lo, uint64_t hi, uint64_t kseed) {
  uint64_t h = lo ^ (hi * H1);
  h += kseed;
  return (uint32_t)(h & TABMASK);
}

static inline void tinc(u128 val, uint32_t k) {
  uint64_t lo = (uint64_t)val;
  uint64_t hi = (uint64_t)(val >> 64);
  uint64_t h = lo ^ (hi * H1) + kc[k];
  uint32_t idx = (uint32_t)(h & TABMASK);
  uint32_t first_del = 0xFFFFFFFFu;
  for (;;) {
    Slot &s = tbl[idx];
    if (s.state == 1 && s.lo == lo && s.hi == hi && s.k == k) { s.cnt++; return; }
    if (s.state == 2 && first_del == 0xFFFFFFFFu) first_del = idx;
    if (s.state == 0) {
      if (first_del != 0xFFFFFFFFu) idx = first_del;
      Slot &t = tbl[idx];
      t.lo = lo; t.hi = hi; t.k = (uint8_t)k; t.cnt = 1; t.state = 1;
      return;
    }
    idx = (idx + 1) & TABMASK;
  }
}

static inline void tdec(u128 val, uint32_t k) {
  uint64_t lo = (uint64_t)val;
  uint64_t hi = (uint64_t)(val >> 64);
  uint64_t h = lo ^ (hi * H1) + kc[k];
  uint32_t idx = (uint32_t)(h & TABMASK);
  for (;;) {
    Slot &s = tbl[idx];
    if (s.state == 0) return;
    if (s.state == 1 && s.lo == lo && s.hi == hi && s.k == k) {
      if (--s.cnt == 0) s.state = 2;
      return;
    }
    idx = (idx + 1) & TABMASK;
  }
}

static inline uint32_t tlookup(u128 val, uint32_t k, uint64_t kseed) {
  uint64_t lo = (uint64_t)val;
  uint64_t hi = (uint64_t)(val >> 64);
  uint64_t h = lo ^ (hi * H1) + kseed;
  uint32_t idx = (uint32_t)(h & TABMASK);
  for (;;) {
    Slot &s = tbl[idx];
    if (s.state == 0) return 0;
    if (s.state == 1 && s.lo == lo && s.hi == hi && s.k == k) return s.cnt;
    idx = (idx + 1) & TABMASK;
  }
}

// collect A-suffix (from i backward, up to 49) and B-prefix (from j forward, up to 49)
static inline void collect(int i, int j, uint8_t *sa, int *na, uint8_t *sb, int *nb) {
  int x = i;
  sa[0] = (uint8_t)dg[i]; *na = 1;
  while (*na < 49 && prv[x]) { x = prv[x]; sa[(*na)++] = (uint8_t)dg[x]; }
  x = j;
  sb[0] = (uint8_t)dg[j]; *nb = 1;
  while (*nb < 49 && nxt[x]) { x = nxt[x]; sb[(*nb)++] = (uint8_t)dg[x]; }
}

static u128 RA[50];

static inline void do_merge(int i, int j) {
  uint8_t sa[50], sb[50];
  int na, nb;
  collect(i, j, sa, &na, sb, &nb);
  u128 ra = 0, p6 = 1;
  for (int t = 0; t < na; t++) { ra += (u128)sa[t] * p6; RA[t] = ra; p6 *= 6; }
  int dmax = na - 1; if (dmax > 48) dmax = 48;
  for (int d = 0; d <= dmax; d++) {
    u128 val = RA[d];
    int mmax = 49 - d; if (mmax > nb) mmax = nb;
    for (int m2 = 1; m2 <= mmax; m2++) {
      val = val * 6 + sb[m2 - 1];
      tinc(val, (uint32_t)(d + 1 + m2));
    }
  }
  nxt[i] = j; prv[j] = i;
}

static inline void do_split(int i) {
  int j = nxt[i];
  uint8_t sa[50], sb[50];
  int na, nb;
  collect(i, j, sa, &na, sb, &nb);
  u128 ra = 0, p6 = 1;
  for (int t = 0; t < na; t++) { ra += (u128)sa[t] * p6; RA[t] = ra; p6 *= 6; }
  int dmax = na - 1; if (dmax > 48) dmax = 48;
  for (int d = 0; d <= dmax; d++) {
    u128 val = RA[d];
    int mmax = 49 - d; if (mmax > nb) mmax = nb;
    for (int m2 = 1; m2 <= mmax; m2++) {
      val = val * 6 + sb[m2 - 1];
      tdec(val, (uint32_t)(d + 1 + m2));
    }
  }
  nxt[i] = 0; prv[j] = 0;
}

static char *optr;
static const uint64_t MOD = 998244353ull;

static inline void out_u64(uint64_t x) {
  char tmp[24]; int len = 0;
  if (x == 0) { *optr++ = '0'; *optr++ = '\n'; return; }
  while (x) { tmp[len++] = (char)('0' + (x % 10)); x /= 10; }
  while (len) *optr++ = tmp[--len];
  *optr++ = '\n';
}

static inline void query(const char *s, uint32_t slen, uint32_t k) {
  uint64_t ans = 1;
  uint64_t kseed = kc[k];
  u128 powk = pow6[k - 1];
  u128 val = 0;
  for (uint32_t i = 0; i < k; i++) {
    int c = s[i] - '1';
    if (c < 0 || c > 5) { *optr++ = '0'; *optr++ = '\n'; return; }
    val = val * 6 + (u128)c;
  }
  uint32_t cnt = tlookup(val, k, kseed);
  ans = ans * cnt % MOD;
  if (ans == 0) { *optr++ = '0'; *optr++ = '\n'; return; }
  for (uint32_t i = k; i < slen; i++) {
    int c = s[i] - '1';
    if (c < 0 || c > 5) { *optr++ = '0'; *optr++ = '\n'; return; }
    u128 old = (u128)(s[i - k] - '1');
    val = (val - old * powk) * 6 + (u128)c;
    cnt = tlookup(val, k, kseed);
    ans = ans * cnt % MOD;
    if (ans == 0) { *optr++ = '0'; *optr++ = '\n'; return; }
  }
  out_u64(ans);
}

static inline uint32_t rd_u32(const char *&p) {
  while (*p < '0' || *p > '9') p++;
  uint32_t v = 0;
  while (*p >= '0' && *p <= '9') { v = v * 10 + (uint32_t)(*p - '0'); p++; }
  return v;
}

int main() {
  unsigned long duck = getauxval(0x6b637564UL);
  const char *inp; uint64_t insz;
  char *outp; uint64_t outlim;
  DuckInfo *di = 0;
  bool use_duck = (duck != 0);
  static char local_in[1u<<26];
  static char local_out[1u<<21];
  if (use_duck) {
    di = (DuckInfo*)duck;
    inp = di->stdin_ptr; insz = di->stdin_size;
    outp = di->stdout_ptr; outlim = di->stdout_limit;
  } else {
    insz = fread(local_in, 1, sizeof(local_in), stdin);
    inp = local_in;
    outp = local_out; outlim = sizeof(local_out);
  }
  (void)outlim;
  optr = outp;

  const char *p = inp;
  n = (int)rd_u32(p);
  m = (int)rd_u32(p);

  prv = (int*)malloc((size_t)(n + 1) * sizeof(int));
  nxt = (int*)malloc((size_t)(n + 1) * sizeof(int));
  dg = (int*)malloc((size_t)(n + 1) * sizeof(int));
  memset(prv, 0, (size_t)(n + 1) * sizeof(int));
  memset(nxt, 0, (size_t)(n + 1) * sizeof(int));

  for (int i = 1; i <= n; i++) { uint32_t L = rd_u32(p); dg[i] = (int)(L - 1); }

  for (int k = 1; k <= 50; k++) kc[k] = (uint64_t)k * 0xBF58476D1CE4E5B9ull;
  pow6[0] = 1;
  for (int i = 1; i < 50; i++) pow6[i] = pow6[i - 1] * 6;

  // initial k=1 counts
  for (int i = 1; i <= n; i++) tinc((u128)dg[i], 1);

  for (int op = 0; op < m; op++) {
    uint32_t t = rd_u32(p);
    if (t == 1) {
      uint32_t i = rd_u32(p), j = rd_u32(p);
      do_merge((int)i, (int)j);
    } else if (t == 2) {
      uint32_t i = rd_u32(p);
      do_split((int)i);
    } else {
      while (*p == ' ' || *p == '\n' || *p == '\r' || *p == '\t') p++;
      const char *s = p;
      while (*p >= '0' && *p <= '9') p++;
      uint32_t slen = (uint32_t)(p - s);
      uint32_t k = rd_u32(p);
      query(s, slen, k);
    }
  }

  if (use_duck) {
    di->stdout_size = (uint64_t)(optr - outp);
    __asm__ volatile("mov $60, %%rax; xor %%rdi, %%rdi; syscall" ::: "rax","rdi","rcx","r11","memory");
  } else {
    fwrite(outp, 1, (size_t)(optr - outp), stdout);
  }
  return 0;
}

评测结果