代码

// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6s_agg2，原提交 #110328
//     <https://duck.ac/submission/110328>（判题机 Time = 258.732222 ms = 本题实时 T）
//     —— 本文件正文 = **该提交的逐字节副本**；其自带引用/思路注释区原样保留在下方。
//     抄它的理由：该件是本题对手当前最好件 T，比本账号现役最好件 #107823（263.36508 ms）
//     快 4.632858 ms（1.76%）。用途：压缩本方缺口（RULES：红题上真更快件必须发）。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号）现役最好件 #107823
//     <https://duck.ac/submission/107823>（263.36508 ms）—— 本地闸门对照基座，不参与正文。
// 合规：duck.ac 提交正文按站点规则公开可见、可直接取用；原提交正文无独立许可证声明。
//     本文件按 /home/yjp/duck.ac/RULES.md 第 3 节署名作者账号与原提交地址。
//     除本头部外，正文**未作任何改动**（无注释剥离、无空白压缩、无语义改动）。
// ======================
// ===== 思路 =====
// 【抄件席 rc_（非本席新工作）】本题 T 持有者 #110328 比我方现役最好件快 1.76%，按铁律落地逐字节副本。
// 本地闸门（**先声明题面域**：n,m 正整数；长度 ≤6；操作 1/2/3 均满足题面前置条件）：
// 复用**本件自带的 `-DLOCAL` stdin→stdout 驱动**（`§2.19.1381`：优先复用现成装置）⇒ 两侧非空 + 逐字节相同 + 正控。
// ================
// References:
// - duck.ac user saffah_cc_v41_agg1, https://duck.ac/submission/107823:
//   This accepted public source is the base; its two-pass query ring, table
//   engine, update pipeline and predecessor citations are retained below.
//   No separate license notice appeared on the public submission.
// - duck.ac user saffah_codex_6s_agg2, https://duck.ac/submission/107677:
//   Our prior independent prefix-hash work informed the investigation; no
//   source fragment from that submission is copied into this variant.
// Approach:
// Store each query-ring hash already multiplied by HMM. The prefetch and
// lookup then consume the same mixed key, removing one 64-bit multiply per
// window. Recover the next block's raw rolling hash with the modular inverse
// of HMM once per block, preserving the original rolling recurrence.
// Parameter experiment: 512 hashes per L1 ring and 12 query windows
// of table prefetch lookahead. This changes batching and cache timing
// while preserving every mixed key and lookup result.
// Purpose:
// Experimentally measure whether moving the hash mixing into the sequential
// generation pass improves official time while retaining exact query results.
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #107778 <https://duck.ac/submission/107778>
//     用途：本次提交的**唯一基座**（本账号本题当代最好件 266.494 ms）。正文逐字节复制，
//     只做以下两处改动。许可：本站账号本人的公开提交记录。
// [2] duck.ac 用户 saffah_codex_6s_agg2，提交 #107553 <https://duck.ac/submission/107553>
//     用途：基座的结构来源（槽指针数组 + prefetchw + h2 前瞻链）。
// [3] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #107609 / #107742 / #107757
//     用途：h2 降宽、两遍法预取机构、更新环前瞻尾拆分的来源。
// ======================
// ===== 思路 =====
// 本席 b17z_（饱和式救援第二席），角度 = **预取机构本身的成本**。
// 本发两处都是**纯 codegen / 内存布局**改动，不碰任何数值路径：
//
// (1) **DISP32（§2.19.799）：`EPF`/`EKEY`/`ELVL` 三个全局数组合并为一个结构体数组**
//     `struct EntP { u64 *slot; u64 key; u32 lv; u32 _pad; };`
//     三者总是**一起写、一起读**（生成环写入、更新环读出），但作为三个独立全局，
//     gcc 在条目生成环里要为每一个**分别 rip 相对 `lea` 物化基址**（本席实测每迭代 5 条 `lea`）；
//     合成一个结构体后三个字段变成**同一基址寄存器上的 disp8 位移**。
//
// (2) 查询两遍法的 pass B **按 4 展开**（`t + 4 <= nb`，余数走尾循环），
//     并把 `c` 声明为 `u64` 让 gcc 省掉每迭代一次的 32→64 零扩展。
//     展开把回边 `cmp/ja`、环内不变量（`if(!kk) kk=1` 的 cmove 源）摊到每 4 条迭代一次。
//
// ★ 本轮**阴性结果（已入库 notes）**：在基座上再加 `#pragma GCC optimize("O3","unroll-loops")`
//   虽然把动态指令数再降 2.64%，判题机却**变慢**（#107814 = 266.748 > 266.494）——
//   该 pragma 让 `.text` 从 10180 B 涨到 15837 B（+56%）⇒ **代码尺寸压过了指令数**。
//   ⇒ `valgrind` 的指令计数在"改动改变代码尺寸"时**不再可外推**，本发因此**不带该 pragma**。
//
// 仪器：`valgrind --tool=callgrind` 的动态指令数（确定性；本机计时在本题不可用）。
// 同一输入 `b17z_bench.txt`（n=30000、1.5e6 查询字符）：
//     基座 #107609 : 191,198,427 条
//     #107742      : 178,005,299 条
//     #107757      : 171,641,241 条
//     #107778（基座）: 168,776,536 条
//     本发         : **165,790,914 条**（较基座 -1.77%，较 #107609 -13.29%）
// 闸门：sample.txt 与 4 个 10^7 级生产输入 + 基准输入上，与基座**逐位相同**；基座自带
// CHECKING 校验器通过。
// ================
// References:
// - duck.ac user saffah_cc_v41_260924, https://duck.ac/submission/107415:
//   copied the public accepted worm queue engine, including its original ideas
//   and predecessor attribution. Its public source has no separate license notice.
// - duck.ac user saffah_cc_v41_agg1, https://duck.ac/submission/107100:
//   adapted its idea of using write-intent prefetch for a read-modify-write target.
//   The public submission gives no separate license notice.
// Approach:
// During batch generation, save the already computed mixed hash beside its
// prefetched table-slot pointer. During insertion, first test that prefetched
// slot directly. Only a collision needs a probe index and the table mask.
// This removes a duplicate 64-bit multiply and initial address computation
// from every update while retaining the exact probing and counts.
// Prefetch hash-table slots with write intent so updates can own those lines
// before changing their counts. This replaces only the two batch-slot hints.
// Merge the matching-key and empty-slot cases into one hot-path exit,
// leaving only collisions in the probe loop.
// Purpose:
// Experimental official submission to measure this update-path change.
#pragma GCC optimize("O3")
#pragma GCC target("bmi,bmi2,popcnt,lzcnt")
// NOI2017 Day1 T2 -- 蚯蚓排队 (Earthworm queue)
// Counts of backwards strings of each length 1..50 kept in open-addressing tables.
//   merge : for x within last 49 of A, add strings (suffix of A at x)+(prefix of B), lengths d+1..min(50,d+|B|)
//   split : same computation, decrement
//   query : multiply counts of every length-k substring of s
// Optimisations:  (a) pre-scan finds which k values occur -> only those levels are maintained,
//                (b) per-level tables are sized to 2*(n-l+1) slots, packed in one pool,
//                (c) entry generation is batched and prefetched before the (latency bound) updates.
typedef unsigned char u8;
typedef unsigned int u32;
typedef unsigned long long u64;

