代码

// Experiment: SoA layout + batched merge tincs
#include <sys/auxv.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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));

static int n, m;
static int *prv, *nxt, *dg;
static uint32_t cnt1[6];

#define TABSZ (1u<<24)
#define TABMASK (TABSZ-1)
static uint64_t *tkey;    // 8 bytes
static uint32_t *tmeta;   // 4 bytes

static uint64_t kc[51];
static uint64_t pow6[50];
static const uint64_t H1 = 0x9E3779B97F4A7C15ull;

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

static inline void tinc(uint64_t key, uint32_t k) {
  uint32_t idx = hash_idx(key, kc[k]);
  uint32_t first_del = 0xFFFFFFFFu;
  for (;;) {
    uint32_t meta = tmeta[idx];
    uint32_t st = meta >> 26;
    if (st == 1) {
      if (tkey[idx] == key && ((meta >> 20) & 63) == k) { tmeta[idx] = meta + 1; return; }
    } else if (st == 2) {
      if (first_del == 0xFFFFFFFFu) first_del = idx;
    } else {
      if (first_del != 0xFFFFFFFFu) idx = first_del;
      tkey[idx] = key;
      tmeta[idx] = 1u | (k << 20) | (1u << 26);
      return;
    }
    idx = (idx + 1) & TABMASK;
  }
}

static inline void tdec(uint64_t key, uint32_t k) {
  uint32_t idx = hash_idx(key, kc[k]);
  for (;;) {
    uint32_t meta = tmeta[idx];
    uint32_t st = meta >> 26;
    if (st == 0) return;
    if (st == 1) {
      if (tkey[idx] == key && ((meta >> 20) & 63) == k) {
        uint32_t c = (meta & 0xFFFFF) - 1;
        if (c == 0) tmeta[idx] = (k << 20) | (2u << 26);
        else tmeta[idx] = (meta & ~0xFFFFFu) | c;
        return;
      }
    }
    idx = (idx + 1) & TABMASK;
  }
}

static inline uint32_t tlookup(uint64_t key, uint32_t k, uint64_t kseed) {
  uint32_t idx = hash_idx(key, kseed);
  for (;;) {
    uint32_t meta = tmeta[idx];
    uint32_t st = meta >> 26;
    if (st == 0) return 0;
    if (st == 1 && tkey[idx] == key && ((meta >> 20) & 63) == k) return meta & 0xFFFFF;
    idx = (idx + 1) & TABMASK;
  }
}

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 uint64_t RA[50];
static uint64_t keybuf[1226];
static uint32_t kbuf[1226];

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);
  uint64_t ra = 0, p6 = 1;
  for (int t = 0; t < na; t++) { ra += (uint64_t)sa[t] * p6; RA[t] = ra; p6 *= 6; }
  int dmax = na - 1; if (dmax > 48) dmax = 48;
  for (int d = 0; d <= dmax; d++) {
    uint64_t 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);
  uint64_t ra = 0, p6 = 1;
  for (int t = 0; t < na; t++) { ra += (uint64_t)sa[t] * p6; RA[t] = ra; p6 *= 6; }
  int dmax = na - 1; if (dmax > 48) dmax = 48;
  for (int d = 0; d <= dmax; d++) {
    uint64_t 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;
  if (k == 1) {
    for (uint32_t i = 0; i < slen; i++) {
      int c = s[i] - '1';
      if (c < 0 || c > 5) { *optr++ = '0'; *optr++ = '\n'; return; }
      ans = ans * cnt1[c] % MOD;
      if (ans == 0) { *optr++ = '0'; *optr++ = '\n'; return; }
    }
    out_u64(ans); return;
  }
  uint64_t kseed = kc[k];
  uint64_t powk = pow6[k - 1];
  uint64_t 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 + (uint64_t)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; }
    uint64_t old = (uint64_t)(s[i - k] - '1');
    val = (val - old * powk) * 6 + (uint64_t)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;

  tkey = (uint64_t*)malloc(TABSZ * sizeof(uint64_t));
  tmeta = (uint32_t*)malloc(TABSZ * sizeof(uint32_t));
  memset(tmeta, 0, TABSZ * sizeof(uint32_t));

  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;
  for (int i = 1; i <= n; i++) cnt1[dg[i]]++;

  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;
}

评测结果