static const u32 MOD = 998244353;
static const u64 HB = 0x9E3779B97F4A7C15ULL | 1ULL;
// hash must be mixed before splitting into index/key: key = hash>>18 alone would
// make strings differing in the last character (e.g. "12321" vs "12322") collide.
static const u64 HMM = 0x9E3779B97F4A7C15ULL;

#define MAXN 300005
#define MAXK 50
#define TMAXBITS 19
#define TMAXSIZE (1u << TMAXBITS)

static const u8 *gip;
static const u8 *gEND;
static u8 *gob;

static u64 POW[MAXK + 2];
static u32 NXT[MAXN], PRV[MAXN];
static u8 VAL[MAXN];

static u64 *TBL[MAXK + 1];
static u32 TMSK[MAXK + 1];
static u64 POOL[51ULL * TMAXSIZE];

// bits: bit s of SMASK[d] set iff level (d+s) is needed; SMAXD[d] = highest such s
static u64 SMASK[MAXK + 2];
static u32 SMAXD[MAXK + 2];
static u32 DMAXX;   // deepest worm distance that can still produce a needed entry
static u8 NEEDED[MAXK + 1];

// ---- input ----
static const u64 MASKV[9] = {0ULL, 0xFFULL, 0xFFFFULL, 0xFFFFFFULL, 0xFFFFFFFFULL,
                             0xFFFFFFFFFFULL, 0xFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFULL,
                             0xFFFFFFFFFFFFFFFFULL};
static const u64 INV5[9] = {1ULL,
                            0xCCCCCCCCCCCCCCCDULL, 0x8F5C28F5C28F5C29ULL, 0x1CAC083126E978D5ULL,
                            0xD288CE703AFB7E91ULL, 0x5D4E8FB00BCBE61DULL, 0x790FB65668C26139ULL,
                            0xE5032477AE8D46A5ULL, 0xC767074B22E90E21ULL};

static inline u32 rd() {
  // RIGHT-ALIGN the k digits by shifting t LEFT 8*(8-k) bits: the separator byte (t's
  // byte k) and everything after it shifts out of the 64-bit word, so the three-level
  // SWAR fusion then yields the value DIRECTLY -- no MASKV[]/INV5[] table loads, no >>j,
  // no in-table magic multiply.  Ported verbatim from work/noip17f_lane4/PF2.cpp rd()
  // (lines 43-62), where it is the shipped, row-minimum form.
  for (;;) {
    u64 x;
    __builtin_memcpy(&x, gip, 8);
    u64 t = x ^ 0x3030303030303030ULL;
    u64 mm = ((t + 0x7676767676767676ULL) | t) & 0x8080808080808080ULL;
    u32 k = mm ? (u32)(__builtin_ctzll(mm) >> 3) : 8u;
    if (k == 0) { gip++; continue; }
    u64 d = t << ((8u - k) << 3);
    u64 c1 = (d * 10 + (d >> 8)) & 0x00FF00FF00FF00FFULL;
    u64 c2 = (c1 * 100 + (c1 >> 16)) & 0x0000FFFF0000FFFFULL;
    u64 c3 = (c2 * 10000 + (c2 >> 32));
    gip += k + 1;
    return (u32)c3;
  }
}

static inline u32 swar_len(const u8 *p) {  // length of digit run
  u32 L = 0;
  for (;;) {
    u64 x;
    __builtin_memcpy(&x, p, 8);
    u64 m = (x - 0x3030303030303030ULL) & ~x & 0x8080808080808080ULL;
    if (m) return L + ((u32)__builtin_ctzll(m) >> 3);
    L += 8;
    p += 8;
  }
}

// ---- output ----
static const char HEXD[201] =
    "00010203040506070809101112131415161718192021222324252627282930313233343536373839"
    "40414243444546474849505152535455565758596061626364656667686970717273747576777879"
    "8081828384858687888990919293949596979899";

static inline void wr(u32 v) {
  u32 len;
  if (v < 10) len = 1;
  else if (v < 100) len = 2;
  else if (v < 1000) len = 3;
  else if (v < 10000) len = 4;
  else if (v < 100000) len = 5;
  else if (v < 1000000) len = 6;
  else if (v < 10000000) len = 7;
  else if (v < 100000000) len = 8;
  else len = 9;
  u8 *o = gob + len;
  u32 t = v;
  while (t >= 100) {
    u32 q = t / 100;
    u32 r = t - q * 100;
    o -= 2;
    __builtin_memcpy(o, HEXD + r * 2, 2);
    t = q;
  }
  if (t < 10) *--o = (u8)('0' + t);
  else { o -= 2; __builtin_memcpy(o, HEXD + t * 2, 2); }
  gob += len;
  *gob++ = '\n';
}

// ---- hash table ----
#ifdef CHECKING
static u64 LEVELSUM[MAXK + 1];
static u32 GOP;
static void verify(u32 n);
#endif

static inline void tupd(u32 ell, u64 key, long sgn) {
  u64 *T = TBL[ell];
  key *= HMM;
  u32 idx = (u32)key & TMSK[ell];
  u64 kk = key >> 18;
  if (!kk) kk = 1;
  for (;;) {
    u64 e = T[idx];
#if defined(CHECKING)
    if ((e >> 18) == kk) { LEVELSUM[ell] += sgn; T[idx] = e + sgn; return; }
    if (e == 0) { LEVELSUM[ell] += sgn; T[idx] = (kk << 18) + (u64)(sgn > 0 ? sgn : 1); return; }
#else
    if ((e >> 18) == kk) { T[idx] = e + sgn; return; }
    if (e == 0) { T[idx] = (kk << 18) + (u64)(sgn > 0 ? sgn : 1); return; }
#endif
    idx = (idx + 1) & TMSK[ell];
  }
}


static inline void tupd_pref(u32 ell, u64 mixed, long sgn, u64 *slot) {
  u64 kk = mixed >> 18;
  if (!kk) kk = 1;
  u64 e = *slot;
  if ((e >> 18) == kk || e == 0) {
#ifdef CHECKING
    LEVELSUM[ell] += sgn;
#endif
    *slot = e ? e + sgn : (kk << 18) + 1ULL;
    return;
  }
  u64 *T = TBL[ell];
  const u32 mask = TMSK[ell];
  u32 idx = (u32)mixed & mask;
  for (;;) {
    idx = (idx + 1) & mask;
    e = T[idx];
    if ((e >> 18) == kk || e == 0) {
#ifdef CHECKING
      LEVELSUM[ell] += sgn;
#endif
      T[idx] = e ? e + sgn : (kk << 18) + 1ULL;
      return;
    }
  }
}

static inline u32 tget_mixed(u32 ell, u64 mixed) {
  const u64 *T = TBL[ell];
  u32 idx = (u32)mixed & TMSK[ell];
  u64 kk = mixed >> 18;
  if (!kk) kk = 1;
  for (;;) {
    u64 e = T[idx];
    if ((e >> 18) == kk) return (u32)(e & 0x3FFFF);
    if (e == 0) return 0;
    idx = (idx + 1) & TMSK[ell];
  }
}

static inline u32 tget(u32 ell, u64 key) {
  const u64 *T = TBL[ell];
  key *= HMM;
  u32 idx = (u32)key & TMSK[ell];
  u64 kk = key >> 18;
  if (!kk) kk = 1;
  for (;;) {
    u64 e = T[idx];
    if ((e >> 18) == kk) return (u32)(e & 0x3FFFF);
    if (e == 0) return 0;
    idx = (idx + 1) & TMSK[ell];
  }
}

// ---- merge / split update ----
#define MAXENT 1300
// DISP32: the three per-entry arrays (slot pointer / mixed key / level) are read
// and written together.  As three separate globals gcc materialises THREE
// rip-relative bases per entry inside the generation loop (measured: 5 `lea` per
// iteration).  As one struct the three fields are disp8-displacements off a
// single base register.
struct EntP { u64 *slot; u64 key; u32 lv; u32 _pad; };
static EntP EE[MAXENT];
static inline void prefetchw_slot(const u64 *p) { __asm__ __volatile__("prefetchw %0" :: "m"(*p)); }

#ifdef PROF
static u64 T_UPD, T_QRY, T_PRE, T_PARSE, T_BUF;
static u32 N_UPD, N_QRY, N_ENT;
static inline u64 rdtp(){ unsigned a,d; __asm__ volatile("rdtsc":"=a"(a),"=d"(d)); return ((u64)d<<32)|a; }
#else
#define rdtp() 0
#endif

// Tail-suffix-hash cache: after a merge whose B side is a single worm the new tail
// is that worm, and TCH[q] caches the hash of the string of length q+1 ending at it.
// This removes the dependent PRV pointer walk for the very common "append one worm"
// pattern.  Invalidated by any split or by any multi-worm merge.
static u64 TCH[MAXK + 1];
static u32 TCT, TCN;

static inline void update(u32 i, u32 j, long sgn) {
#ifdef PROF
  u64 _t0 = rdtp(); N_UPD++;
#endif
  if (!DMAXX) return;  // only level 1 is queried: merges/splits change nothing
  u32 bv[MAXK + 1];
  u32 tb = 0;
  u32 xs[MAXK + 2];
  u32 D = 0;
  // ---- BX3: the B-side successor chain and the A-side predecessor chain are
  // INDEPENDENT, and the A-side index sequence does not depend on `tb` (only the
  // per-depth work below does).  Walk them CONCURRENTLY so both chains' misses are
  // in flight together instead of back to back.  Bit-identical output: `D` is the
  // original `d` at loop exit and xs[] is the same visit order.
  {
    u32 y = j, x = i;
    while ((y && tb < MAXK) || (x && D < DMAXX)) {
      if (y && tb < MAXK) { bv[tb++] = VAL[y]; y = NXT[y]; }
      if (x && D < DMAXX) { xs[D++] = x; x = PRV[x]; }
    }
  }
  u32 nent = 0;
  if (sgn > 0 && tb == 1 && TCN && i == TCT) {
    // fast path: append single worm j after i using the cached suffix hashes
    u32 vj = VAL[j];
    u32 lim = TCN < MAXK ? TCN : MAXK - 1;
    for (u32 q = lim; q-- > 0;) {
      u64 hh = TCH[q] * HB + vj;
      TCH[q + 1] = hh;
      u32 lv = q + 2;
      if (NEEDED[lv]) {
        u64 mixed = hh * HMM; EE[nent].slot = &TBL[lv][(u32)mixed & TMSK[lv]]; EE[nent].key = mixed; EE[nent].lv = lv; nent++;
        ;
      }
    }
    TCH[0] = vj;
    TCN = (TCN < MAXK) ? TCN + 1 : MAXK;
    TCT = j;
#ifdef PROF
    T_BUF += rdtp() - _t0; N_ENT += nent; _t0 = rdtp();
#endif
    { u32 _hl = nent < 34 ? nent : 34; for (u32 _h = 0; _h < _hl; _h++) prefetchw_slot(EE[_h].slot);
    u32 _t = 0, _lim = nent > 34 ? nent - 34 : 0;
    for (; _t < _lim; _t++) { prefetchw_slot(EE[_t + 34].slot); tupd_pref(EE[_t].lv, EE[_t].key, sgn, EE[_t].slot); }
    for (; _t < nent; _t++) tupd_pref(EE[_t].lv, EE[_t].key, sgn, EE[_t].slot); }
#ifdef PROF
    T_UPD += rdtp() - _t0;
#endif
    return;
  }
  TCT = 0;                 // general path invalidates the cache
  u64 chbuf[MAXK + 1];     // suffix hashes of the walked region (for cache rebuild)
  u64 h = 0;
  for (u32 d = 1; d <= D; d++) {   // deeper worms can never produce a needed level
    h = (u64)VAL[xs[d - 1]] * POW[d - 1] + h;  // prepend char x in front of the suffix string
    if (tb == 1) chbuf[d - 1] = h;
    u32 s_hi = SMAXD[d];
    if (s_hi) {
      if (s_hi > tb) s_hi = tb;
      if (s_hi) {
        u64 need = SMASK[d];
        u64 key = h;
        for (u32 s = 1; s <= s_hi; s++) {
          key = key * HB + bv[s - 1];
          if ((need >> s) & 1) {
            u64 mixed = key * HMM;
            EE[nent].slot = &TBL[d + s][(u32)mixed & TMSK[d + s]];
            EE[nent].key = mixed;
            EE[nent].lv = d + s;
            nent++;
            ;
          }
        }
      }
    }
  }
  if (sgn > 0 && tb == 1) {  // single-worm append: the new tail is j, rebuild the cache
    u32 vj = VAL[j];
    u32 lim = D < MAXK ? D : MAXK - 1;
    TCH[0] = vj;
    for (u32 q = 0; q < lim; q++) TCH[q + 1] = chbuf[q] * HB + vj;
    TCN = lim + 1;
    TCT = j;
  }
#ifdef PROF
  T_BUF += rdtp() - _t0; N_ENT += nent; _t0 = rdtp();
#endif
  { u32 _hl = nent < 34 ? nent : 34; for (u32 _h = 0; _h < _hl; _h++) prefetchw_slot(EE[_h].slot);
    u32 _t = 0, _lim = nent > 34 ? nent - 34 : 0;
    for (; _t < _lim; _t++) { prefetchw_slot(EE[_t + 34].slot); tupd_pref(EE[_t].lv, EE[_t].key, sgn, EE[_t].slot); }
    for (; _t < nent; _t++) tupd_pref(EE[_t].lv, EE[_t].key, sgn, EE[_t].slot); }
#ifdef PROF
  T_UPD += rdtp() - _t0;
#endif
}

// ---- query ----
static void solve() {
  POW[0] = 1;
  for (u32 i = 1; i <= MAXK; i++) POW[i] = POW[i - 1] * HB;
  u32 n = rd(), m = rd();
#ifdef CHECKING
  GOP = 0;
#endif
  for (u32 i = 1; i <= n; i++) { VAL[i] = (u8)rd(); NXT[i] = 0; PRV[i] = 0; }

  // (a) pre-scan: which k values appear in queries
  for (u32 i = 0; i <= MAXK; i++) NEEDED[i] = 0;
#ifdef PROF
  u64 _p0 = rdtp();
#endif
  {
    const u8 *p = gip;
    while (p < gEND) {
      const u8 *ls = p;
      for (;;) {  // find end of line (SWAR)
        u64 x;
        __builtin_memcpy(&x, p, 8);
        u64 y = x ^ 0x0A0A0A0A0A0A0A0AULL;
        u64 mm = (y - 0x0101010101010101ULL) & ~y & 0x8080808080808080ULL;
        if (mm) { p += ((u32)__builtin_ctzll(mm) >> 3); break; }
        p += 8;
        if (p >= gEND) { p = gEND; break; }
      }
      if (*ls == '3') {
        const u8 *q = p - 1;
        if (q >= ls && *q == '\r') q--;
        u32 k = 0, mul = 1;
        while (q >= ls && *q >= '0' && *q <= '9') { k += (u32)(*q - '0') * mul; mul *= 10; q--; }
        if (k >= 1 && k <= MAXK) NEEDED[k] = 1;
      }
      p++;
    }
  }
#ifdef PROF
  T_PRE = rdtp() - _p0;
#endif
  // build level masks + sized tables
  for (u32 d = 0; d <= MAXK; d++) SMASK[d] = 0;
  for (u32 d = 1; d <= MAXK; d++) {
    u64 msk = 0;
    for (u32 s = 1; s + d <= MAXK; s++) if (NEEDED[s + d]) msk |= 1ULL << s;
    SMASK[d] = msk;
    SMAXD[d] = msk ? (u32)(63 - __builtin_clzll(msk)) : 0;
  }
  DMAXX = 0;
  for (u32 d = 1; d <= MAXK; d++) if (SMAXD[d]) DMAXX = d;
  {
    // at level l there are at most min(n-l+1, 6^l) distinct strings, so the table
    // only needs twice that many slots (level 1 -> 32 slots, stays in L1)
    u64 *pool = POOL;
    u64 p6 = 6;
    for (u32 l = 1; l <= MAXK; l++) {
      u32 want = 5;
      u64 avail = (n + 1 > l) ? (u64)(n - l + 1) : 0;
      if (p6 < avail) avail = p6;
      if (avail) {
        u64 need = 2ULL * avail + 16;
        while ((1ULL << want) < need && want < TMAXBITS) want++;
      }
      TBL[l] = pool;
      TMSK[l] = (1u << want) - 1;
      pool += (1u << want);
      if (p6 < (1ULL << 40)) p6 *= 6;
    }
  }
  if (NEEDED[1]) {
    u32 c6[7] = {0, 0, 0, 0, 0, 0, 0};
    for (u32 i = 1; i <= n; i++) c6[VAL[i]]++;
    for (u32 v = 1; v <= 6; v++) if (c6[v]) tupd(1, (u64)v, (long)c6[v]);
  }
  for (u32 op = 0; op < m; op++) {
    u32 t = rd();
    if (t == 1) {
      u32 i = rd(), j = rd();
      update(i, j, 1);
      NXT[i] = j; PRV[j] = i;
    } else if (t == 2) {
      u32 i = rd();
      u32 j = NXT[i];
      if (j) update(i, j, -1);
      NXT[i] = 0;
      if (j) PRV[j] = 0;
    } else {
#ifdef PROF
      N_QRY++; u64 _q0 = rdtp();
#endif
      while (*gip <= 32) gip++;  // skip separator before s
      const u8 *ps = gip;
      u32 L = swar_len(ps);
      gip = ps + L;
      u32 k = rd();
      u64 res;
      if (k > MAXK) {
        res = 0;  // no worm has a string longer than 50
      } else {
        u64 pk = POW[k];
        u32 nw = L - k + 1;
        u64 acc = 1;
        // all length-k windows coincide iff every character of s is the same
        // (holds for the "all ones" test points) -> single lookup + power
        u32 same = 1;
        {
          const u8 c0 = ps[0];
          u64 pat = 0x0101010101010101ULL * (u64)c0;
          const u8 *a = ps;
          u32 rem = L;
          while (rem >= 8) {
            u64 x;
            __builtin_memcpy(&x, a, 8);
            if (x != pat) { same = 0; break; }
            a += 8; rem -= 8;
          }
          if (same) for (; rem; rem--) { if (*a++ != c0) { same = 0; break; } }
        }
        if (same) {
          u64 h = 0;
          for (u32 i = 0; i < k; i++) h = h * HB + (u64)(ps[i] - '0');
          u64 base = tget(k, h) % MOD;
          u64 r = 1, e = nw;
          while (e) { if (e & 1) r = r * base % MOD; base = base * base % MOD; e >>= 1; }
          acc = r;
        } else {
          const u8 *p = ps;
          u64 h1 = 0;
          for (u32 i = 0; i < k; i++) h1 = h1 * HB + (u64)(p[i] - '0');
          u32 i = 0;
          // D as a COMPILE-TIME constant: with a runtime D gcc must keep an extra
          // `i+D` register live (spilled to the stack here); as a constant the term
          // folds into the addressing mode.  Small tables keep the old D==0
          // behaviour by taking the plain tail loop instead (separate predicate).
          const u32 D = 12;
          if (TMSK[k] >= (1u << 13) && nw > D) {
            // ---- two-pass prefetch (seat b17z_'s angle) -------------------------
            // The two rolling-hash chains (h1 for the lookup, h2 for the lookahead
            // address) cost ~19 of this loop's ~64 instructions, and h2 is pure
            // address generation for a *hint*.  Here the ONE h1 chain is recomputed
            // for a whole block into a small L1-resident ring by a loop that touches
            // no table and runs no probe (branch-light, register-light); the hot loop
            // then reads the hash of window t and of window t+D straight out of the
            // ring.  Per iteration the lookahead costs a load + imul + and +
            // prefetcht0 instead of a second rolling-hash chain.
            // Pass A uses the SAME recurrence with the SAME operands, so the stored
            // h values are bit-identical to those the fused loop computed, and pass B
            // prefetches exactly the same lines.
            const u32 BLK = 512;
            const u32 HMM32 = (u32)HMM;
            u64 *T = TBL[k];
            u32 msk = TMSK[k];
            const u32 lim = nw - D;   // windows that have a valid t+D lookahead
            u64 hb[BLK + 16];
            u64 h = h1;               // hash of window `blk`
            u32 blk = 0, dead = 0;
            while (blk < lim) {
              u32 nb = lim - blk;
              if (nb > BLK) nb = BLK;
              const u32 ext = nb + D;
              u64 hh = h;
              {
                // fold the '-\'0\'' bias of BOTH operands into one per-query constant:
                //   (pa-'0') - (pb-'0')*pk  ==  pa - pb*pk + (48*pk - 48)
                // so both byte loads become plain zero-extends (no movslq) and the
                // whole increment is sub + add against precomputed registers.
                const u64 BIAS = 48 * pk - 48;
                const u8 *pa = p + blk + k;
                const u8 *pb = p + blk;
                const u8 *paE = pa + ext;
                u64 *hp = hb;
                for (; pa < paE; pa++, pb++) {
                  *hp++ = hh * HMM;
                  hh = hh * HB + (u64)*pa - (u64)*pb * pk + BIAS;
                }
              }
              const u64 hnext = hb[nb] * 0xf1de83e19937733dULL;
              u32 t = 0;
              for (; t + 4 <= nb; t += 4) {     // pass B, unrolled x4
                __builtin_prefetch(&T[((u32)hb[t + D] & msk)]);
                u64 c = tget_mixed(k, hb[t]);
                if (!c) { acc = 0; dead = 1; break; }
                acc *= c;
                if (acc >= (1ULL << 45)) acc %= MOD;
                __builtin_prefetch(&T[((u32)hb[t + 1 + D] & msk)]);
                c = tget_mixed(k, hb[t + 1]);
                if (!c) { acc = 0; dead = 1; break; }
                acc *= c;
                if (acc >= (1ULL << 45)) acc %= MOD;
                __builtin_prefetch(&T[((u32)hb[t + 2 + D] & msk)]);
                c = tget_mixed(k, hb[t + 2]);
                if (!c) { acc = 0; dead = 1; break; }
                acc *= c;
                if (acc >= (1ULL << 45)) acc %= MOD;
                __builtin_prefetch(&T[((u32)hb[t + 3 + D] & msk)]);
                c = tget_mixed(k, hb[t + 3]);
                if (!c) { acc = 0; dead = 1; break; }
                acc *= c;
                if (acc >= (1ULL << 45)) acc %= MOD;
              }
              if (!dead)
                for (; t < nb; t++) {           // pass B tail
                  __builtin_prefetch(&T[((u32)hb[t + D] & msk)]);
                  u64 c = tget_mixed(k, hb[t]);
                  if (!c) { acc = 0; dead = 1; break; }
                  acc *= c;
                  if (acc >= (1ULL << 45)) acc %= MOD;
                }
              if (dead) break;
              h = hnext;
              blk += nb;
            }
            if (!dead) {                       // tail: windows [lim, nw)
              u64 hh = h;
              for (i = lim; i < nw; i++) {
                u32 c = tget(k, hh);
                if (!c) { acc = 0; break; }
                acc *= c;
                if (acc >= (1ULL << 45)) acc %= MOD;
                hh = hh * HB + (u64)(p[i + k] - '0') - (u64)(p[i] - '0') * pk;
              }
            } else {
              i = nw;
            }
          } else {
            for (; i < nw; i++) {
              u32 c = tget(k, h1);
              if (!c) { acc = 0; break; }
              acc *= c;
              if (acc >= (1ULL << 45)) acc %= MOD;
              h1 = h1 * HB + (u64)(p[i + k] - '0') - (u64)(p[i] - '0') * pk;
            }
          }
          if (acc >= MOD) acc %= MOD;
        }
        res = acc;
      }
      wr((u32)res);
#ifdef PROF
      T_QRY += rdtp() - _q0;
#endif
    }
#ifdef CHECKING
    GOP++;
#ifdef CHECKALL
    verify(n);
#else
    if (op + 1 == m) verify(n);
#endif
#endif
  }
}

#ifdef CHECKING
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
static void verify(u32 n) {
  static std::map<std::string, u32> cnt[MAXK + 1];
  for (u32 l = 1; l <= MAXK; l++) cnt[l].clear();
  for (u32 x = 1; x <= n; x++) {
    std::string s; u32 y = x;
    for (u32 l = 1; l <= MAXK; l++) {
      if (!y) break;
      s += (char)('0' + VAL[y]); y = NXT[y];
      cnt[l][s]++;
    }
  }
  int bad = 0;
  for (u32 l = 1; l <= MAXK; l++) {
    if (!NEEDED[l]) continue;
    u64 tot = 0;
    {
      std::map<u64, std::string> seen;
      for (std::map<std::string, u32>::iterator it = cnt[l].begin(); it != cnt[l].end(); ++it) {
        u64 h = 0;
        for (size_t i = 0; i < it->first.size(); i++) h = h * HB + (u64)(it->first[i] - '0');
        std::map<u64, std::string>::iterator s2 = seen.find(h);
        if (s2 != seen.end()) {
          printf("  OP%u HASHCOLLISION level %u: %s vs %s\n", GOP, l,
                 it->first.c_str(), s2->second.c_str());
          bad = 1;
        } else seen[h] = it->first;
      }
    }
    for (std::map<std::string, u32>::iterator it = cnt[l].begin(); it != cnt[l].end(); ++it) {
      u64 h = 0;
      for (size_t i = 0; i < it->first.size(); i++) h = h * HB + (u64)(it->first[i] - '0');
      u32 got = tget(l, h);
      if ((u64)got != it->second) {
        printf("  OP%u level %u str %s table=%u true=%u\n", GOP, l, it->first.c_str(), got, it->second);
        bad = 1;
      }
      tot += it->second;
    }
    if (tot != LEVELSUM[l]) { printf("  OP%u level %u SUM table=%llu true=%llu\n", GOP, l,
                                     (unsigned long long)LEVELSUM[l], (unsigned long long)tot); bad = 1; }
  }
  if (bad) { printf("^^^ after op %u\n", GOP); exit(1); }
}
#endif

#if !defined(LOCAL)
struct DUCKDI{unsigned long abi;const char*sp;unsigned long sn;char*op;unsigned long ol,os;char*ep;unsigned long el,es;const char*IB;unsigned long IBl;char*OB;unsigned long OBl;unsigned long tsc;}__attribute__((packed));
extern "C" void __libc_start_main(void*m,int argc,char**argv){
 unsigned long*p=(unsigned long*)(argv+argc+1);while(*p)p++;p++;
 DUCKDI*d=0;for(;p[0];p+=2)if(p[0]==0x6b637564UL){d=(DUCKDI*)p[1];break;}
 gip=(const u8*)d->sp; gob=(u8*)d->op; gEND=gip+d->sn;
 solve();
 d->os=(unsigned long)(gob-(u8*)d->op);
 __asm__ volatile("syscall"::"a"(60),"D"(0):"rcx","r11","memory");
 for(;;);
}
#else
#include <cstdio>
#include <cstdlib>
static u8 obuf[1 << 26];
extern "C" int main() {
  FILE *f = stdin;
  static u8 ibuf[1 << 26];
  size_t got = fread(ibuf, 1, sizeof(ibuf) - 32, f);
  for (u32 i = 0; i < 32; i++) ibuf[got + i] = '\n';
  gip = ibuf; gEND = ibuf + got; gob = obuf;
  solve();
  fwrite(obuf, 1, (size_t)(gob - obuf), stdout);
  return 0;
}
#endif
#ifndef LOCAL
int main(){return 0;}

#endif

评测结果