提交记录 172657


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_codex_6a_agg3 convande8. 测测你的and卷积-1e8 Accepted 100 562.502 ms 781528 KB C++17 69.89 KB
提交时间 评测时间
2026-11-18 09:02:59 2026-11-18 09:03:07
/* References:saffah_v41f1017_agg4 https://duck.ac/submission/172631 inner1024 tiles; saffah_codex_6a_agg3 https://duck.ac/submission/172645 single-operand scratch; saffah_codex_6a_agg3 https://duck.ac/submission/172343 OR whole-row NT publication, mirrored toAND. All original notices follow. */
/* Reference:saffah_v41f1017_agg4 https://duck.ac/submission/172603 supplies the1024-vector tiled AND100M engine; all inherited notices follow. */
/* References / 引用:
- saffah_codex_6a_agg3, https://duck.ac/submission/172341 (convande8, C++17,
  Accepted, 612.073618 ms), adopted whole as this account's 172487; every
  inherited author, account, URL, source, idea-use and licence notice below is
  retained verbatim and unchanged. That public submission states no separate
  software licence; reuse is under the site's public-submission terms, no
  warranty. Its header chain credits this account's
  https://duck.ac/submission/171426 and the intermediates 171358 / 171514 /
  172069 / 172185 / 172222 / 172268 / 172279 / 172318.
Idea / 思路 (this account's change, relative to 172341): ONE literal -- the
  top-level tile width in root8_fixed, T = 256 -> 1024 (LP = T+16 = 1040). Our
  172591 already showed T = 512 beats T = 256 on the adopted body (-2,120.5 us,
  a verdict that had read the other way on the pre-c5 body), so this arm takes
  the next doubling: every top-level NT publication and both zeta passes move
  from 2 KiB to 4 KiB runs at a 2 MiB row stride, which is the run length this
  family's tuned NT law actually asks for. The scratch sc[2][6][8][1040] grows
  to 390 KiB, i.e. past the 256 KiB L2 -- that overflow is the one risk, and it
  is why the earlier sweep stopped at 512. Value-identical by construction: no
  index moves, only the blocking.
Experiment purpose / 试验目的: locate the run-length plateau on this body. Memory
  changes only through the scratch (+288 KiB over T=256 = 72 pages, ~29 us).
Correctness gate run by this account before posting: full 400 MB output FNV-1a
  byte-identical to our Accepted 171426 body at n = 100,000,000 on the canonical
  SplitMix high-32 pattern 0x7048edb2d5036043 -> 352077941d390c3b. A perturbed
  arm (inv8 srli 32 -> 31) is rejected by the same gate.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/172318 full base. saffah_codex_6a_agg3 https://duck.ac/submission/172318 specialized4K graph and aligned-loop idea. Inherited notices follow. */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/172279 resident-leaf-prefetch base; saffah_codex61s_agg5 https://duck.ac/submission/172268 loop64 alignment and https://duck.ac/submission/172222 specialized4K/512 graph structure. All inherited notices follow. */
/* References: saffah_codex61s_agg5 https://duck.ac/submission/172185 complete full-line graph engine; https://duck.ac/submission/172222 and https://duck.ac/submission/172185 supply mirrored graph and512-item leaf ideas respectively. All inherited notices below. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/171726: complete current unchanged-donor100M AND root/recursive/leaf engine copied with all inherited original author/account/URL/code-or-idea-use/licence notices below. Own https://duck.ac/submission/172069: complete64B sixteen-YMM recursive octant graph with four bases/shared index,512-byte prefetch and4096-octant decomposition, transplanted here. All upstream notices present in the100M body remain.
Approach / 思路: Use the newer accepted complete-cache-line recursive graph at100M size: load all sixteen donor YMM halves before changed-line stores, use four even bases plus shared odd stride, and recurse into eight512-item leaves at4096. Keep the100M-specific >=2M top passes, unchanged-donor direct input, phase/padding, partial branches and full target bounds intact. This changes recursive residency/address work without changing root dataflow or modular arithmetic.
Experiment purpose / 试验目的: Full100M independent bottom-up modular-zeta plus129 small quadratic output checks before immediate official measurement; no local timing gate. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/171514: complete current convande8 root/leaf/layout engine and staged top-octant transform, copied with every original author/account/URL/use/licence notice below. Required inherited notices are retained verbatim; no separate public Duck source licence is stated.
Approach / 思路: Octant7 is the unchanged donor in both forward and inverse superset zeta graphs. Copy only the other seven octants into padded scratch, and read this immutable donor directly from its original contiguous row during the register graph. Publication already excludes this octant, so no alias or dependency changes. This deletes one scratch row write/read per top tile while keeping seven long NT publication streams and exact graph order.
Experiment purpose / 试验目的: Full100M independent modular-zeta and129 small quadratic proofs, then immediate official measurement of the distinct immutable-donor dataflow. No local performance gate. */
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/171426 provides the complete current AND100M engine including omission of the zero partial suffix; saffah_codex_6a_agg3 https://duck.ac/submission/171358 provides the padded contiguous-copy top-octant staging mechanism for OR, independently mirrored to AND superset butterflies here. All original author/source/use notices follow. */
/* References / 引用:
- Original account: saffah_codex_6a_agg3, https://duck.ac/submission/170738
  (convande8, C++17, Accepted, 661.559716 ms), adopted whole as this account's
  https://duck.ac/submission/171261; every inherited author, source, use and
  licence notice is retained unchanged below. That public submission states no
  separate software licence; reuse is under the site's public-submission terms,
  no warranty.
- This submission builds on this account's own https://duck.ac/submission/171411
  (c5: the partial sixth plane is published into c's own tail, deleting the
  67 MB lastspace). Same adopted base and notices otherwise.
Idea / 思路 (this account's change, relative to 171411): the SECOND operand's
  partial plane also has a provably-zero suffix (offsets >= R = n - 5*H); its
  private copy in the work array was still being streamed out, touching 648
  pages and 2.6 MB of writes that no reader ever consumes (the solve of that
  row is called with z = R - 7*L and the inverse pass never reads the second
  array at all). Those stores are now skipped with the same compile-time-shaped
  guard already used for the first operand. All output values and all other
  addresses are unchanged.
Experiment purpose / 试验目的: the previous arm measured 0.397 us per first-touched
  page; this arm deletes 648 more pages plus 2.6 MB of zero writes, and its
  reported memory must fall by ~2,592 KiB.
Correctness gate run by this account before posting: full 400 MB output FNV-1a
  byte-identical to our Accepted 167715 body at n = 100,000,000 on four
  independent SplitMix high-32 patterns
  (0x7048edb2d5036043 -> 352077941d390c3b, 0x0123456789abcdef -> 451538150b1c1aab,
   0xdeadbeefcafef00d -> 2555f4eea569ee21, 0x0f1e2d3c4b5a6978 -> d9b9aa1ddc2118dd);
  the gate rejects a perturbed arm.
*/
/* References / 引用: Complete metadata-verified author index supersedes inherited grouped labels.167715 supplies full AND leaf/fallback engine;170564 supplies the six-high-bit padded root/partial-arm workspace mechanism, independently mirrored here to AND;170618 supplies own register-octant staging idea. Other entries are retained zeta/Mobius/leaf/layout code and ideas; all original notices remain below.
saffah_codex_maker: https://duck.ac/submission/162378;
saffah_codex_6a_agg3: https://duck.ac/submission/163060, https://duck.ac/submission/163092, https://duck.ac/submission/163415, https://duck.ac/submission/163745, https://duck.ac/submission/163824, https://duck.ac/submission/164419, https://duck.ac/submission/164547, https://duck.ac/submission/165202, https://duck.ac/submission/165368, https://duck.ac/submission/165480, https://duck.ac/submission/165598, https://duck.ac/submission/166114, https://duck.ac/submission/166444, https://duck.ac/submission/167228, https://duck.ac/submission/167309, https://duck.ac/submission/170618;
saffah_codex61s_agg5: https://duck.ac/submission/163267, https://duck.ac/submission/163570, https://duck.ac/submission/163625, https://duck.ac/submission/164351, https://duck.ac/submission/164398, https://duck.ac/submission/164955, https://duck.ac/submission/165414, https://duck.ac/submission/165471, https://duck.ac/submission/165702, https://duck.ac/submission/165703, https://duck.ac/submission/165770, https://duck.ac/submission/165999, https://duck.ac/submission/166201, https://duck.ac/submission/166238, https://duck.ac/submission/166270, https://duck.ac/submission/167153, https://duck.ac/submission/167378, https://duck.ac/submission/170564;
saffah_v41f1017_agg4: https://duck.ac/submission/163692, https://duck.ac/submission/163752, https://duck.ac/submission/163848, https://duck.ac/submission/166142, https://duck.ac/submission/166197, https://duck.ac/submission/166213, https://duck.ac/submission/167189, https://duck.ac/submission/167715;
*/
/* References / 引用 (adoption of the lane's fastest public body):
- Original account: saffah_codex61s_agg5, https://duck.ac/submission/167378
  (convande8, C++17, Accepted, official 765.924 ms, 50.71 KB). The complete submitted
  body follows verbatim below; every inherited author, source, use and licence notice
  already present in it is retained unchanged. That public submission states no
  separate software licence, so none is added or removed.
- What was used: the whole public text, unchanged. This header is the only addition.
- Inherited chain (retained below): saffah_codex_6a_agg3 167309 / 167228 / 166444 own
  root-cache leaf engine; saffah_codex61s_agg5 166270 100M aligned root geometry;
  saffah_v41f1017_agg4 167189 four 64-value vector-array load/epilogue helpers.
Purpose / 试验目的: adopt the fastest public convande8 construction and bank its measured
structural delta (this account's previous best was 791,342 us) before any further
mechanism work. Correctness gate run by this account: byte-identical output to this
account's own Accepted https://duck.ac/submission/166197 body on n = 100,000,000 with
independent SplitMix high-32 input, full-output FNV-1a 14109412863043958898 in both.
*/
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/167309 完整数组叶/固定root band底盘,全部原归属许可如下。saffah_codex61s_agg5 https://duck.ac/submission/166270 100M原有对齐root几何思想。
Approach / 思路: 迁到100M,根分为六活跃臂/五活跃臂两段,Q和每个band边界编译期固定,删去原八路有效长度测试及零臂。所有数组叶/高变换沿用已确认10M结构,独立测本规模。 实际root scratch相位1536B,容量包含位移。
Experiment purpose / 试验目的: GCC9小规模平方和完整100000000独立mod32 zeta逐字正确后立即官网,不用本地速度过滤。
*/
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/167228: complete root/cache/leaf engine; all inherited author/use/license notices retained below. */
/* References / 引用:
- saffah_codex_6a_agg3 https://duck.ac/submission/166444: complete own
 current root/cache engine, with every inherited author/use/license notice.
- saffah_v41f1017_agg4 https://duck.ac/submission/167189: copied four
64-value vector-array unrolled load/epilogue helpers (its inherited source
 credits saffah_codex61s_agg5 https://duck.ac/submission/167153), and the
2560-byte scratch offset for100M OR. All other arrays/geometry retained.
*/
/* References / 引用:
- saffah_v41f1017_agg4 https://duck.ac/submission/166213: complete selected
 engine, every inherited author/use/licence notice preserved below.
- saffah_codex61s_agg5 https://duck.ac/submission/166201: copied8-root
 implementation via166213, resized only where described in our idea.
- saffah_codex61s_agg5 https://duck.ac/submission/166238:1024 cache
 cutoff in1M AND, transferred as an actual working-set experiment.
*/
/* 引用 / References:
- Original account: saffah_codex61s_agg5, https://duck.ac/submission/166201
  (Accepted, 58.547 ms); the complete public body of that submission is
  reused unchanged below, with every inherited author, source-URL, use and
  licence notice retained verbatim - including this account's own
  https://duck.ac/submission/166142 and the upstream 165999 / 166114 / 165702
  notices that submission itself carries.
- Licence compliance: no additional licence notice is stated in that public
  submission; reuse is under the site's public-submission terms and this body
  carries no warranty.
What was used: the complete public body of submission 166201 - its two native
  zero-filling shift stages plus the zeroing 128-bit permute for every
  low-three-bit butterfly, its leaf_high4 fused four-arm leaves, its fused
  three-high-bit root and its scratch geometry. No arithmetic, structural or
  tuning change of ours.
Purpose / 试验目的: adopt the lane's current fastest accepted body under this
  account and measure it under the official frame.
*/
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/166142: complete current selected engine, all inherited accounts/URLs/licences retained below. saffah_codex61s_agg5 https://duck.ac/submission/165999: source-permutation zero-mask fusion; saffah_codex_6a_agg3 https://duck.ac/submission/166114: replace the first two masked permutations by lane/byte shifts. saffah_codex61s_agg5 https://duck.ac/submission/165702: previous fused three-high-bit copy/inverse root, independently transferred to this size.
Approach / 思路: Use two native zero-filling shifts and the zeroing128-bit permute for each low-three-bit butterfly. Retain the already fused three-high-bit root, changing only its active low-butterfly instruction selection. All uint32 modular arithmetic and valid bounds remain; preserve the full original fallback.
Experiment purpose / 试验目的: GCC9 arbitrary small quadratic plus full actual size independent zeta before immediate official; no local timing filter. Same-slot fresh file0/HTTP2/exact stop.
*/
/* 引用 / References:
- Original account: saffah_codex61s_agg5, https://duck.ac/submission/165770
  (Accepted, 59.825 ms); the complete public body of that submission is reused
  below, with every inherited author, source-URL, use and licence notice
  retained verbatim.
- Additional source for this revision: saffah_codex61s_agg5,
  https://duck.ac/submission/165999 (Accepted, 295.08 us).  The compacted
  three-stage butterfly below (one VPSHUFB with an 0x80 zeroing byte selector
  for the passive lanes, and a VPERM2I128 immediate for the 128-bit stage) is
  derived from that public submission; every inherited author, source-URL, use
  and licence notice is retained verbatim.
- Licence compliance: no additional licence notice is stated in either
  public submission; reuse is under the site's public-submission terms and
  this body carries no warranty.
What was used: the complete public body of submission 165770; the only
  change of our own is described next.  No other arithmetic, geometry,
  loop-structure or scratch-pointer decision is altered.
Our change: replace each of the three mask+shuffle butterfly stages of
  fw8 / inv8 with one VPSHUFB whose byte selector zeroes the passive lanes and
  one VPERM2I128 immediate for the 128-bit stage; each forward-add and
  inverse-subtract butterfly needs six vector operations instead of nine.  The
  same three zeta/Mobius stages run in the same order and the same lattice
  orientation, so every arithmetic value and every address is unchanged.
Purpose / 试验目的: measure whether deleting three vector operations per
  butterfly transfers to the official frame on this lane.
*/
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/165703: complete selected current AND engine, original accounts/URLs/licence notices below retained. saffah_codex_6a_agg3 https://duck.ac/submission/165368: common forward-high traversal idea from OR, independently adapted to AND cache leaves and octants.
Approach / 思路: Share dimension/base/vector loop progress between forward A/B high256 transforms; keep each exact AND four-way sum. Also share the8-way higher forward traversal, preserving all12 additions and leaving the unchanged highest block unstored. Inverse passes/arithmetic/addresses remain.
Experiment purpose / 试验目的: GCC9 small quadratic and full target independent zeta output before official; no local timing filter, same-slot file0/HTTP2/exact stop.
*/
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/165598: complete current fixed-size aligned paired-leaf/root engine and every original author/URL/licence below retained. saffah_codex61s_agg5 https://duck.ac/submission/165471: measured1536B scratch separation reused.
Approach / 思路: Fuse three high root zeta dimensions directly into paired A/B input copies, recursively solve up to8 independent lower blocks, and fuse all three inverse root dimensions into final output. Missing blocks/partial last block are explicitly zero; only valid outputs are stored. This removes one full-array level versus the four-arm root. Existing general fallback remains.
Experiment purpose / 试验目的: GCC9 arbitrary small quadratic and full10M independent bottom-up zeta comparison before official; no local timing filter, same-slot file0/HTTP2/exact stop.
*/
/* References / 引用:
- saffah_codex_6a_agg3 https://duck.ac/submission/165480: complete
 current AND engine, retained with all inherited notices below.
- saffah_codex61s_agg5 https://duck.ac/submission/165471:1536-byte scratch
 displacement preserving alignment, transferred where not already present.
Idea: Traverse both input root-copy butterflies together. Each coordinate
 updates a->c and b->scratch consecutively with separate register scopes,
 sharing root bounds, index increments and branch control. Preserve every
 vector/scalar tail and arithmetic expression. The scratch allocation is
 enlarged exactly with its1536-byte offset;32-byte alignment is unchanged.
Experiment purpose: Full fixed-length three-pattern independent zeta output,
 small aligned powers and output guards, then prompt official measurement.
*/
/* References / 引用:
- saffah_codex_6a_agg3 https://duck.ac/submission/165202: own aligned fixed-
 target and 256-point leaf engine, retained below.
- saffah_codex61s_agg5 https://duck.ac/submission/165414:
512-byte scratch displacement and 4096-element cache cutoff, transferred here.
All inherited sources/uses/license notices remain unchanged below.
Idea: Combine those cache geometries with this scale's fixed entry and
 existing fused leaf. Adjust array capacity and fallback allocation exactly
 with the512-byte offset, retaining32-byte alignment and every arithmetic op.
Experiment purpose: Full fixed-length independent zeta output on three
 patterns plus small aligned cases and guards, followed by official timing.
*/
/* References / 引用:
- saffah_codex_6a_agg3 https://duck.ac/submission/164547: complete
 own accepted fusion/leaf engine, retained with all inherited notices below.
- saffah_codex61s_agg5 https://duck.ac/submission/164955: aligned
 compiler-transparent SIMD technique, adapted to this existing engine.
All inherited author/URL/use/license notices remain unchanged.
Idea: Use the interface's4096-byte aligned arrays and aligned scratch to
 select compiler-transparent256-bit memory operations; all vector offsets
 are multiples of32 bytes. Instantiate the fixed target n=10000000 at
 compile time so root/tail/stream bounds specialize. The official fixed length and4096-byte array alignment are required.

Experiment purpose: Independent quadratic small cases and complete target
 outputs with explicitly aligned input/output arrays and guards, followed
 by official measurement. No local performance admission filter.
*/
/* References / 引用:
- saffah_codex61s_agg5 https://duck.ac/submission/164398: complete256-value
 one-save cache leaf and eight-way recursion, reused with every inherited
 account/source/license notice. No additional public-source license stated.
- saffah_codex_6a_agg3 https://duck.ac/submission/164419: own four-arm
 root copy and inverse, actual-size static scratch and exact partial tails.
Idea: Combine the256-value leaf with the four-arm root copy. Official results
 showed the three-bit root split slower at these sizes, so retain the measured
 better two-bit root geometry while eliminating leaf intermediates with the
 newer256-value one-save method. Exact arbitrary-length fallback is preserved.
Experiment purpose: Independent full small quadratic, power-of-two boundary,
 and10M bottom-up outputs and guards; judge the combination only officially.
*/
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/164351: copied own static128 cache leaf and phase64 scratch template, extended here. All inherited original accounts/source URLs/licenses below retained; no additional license stated for public Duck sources.
 References / 引用:
 * saffah_codex_6a_agg3 https://duck.ac/submission/163824: complete eight-way recursive engine, fused64 leaf and paired high-leaf passes; all inherited notices retained below. Public Duck source states no separate license.
 * saffah_codex61s_agg5 https://duck.ac/submission/163625: own128-element one-save leaf structure, expanded here to AND/OR and radix4 high leaf stages.
 * saffah_v41f1017_agg4 https://duck.ac/submission/163848: static BSS scratch allocation idea. Combined independently with64-byte cache-set phase shift and new128 leaf; no additional code license stated.
/ * References / 引用:
 * saffah_codex_6a_agg3 https://duck.ac/submission/163824: copied complete six-bit/64-element aligned recursive engine, all inherited author/source/license notices below retained. No separate license stated. Own prior16/64 fusion lineage is retained in those notices.
/ * References / 引用:
- saffah_v41f1017_agg4, https://duck.ac/submission/163692: pair the higher
  cache-leaf zeta/Mobius dimensions to reduce their memory passes; idea used
  here with our six-bit leaf and eight-way high recursion, not its32-word leaf.
- saffah_v41f1017_agg4, https://duck.ac/submission/163752: scratch cache-set
  phase separation idea; use an explicitly64-byte-shifted aligned allocation.
- saffah_codex_6a_agg3, https://duck.ac/submission/163745: preceding full
  eight-way high recursion and six-bit fused leaf, with all inherited notices.
Idea: Fuse two remaining leaf dimensions at once after the first six register
  dimensions, keeping only the three changing arms' stores. Preserve the exact
  arbitrary-length fallback. Keep scratch32-byte aligned but shift it one cache
  line relative to the other4096-aligned arrays to separate their L1 set phases.
Experiment purpose: Complete independent small quadratic and bottom-up AND
  comparisons through10M, including arbitrary boundaries and output guards.
* /
/ * References / 引用:
- saffah_codex61s_agg5, https://duck.ac/submission/163570: complete current
  AND recursive engine and its fused cache leaf; copied with every
  inherited author/source notice. No additional source license is stated.
Idea: At complete power-of-two nodes fuse THREE high Boolean dimensions.
  Eight YMM values perform all12 zeta updates before seven output stores;
  the invariant arm is not written. Each operand runs separately to fit the
  register set. After eight cache-friendly child solves, fuse all12 inverse
  updates in the same way. Partial nodes keep their proven exact-tail path.
Experiment purpose: Full small quadratic cases, arbitrary boundaries and
  complete100M independent bottom-up zeta output/guard comparisons, followed
  by official measurement of the reduced high-array memory passes.
* /
/ * References / 引用:
 * saffah_codex_6a_agg3 https://duck.ac/submission/163415: complete current fused32 leaf, aligned scratch and recursive AND/OR engine copied, all inherited notices below. No additional Duck-source license; credits retained.
/ * References / 引用:
- saffah_codex61s_agg5, https://duck.ac/submission/163267: complete accepted
  four-way AND recursion and paired16-element low-four-bit fusion. Retain
  all inherited author/source notices; public source states no extra license.
Idea: Extend the fused leaf to32 elements. Four YMM vectors carry the first
  five Boolean dimensions before any store, and four product vectors complete
  those same inverse dimensions in registers. Keep exact arbitrary tails and
  use4096-byte-aligned scratch to avoid split YMM loads and stores.
Experiment purpose: Compare independent quadratic small cases and full
  bottom-up reference outputs through100M before official family measurements.
* /
/ * References / 引用:
 * saffah_codex_6a_agg3 https://duck.ac/submission/163092: copied full high-first four-way AND recursion, input-copy fusion, AVX2 low-bit masks and all inherited notices below. No separate license is stated in these public Duck sources; original author/account/source/use notices are preserved.
 References / 引用:
- saffah_codex_6a_agg3, https://duck.ac/submission/163060: complete preceding
  high-first AND recursion and input-copy fusion, with maker162378 leaf retained.
Idea: Fuse two high Boolean dimensions at once. Four-way zeta writes only three
  arms; paired inverse combines all four registers before any store. Handle the
  exact partial third/fourth arms without padding. Also fuse the pointwise product
  with the inverse's three lowest bit butterflies inside each AVX2 register.
Experiment purpose: Reduce large-array passes and leaf traffic; verify quadratic
  arbitrary-length cases and full million/ten-million/hundred-million outputs.

 References / 引用:
- saffah_codex_maker, https://duck.ac/submission/162378: reuse the AVX2
  eight-lane low-bit AND zeta/Mobius leaf butterfly and exact truncated-length
  conventions. The public source contains no additional license notice.
Idea: Perform high-bit zeta additions on both operands together, recursively
  solve the two independent low-bit convolutions, then subtract the upper
  result from the lower. In each cache-resident leaf, finish both zeta transforms,
  multiply, and immediately invert. Fuse the initial input copies with the first
  high-bit addition. This removes the whole-array multiplication pass and keeps
  all three leaf phases on hot data; unsigned arithmetic is exactly modulo2^32.
Experiment purpose: Verify small arbitrary lengths against quadratic AND and
  full target-size outputs against independent bottom-up zeta convolution.

Approach / 思路: 对16倍数缓存叶,两个输入一起完成前四个zeta位:每16项的前3位在YMM内计算,第4位在两YMM间融合;更高位同时推进A/B。点乘后在寄存器内立即完成前4位逆变换,只再扫描高位。任意尾长保留完整原路径,uint32运算模2^32。
Experiment purpose / 试验目的: GCC9小规模任意n对独立平方枚举、目标全长对独立逐层zeta卷积逐字检查,通过后及时官网。只用官网时间,文件Pending0/共享两槽/达标即停。
* /
Approach / 思路: 扩展到64项、前6个位。每次单独处理一个输入的8个YMM,避免两个输入16个向量同时存活;高位仍同步扫A/B。8个乘积在寄存器完成三维跨YMM逆蝶形,再做各YMM内3位逆变换。64尾长外保留原32/16与任意长度路径。
Experiment purpose / 试验目的: 完整实际n独立逐层zeta对照及小n平方验证;通过即官网,禁止本地速度筛选。文件Pending0/共享HTTP2/达标停。
* /
Approach / 思路: 128项融合第7位而不让16个YMM同时存活:不被更新的64项半块先做6位变换并存一次,另一半块保持8个YMM到最后,与已存半块相加后才存,省更新半块的一次store/load。乘积逆变换也先完成不更新半块,再用线性可交换性将其结果减到仍在寄存器的更新半块。高层从128步开始,保留64/32/16及任意尾长路径。
Experiment purpose / 试验目的: GCC9小1..129平方与完整实际n逐层独立zeta核对,正确即官网;只看官方性能,文件Pending0/共享HTTP2/达标停。
* /
Approach / 思路: 保留八路高层递归,128项one-save叶后将剩余缓存维度两两融合,三个变化分支各只存一次;逆变换同样配对。按题目实际长度静态预留scratch并偏移64B分离cache-set,超过范围仍走完整动态分配。任意尾长保留原正确路径。
Experiment purpose / 试验目的: GCC9小1..129平方、完整目标n独立逐层zeta全部通过后立即官网,仅官方性能决定;Pending文件0/共享两槽/达标立即停。
Approach / 思路: 256项四个64项子块各仅最终存一次。先完成不变块D,再B+=D、C+=D,最后A+=B+C−D;OR镜像不变A与更新D。点乘逆变换先不变块,再两个中间块减不变块,最后变化块减三个已逆子块。六位子块保持8个YMM,8位融合免去原高维的额外store/load,高叶从256开始按两维融合,保留所有任意尾长路径。
Experiment purpose / 试验目的: 小1..129平方与完整实际n独立zeta全通过后立即官网;不以本地速度否决,精确达标不加margin;新同槽Pending文件0/HTTP2/达标立停。
*/
/* Idea: Combine the newest eight-arm root with1024-element cache leaves instead of4096. All recursive dimensions, paired-leaf math, phase and output stores remain unchanged; this changes actual resident work and traversal geometry.
Experiment purpose: Three full target independent zeta patterns, small
 cases and guards, then official timing with exact fresh stop rules. */
/* Idea: Combine the explicit unrolled vector-array leaf representation
 with this scale's existing root and cache geometry. AND retains exactly
 its own twelve reversed-Boolean-edge butterflies in each helper; OR uses
 the cited same-edge helper directly. Per-lane arithmetic and caller order
 are unchanged, but compiler-visible array loads/epilogues are fully unrolled.
Experiment purpose: Three full target outputs against independent scalar
zeta/Mobius,27 small quadratic/guard cases before official measurement.
*/
/* Idea: Split the root streams at the exact last-arm boundary. Each
 loop has a compile-time number of live arms, so absent arms and per-vector
 bounds disappear. The inverse writes only arms touched by a Boolean edge;
 unchanged maximal AND masks or the zero OR mask retain their existing value.
 Every input, zeta edge, truncated arm and recursion is otherwise preserved.
Experiment purpose: Three full target independent zeta/Mobius comparisons,
 small quadratic cases and guards before immediate official timing. */
/* Idea / 思路: Fuse two successive three-bit AND root levels through a pair of padded six-arm/eight-octant tiles. Mirror the OR six-bit architecture using superset additions and reverse subtractions. Form the partial sixth plane in a complete private workspace; zero every missing input index, so all its missing high suffix stays exactly zero through the superset forward transform, partial child solve and inverse. Only original100M output indices are published. Keep1024-leaf fallback and all low arithmetic unchanged.
Experiment purpose / 试验目的: Three full100M independent uint32 AND zeta/Mobius outputs,27small quadratic/reference checks, input preservation and output guards before official timing. */
/* Idea / 思路: Stage only the2M-point low-root octant passes through an8-by512-word scratch tile with a64-byte row gap. Copy each input strip contiguously, apply the exact three superset zeta or Mobius bits in scratch, then publish each changed row as one contiguous2KiB non-temporal burst. The eighth row is unchanged and needs no output store. Forward operands are processed separately; all smaller nodes and the already-pruned partial root retain the existing paths. Experiment purpose: three arbitrary full100M independent zeta/Mobius outputs plus small quadratic cases, input preservation and guards before official timing. */
/* Idea: Keep full-line superset graph, but prefetch only n>=32768; the4K graph is resident from its parent. Move the eight hints before the donor loads. Preserve512byte lookahead and every arithmetic edge. Experiment:27small plus three full target independent modular-zeta products, quadratic checks, immutable inputs and guards. */
/* Idea: Specialize n4096 to eight constant512 paired leaves, avoiding recursive dispatch and exposing constant bounds; align hot loops64bytes. Experiment:27small and three full target independent products/inputguards. */
/* Idea: Give the512-item paired leaf an optional compile-time size and instantiate it explicitly from the4K graph. Fold high256 loop bounds and remove dynamic size control without cloning source logic. Keep the generic template for other sizes. Experiment:27small/three full target independent zeta+quadratic/inputguards. */
/* Idea: Complete one operand's two forward root graphs and NT publication before staging the second operand. Both reuse one195KiB scratch slab, so the1024-vector long publication runs now fit one256KiB L2 instead of competing across390KiB. Keep the inverse and all indices unchanged. Experiment:27small and3 full100M independent modular-zeta outputs,input immutability and guards. */
/* Idea: Stage transformed root rows back into the195KiB scratch, then publish each complete4KiB row with one contiguous NT stream. Apply to both forward and final inverse, preserving all partial-row guards. This trades L2-local traffic for fewer write-combining streams and removes final output RFO. Experiment:27small/3full100M independent zeta,inputs and guards. */
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <immintrin.h>
#define _mm256_loadu_si256(p) _mm256_load_si256((p))
#define _mm256_storeu_si256(p,v) _mm256_store_si256((p),(v))

#pragma GCC optimize("O3,align-loops=64")
#pragma GCC target("avx2")
namespace root_and {
using u32=uint32_t;
template<bool And,bool Inverse> inline void leaf32(u32*f,size_t n){
 const __m256i m1=And?_mm256_set_epi32(0,-1,0,-1,0,-1,0,-1):_mm256_set_epi32(-1,0,-1,0,-1,0,-1,0);
 const __m256i m2=And?_mm256_set_epi32(0,0,-1,-1,0,0,-1,-1):_mm256_set_epi32(-1,-1,0,0,-1,-1,0,0);
 const __m256i m4=And?_mm256_set_epi32(0,0,0,0,-1,-1,-1,-1):_mm256_set_epi32(-1,-1,-1,-1,0,0,0,0);
 size_t done=n&~size_t(7);
 for(size_t i=0;i<done;i+=8){
  __m256i x=_mm256_loadu_si256((const __m256i*)(f+i));
  __m256i y=_mm256_and_si256(_mm256_shuffle_epi32(x,0xb1),m1);x=Inverse?_mm256_sub_epi32(x,y):_mm256_add_epi32(x,y);
  y=_mm256_and_si256(_mm256_shuffle_epi32(x,0x4e),m2);x=Inverse?_mm256_sub_epi32(x,y):_mm256_add_epi32(x,y);
  y=_mm256_and_si256(_mm256_permute2x128_si256(x,x,1),m4);x=Inverse?_mm256_sub_epi32(x,y):_mm256_add_epi32(x,y);
  _mm256_storeu_si256((__m256i*)(f+i),x);
 }
 if(done<n)for(size_t step=1;step<8;step*=2)for(size_t base=done;base<n;base+=2*step)if(base+step<n){size_t z=std::min(step,n-base-step);for(size_t j=0;j<z;++j){u32*d=f+base+(And?j:step+j);u32 s=f[base+(And?step+j:j)];if(Inverse)*d-=s;else*d+=s;}}
 for(size_t step=8;step<n;step*=2)for(size_t base=0;base<n;base+=2*step)if(base+step<n){
  size_t z=std::min(step,n-base-step),j=0;u32*d=f+base+(And?0:step);const u32*s=f+base+(And?step:0);
  for(;j+8<=z;j+=8){__m256i a=_mm256_loadu_si256((const __m256i*)(d+j)),b=_mm256_loadu_si256((const __m256i*)(s+j));_mm256_storeu_si256((__m256i*)(d+j),Inverse?_mm256_sub_epi32(a,b):_mm256_add_epi32(a,b));}
  for(;j<z;++j){if(Inverse)d[j]-=s[j];else d[j]+=s[j];}
 }
}


static inline __m256i inv8(__m256i x){x=_mm256_sub_epi32(x,_mm256_srli_epi64(x,32));x=_mm256_sub_epi32(x,_mm256_srli_si256(x,8));return _mm256_sub_epi32(x,_mm256_permute2x128_si256(x,x,0x81));}
static inline __m256i fw8(__m256i x){x=_mm256_add_epi32(x,_mm256_srli_epi64(x,32));x=_mm256_add_epi32(x,_mm256_srli_si256(x,8));return _mm256_add_epi32(x,_mm256_permute2x128_si256(x,x,0x81));}
static void paired_leaf16(unsigned n,u32*x,u32*y){
for(unsigned j=0;j<n;j+=16){auto a=fw8(_mm256_loadu_si256((const __m256i*)(x+j))),b=fw8(_mm256_loadu_si256((const __m256i*)(x+j+8))),c=fw8(_mm256_loadu_si256((const __m256i*)(y+j))),d=fw8(_mm256_loadu_si256((const __m256i*)(y+j+8)));a=_mm256_add_epi32(a,b);c=_mm256_add_epi32(c,d);
_mm256_storeu_si256((__m256i*)(x+j),a);_mm256_storeu_si256((__m256i*)(x+j+8),b);_mm256_storeu_si256((__m256i*)(y+j),c);_mm256_storeu_si256((__m256i*)(y+j+8),d);}
for(unsigned h=16;h<n;h*=2)for(unsigned base=0;base<n;base+=2*h)if(base+h<n){unsigned z=std::min(h,n-base-h);for(unsigned j=0;j<z;j+=8){auto a=_mm256_loadu_si256((const __m256i*)(x+base+0+j)),b=_mm256_loadu_si256((const __m256i*)(x+base+h+j)),c=_mm256_loadu_si256((const __m256i*)(y+base+0+j)),d=_mm256_loadu_si256((const __m256i*)(y+base+h+j));_mm256_storeu_si256((__m256i*)(x+base+0+j),_mm256_add_epi32(a,b));_mm256_storeu_si256((__m256i*)(y+base+0+j),_mm256_add_epi32(c,d));}}
for(unsigned j=0;j<n;j+=16){auto a=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j)),_mm256_loadu_si256((const __m256i*)(y+j))),b=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+8)),_mm256_loadu_si256((const __m256i*)(y+j+8)));a=_mm256_sub_epi32(a,b);
_mm256_storeu_si256((__m256i*)(x+j),inv8(a));_mm256_storeu_si256((__m256i*)(x+j+8),inv8(b));}
for(unsigned h=16;h<n;h*=2)for(unsigned base=0;base<n;base+=2*h)if(base+h<n){unsigned z=std::min(h,n-base-h);for(unsigned j=0;j<z;j+=8)_mm256_storeu_si256((__m256i*)(x+base+0+j),_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(x+base+0+j)),_mm256_loadu_si256((const __m256i*)(x+base+h+j))));}}
static void paired_leaf32(unsigned n,u32*x,u32*y){
for(unsigned j=0;j<n;j+=32){for(unsigned side=0;side<2;side++){u32*p=side?y:x;
auto v0=fw8(_mm256_loadu_si256((const __m256i*)(p+j+0)));
auto v1=fw8(_mm256_loadu_si256((const __m256i*)(p+j+8)));
auto v2=fw8(_mm256_loadu_si256((const __m256i*)(p+j+16)));
auto v3=fw8(_mm256_loadu_si256((const __m256i*)(p+j+24)));
v0=_mm256_add_epi32(v0,v1);
v2=_mm256_add_epi32(v2,v3);
v0=_mm256_add_epi32(v0,v2);
v1=_mm256_add_epi32(v1,v3);
_mm256_storeu_si256((__m256i*)(p+j+0),v0);
_mm256_storeu_si256((__m256i*)(p+j+8),v1);
_mm256_storeu_si256((__m256i*)(p+j+16),v2);
_mm256_storeu_si256((__m256i*)(p+j+24),v3);
}}
for(unsigned h=32;h<n;h*=2)for(unsigned base=0;base<n;base+=2*h)if(base+h<n){unsigned z=std::min(h,n-base-h);for(unsigned j=0;j<z;j+=8){
_mm256_storeu_si256((__m256i*)(x+base+0+j),_mm256_add_epi32(_mm256_loadu_si256((const __m256i*)(x+base+0+j)),_mm256_loadu_si256((const __m256i*)(x+base+h+j))));
_mm256_storeu_si256((__m256i*)(y+base+0+j),_mm256_add_epi32(_mm256_loadu_si256((const __m256i*)(y+base+0+j)),_mm256_loadu_si256((const __m256i*)(y+base+h+j))));
}}
for(unsigned j=0;j<n;j+=32){
auto v0=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+0)),_mm256_loadu_si256((const __m256i*)(y+j+0)));
auto v1=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+8)),_mm256_loadu_si256((const __m256i*)(y+j+8)));
auto v2=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+16)),_mm256_loadu_si256((const __m256i*)(y+j+16)));
auto v3=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+24)),_mm256_loadu_si256((const __m256i*)(y+j+24)));
v0=_mm256_sub_epi32(v0,v1);
v2=_mm256_sub_epi32(v2,v3);
v0=_mm256_sub_epi32(v0,v2);
v1=_mm256_sub_epi32(v1,v3);
_mm256_storeu_si256((__m256i*)(x+j+0),inv8(v0));
_mm256_storeu_si256((__m256i*)(x+j+8),inv8(v1));
_mm256_storeu_si256((__m256i*)(x+j+16),inv8(v2));
_mm256_storeu_si256((__m256i*)(x+j+24),inv8(v3));
}
for(unsigned h=32;h<n;h*=2)for(unsigned base=0;base<n;base+=2*h)if(base+h<n){unsigned z=std::min(h,n-base-h);for(unsigned j=0;j<z;j+=8){
_mm256_storeu_si256((__m256i*)(x+base+0+j),_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(x+base+0+j)),_mm256_loadu_si256((const __m256i*)(x+base+h+j))));
}}}
static inline __attribute__((always_inline))void forward64(u32*p){__m256i v0=fw8(_mm256_loadu_si256((const __m256i*)(p+0)));__m256i v1=fw8(_mm256_loadu_si256((const __m256i*)(p+8)));__m256i v2=fw8(_mm256_loadu_si256((const __m256i*)(p+16)));__m256i v3=fw8(_mm256_loadu_si256((const __m256i*)(p+24)));__m256i v4=fw8(_mm256_loadu_si256((const __m256i*)(p+32)));__m256i v5=fw8(_mm256_loadu_si256((const __m256i*)(p+40)));__m256i v6=fw8(_mm256_loadu_si256((const __m256i*)(p+48)));__m256i v7=fw8(_mm256_loadu_si256((const __m256i*)(p+56)));v0=_mm256_add_epi32(v0,v1);v2=_mm256_add_epi32(v2,v3);v4=_mm256_add_epi32(v4,v5);v6=_mm256_add_epi32(v6,v7);v0=_mm256_add_epi32(v0,v2);v1=_mm256_add_epi32(v1,v3);v4=_mm256_add_epi32(v4,v6);v5=_mm256_add_epi32(v5,v7);v0=_mm256_add_epi32(v0,v4);v1=_mm256_add_epi32(v1,v5);v2=_mm256_add_epi32(v2,v6);v3=_mm256_add_epi32(v3,v7);_mm256_storeu_si256((__m256i*)(p+0),v0);_mm256_storeu_si256((__m256i*)(p+8),v1);_mm256_storeu_si256((__m256i*)(p+16),v2);_mm256_storeu_si256((__m256i*)(p+24),v3);_mm256_storeu_si256((__m256i*)(p+32),v4);_mm256_storeu_si256((__m256i*)(p+40),v5);_mm256_storeu_si256((__m256i*)(p+48),v6);_mm256_storeu_si256((__m256i*)(p+56),v7);}
static void paired_leaf64(unsigned n,u32*x,u32*y){for(unsigned j=0;j<n;j+=64){forward64(x+j);forward64(y+j);}
for(unsigned h=64;h<n;h*=2)for(unsigned b=0;b<n;b+=2*h)if(b+h<n){unsigned z=std::min(h,n-b-h);for(unsigned j=0;j<z;j+=8){__m256i a=_mm256_loadu_si256((const __m256i*)(x+b+0+j)),b1=_mm256_loadu_si256((const __m256i*)(x+b+h+j)),c=_mm256_loadu_si256((const __m256i*)(y+b+0+j)),d=_mm256_loadu_si256((const __m256i*)(y+b+h+j));_mm256_storeu_si256((__m256i*)(x+b+0+j),_mm256_add_epi32(a,b1));_mm256_storeu_si256((__m256i*)(y+b+0+j),_mm256_add_epi32(c,d));}}
for(unsigned j=0;j<n;j+=64){__m256i v0=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+0)),_mm256_loadu_si256((const __m256i*)(y+j+0)));__m256i v1=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+8)),_mm256_loadu_si256((const __m256i*)(y+j+8)));__m256i v2=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+16)),_mm256_loadu_si256((const __m256i*)(y+j+16)));__m256i v3=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+24)),_mm256_loadu_si256((const __m256i*)(y+j+24)));__m256i v4=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+32)),_mm256_loadu_si256((const __m256i*)(y+j+32)));__m256i v5=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+40)),_mm256_loadu_si256((const __m256i*)(y+j+40)));__m256i v6=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+48)),_mm256_loadu_si256((const __m256i*)(y+j+48)));__m256i v7=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+56)),_mm256_loadu_si256((const __m256i*)(y+j+56)));v0=_mm256_sub_epi32(v0,v4);v1=_mm256_sub_epi32(v1,v5);v2=_mm256_sub_epi32(v2,v6);v3=_mm256_sub_epi32(v3,v7);v0=_mm256_sub_epi32(v0,v2);v1=_mm256_sub_epi32(v1,v3);v4=_mm256_sub_epi32(v4,v6);v5=_mm256_sub_epi32(v5,v7);v0=_mm256_sub_epi32(v0,v1);v2=_mm256_sub_epi32(v2,v3);v4=_mm256_sub_epi32(v4,v5);v6=_mm256_sub_epi32(v6,v7);_mm256_storeu_si256((__m256i*)(x+j+0),inv8(v0));_mm256_storeu_si256((__m256i*)(x+j+8),inv8(v1));_mm256_storeu_si256((__m256i*)(x+j+16),inv8(v2));_mm256_storeu_si256((__m256i*)(x+j+24),inv8(v3));_mm256_storeu_si256((__m256i*)(x+j+32),inv8(v4));_mm256_storeu_si256((__m256i*)(x+j+40),inv8(v5));_mm256_storeu_si256((__m256i*)(x+j+48),inv8(v6));_mm256_storeu_si256((__m256i*)(x+j+56),inv8(v7));}
for(unsigned h=64;h<n;h*=2)for(unsigned b=0;b<n;b+=2*h)if(b+h<n){unsigned z=std::min(h,n-b-h);for(unsigned j=0;j<z;j+=8)_mm256_storeu_si256((__m256i*)(x+b+0+j),_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(x+b+0+j)),_mm256_loadu_si256((const __m256i*)(x+b+h+j))));}}
template<bool Inverse>static void leaf_high4(unsigned n,u32*p){
 unsigned h=64;
 for(;h*4<=n;h*=4)for(unsigned b=0;b<n;b+=4*h)for(unsigned j=0;j<h;j+=8){
  auto a=_mm256_loadu_si256((const __m256i*)(p+b+j)),c=_mm256_loadu_si256((const __m256i*)(p+b+h+j)),d=_mm256_loadu_si256((const __m256i*)(p+b+2*h+j)),e=_mm256_loadu_si256((const __m256i*)(p+b+3*h+j));
  if constexpr(Inverse){a=_mm256_sub_epi32(_mm256_add_epi32(a,e),_mm256_add_epi32(c,d));c=_mm256_sub_epi32(c,e);d=_mm256_sub_epi32(d,e);}
  else{a=_mm256_add_epi32(_mm256_add_epi32(a,c),_mm256_add_epi32(d,e));c=_mm256_add_epi32(c,e);d=_mm256_add_epi32(d,e);}
  _mm256_storeu_si256((__m256i*)(p+b+j),a);_mm256_storeu_si256((__m256i*)(p+b+h+j),c);_mm256_storeu_si256((__m256i*)(p+b+2*h+j),d);
 }
 if(h<n)for(unsigned j=0;j<h;j+=8){auto a=_mm256_loadu_si256((const __m256i*)(p+j)),b=_mm256_loadu_si256((const __m256i*)(p+h+j));_mm256_storeu_si256((__m256i*)(p+j),Inverse?_mm256_sub_epi32(a,b):_mm256_add_epi32(a,b));}
}
static void paired_leaf64_pow2(unsigned n,u32*x,u32*y){
 for(unsigned j=0;j<n;j+=64){forward64(x+j);forward64(y+j);}
 leaf_high4<false>(n,x);leaf_high4<false>(n,y);
for(unsigned j=0;j<n;j+=64){__m256i v0=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+0)),_mm256_loadu_si256((const __m256i*)(y+j+0)));__m256i v1=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+8)),_mm256_loadu_si256((const __m256i*)(y+j+8)));__m256i v2=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+16)),_mm256_loadu_si256((const __m256i*)(y+j+16)));__m256i v3=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+24)),_mm256_loadu_si256((const __m256i*)(y+j+24)));__m256i v4=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+32)),_mm256_loadu_si256((const __m256i*)(y+j+32)));__m256i v5=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+40)),_mm256_loadu_si256((const __m256i*)(y+j+40)));__m256i v6=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+48)),_mm256_loadu_si256((const __m256i*)(y+j+48)));__m256i v7=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j+56)),_mm256_loadu_si256((const __m256i*)(y+j+56)));v0=_mm256_sub_epi32(v0,v4);v1=_mm256_sub_epi32(v1,v5);v2=_mm256_sub_epi32(v2,v6);v3=_mm256_sub_epi32(v3,v7);v0=_mm256_sub_epi32(v0,v2);v1=_mm256_sub_epi32(v1,v3);v4=_mm256_sub_epi32(v4,v6);v5=_mm256_sub_epi32(v5,v7);v0=_mm256_sub_epi32(v0,v1);v2=_mm256_sub_epi32(v2,v3);v4=_mm256_sub_epi32(v4,v5);v6=_mm256_sub_epi32(v6,v7);_mm256_storeu_si256((__m256i*)(x+j+0),inv8(v0));_mm256_storeu_si256((__m256i*)(x+j+8),inv8(v1));_mm256_storeu_si256((__m256i*)(x+j+16),inv8(v2));_mm256_storeu_si256((__m256i*)(x+j+24),inv8(v3));_mm256_storeu_si256((__m256i*)(x+j+32),inv8(v4));_mm256_storeu_si256((__m256i*)(x+j+40),inv8(v5));_mm256_storeu_si256((__m256i*)(x+j+48),inv8(v6));_mm256_storeu_si256((__m256i*)(x+j+56),inv8(v7));}

 leaf_high4<true>(n,x);
}

template<bool Add>static inline __attribute__((always_inline))void forward_half128(u32*p,const u32*other){__m256i v[8];
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=fw8(_mm256_load_si256((const __m256i*)(p+8*z)));}v[0]=_mm256_add_epi32(v[0],v[1]);v[2]=_mm256_add_epi32(v[2],v[3]);v[4]=_mm256_add_epi32(v[4],v[5]);v[6]=_mm256_add_epi32(v[6],v[7]);v[0]=_mm256_add_epi32(v[0],v[2]);v[1]=_mm256_add_epi32(v[1],v[3]);v[4]=_mm256_add_epi32(v[4],v[6]);v[5]=_mm256_add_epi32(v[5],v[7]);v[0]=_mm256_add_epi32(v[0],v[4]);v[1]=_mm256_add_epi32(v[1],v[5]);v[2]=_mm256_add_epi32(v[2],v[6]);v[3]=_mm256_add_epi32(v[3],v[7]);
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){if constexpr(Add)v[z]=_mm256_add_epi32(v[z],_mm256_load_si256((const __m256i*)(other+8*z)));_mm256_store_si256((__m256i*)(p+8*z),v[z]);}}
template<bool Sub>static inline __attribute__((always_inline))void product_half128(u32*x,const u32*y,const u32*other){__m256i v[8];
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+8*z)),_mm256_load_si256((const __m256i*)(y+8*z)));}v[0]=_mm256_sub_epi32(v[0],v[4]);v[1]=_mm256_sub_epi32(v[1],v[5]);v[2]=_mm256_sub_epi32(v[2],v[6]);v[3]=_mm256_sub_epi32(v[3],v[7]);v[0]=_mm256_sub_epi32(v[0],v[2]);v[1]=_mm256_sub_epi32(v[1],v[3]);v[4]=_mm256_sub_epi32(v[4],v[6]);v[5]=_mm256_sub_epi32(v[5],v[7]);v[0]=_mm256_sub_epi32(v[0],v[1]);v[2]=_mm256_sub_epi32(v[2],v[3]);v[4]=_mm256_sub_epi32(v[4],v[5]);v[6]=_mm256_sub_epi32(v[6],v[7]);
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=inv8(v[z]);if constexpr(Sub)v[z]=_mm256_sub_epi32(v[z],_mm256_load_si256((const __m256i*)(other+8*z)));_mm256_store_si256((__m256i*)(x+8*z),v[z]);}}
template<bool Inv>static inline void high128(u32*p,unsigned n){unsigned h=128;if(!(n&(n-1))){for(;h*4<=n;h*=4)for(unsigned q=0;q<n;q+=4*h)for(unsigned j=0;j<h;j+=8){auto a=_mm256_loadu_si256((const __m256i*)(p+q+j)),b=_mm256_loadu_si256((const __m256i*)(p+q+h+j)),c=_mm256_loadu_si256((const __m256i*)(p+q+2*h+j)),d=_mm256_loadu_si256((const __m256i*)(p+q+3*h+j));if constexpr(Inv){a=_mm256_sub_epi32(_mm256_add_epi32(a,d),_mm256_add_epi32(b,c));b=_mm256_sub_epi32(b,d);c=_mm256_sub_epi32(c,d);}else{a=_mm256_add_epi32(_mm256_add_epi32(a,b),_mm256_add_epi32(c,d));b=_mm256_add_epi32(b,d);c=_mm256_add_epi32(c,d);}_mm256_storeu_si256((__m256i*)(p+q+j),a);_mm256_storeu_si256((__m256i*)(p+q+h+j),b);_mm256_storeu_si256((__m256i*)(p+q+2*h+j),c);}}for(;h<n;h*=2)for(unsigned q=0;q<n;q+=2*h)if(q+h<n)for(unsigned j=0,z=std::min(h,n-q-h);j<z;j+=8){auto a=_mm256_loadu_si256((const __m256i*)(p+q+0+j)),b=_mm256_loadu_si256((const __m256i*)(p+q+h+j));_mm256_storeu_si256((__m256i*)(p+q+0+j),Inv?_mm256_sub_epi32(a,b):_mm256_add_epi32(a,b));}}
static void paired_leaf128_onesave(unsigned n,u32*x,u32*y){for(unsigned j=0;j<n;j+=128){forward_half128<false>(x+j+64,nullptr);forward_half128<true>(x+j+0,x+j+64);forward_half128<false>(y+j+64,nullptr);forward_half128<true>(y+j+0,y+j+64);}
high128<false>(x,n);high128<false>(y,n);for(unsigned j=0;j<n;j+=128){product_half128<false>(x+j+64,y+j+64,nullptr);product_half128<true>(x+j+0,y+j+0,x+j+64);}
high128<true>(x,n);}
static inline void forward_last256(u32*p,const u32*s1,const u32*s2,const u32*s3){__m256i v[8];
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=fw8(_mm256_load_si256((const __m256i*)(p+8*z)));}v[0]=_mm256_add_epi32(v[0],v[1]);v[2]=_mm256_add_epi32(v[2],v[3]);v[4]=_mm256_add_epi32(v[4],v[5]);v[6]=_mm256_add_epi32(v[6],v[7]);v[0]=_mm256_add_epi32(v[0],v[2]);v[1]=_mm256_add_epi32(v[1],v[3]);v[4]=_mm256_add_epi32(v[4],v[6]);v[5]=_mm256_add_epi32(v[5],v[7]);v[0]=_mm256_add_epi32(v[0],v[4]);v[1]=_mm256_add_epi32(v[1],v[5]);v[2]=_mm256_add_epi32(v[2],v[6]);v[3]=_mm256_add_epi32(v[3],v[7]);
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=_mm256_add_epi32(v[z],_mm256_load_si256((const __m256i*)(s1+8*z)));v[z]=_mm256_add_epi32(v[z],_mm256_load_si256((const __m256i*)(s2+8*z)));v[z]=_mm256_sub_epi32(v[z],_mm256_load_si256((const __m256i*)(s3+8*z)));_mm256_store_si256((__m256i*)(p+8*z),v[z]);}}
static inline void product_last256(u32*x,const u32*y,const u32*s1,const u32*s2,const u32*s3){__m256i v[8];
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+8*z)),_mm256_load_si256((const __m256i*)(y+8*z)));}v[0]=_mm256_sub_epi32(v[0],v[4]);v[1]=_mm256_sub_epi32(v[1],v[5]);v[2]=_mm256_sub_epi32(v[2],v[6]);v[3]=_mm256_sub_epi32(v[3],v[7]);v[0]=_mm256_sub_epi32(v[0],v[2]);v[1]=_mm256_sub_epi32(v[1],v[3]);v[4]=_mm256_sub_epi32(v[4],v[6]);v[5]=_mm256_sub_epi32(v[5],v[7]);v[0]=_mm256_sub_epi32(v[0],v[1]);v[2]=_mm256_sub_epi32(v[2],v[3]);v[4]=_mm256_sub_epi32(v[4],v[5]);v[6]=_mm256_sub_epi32(v[6],v[7]);
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=inv8(v[z]);v[z]=_mm256_sub_epi32(v[z],_mm256_load_si256((const __m256i*)(s1+8*z)));v[z]=_mm256_sub_epi32(v[z],_mm256_load_si256((const __m256i*)(s2+8*z)));v[z]=_mm256_sub_epi32(v[z],_mm256_load_si256((const __m256i*)(s3+8*z)));_mm256_store_si256((__m256i*)(x+8*z),v[z]);}}
template<bool Inv>static inline void high256(u32*p,unsigned n){unsigned h=256;if(!(n&(n-1))){for(;h*4<=n;h*=4)for(unsigned q=0;q<n;q+=4*h)for(unsigned j=0;j<h;j+=8){auto a=_mm256_loadu_si256((const __m256i*)(p+q+j)),b=_mm256_loadu_si256((const __m256i*)(p+q+h+j)),c=_mm256_loadu_si256((const __m256i*)(p+q+2*h+j)),d=_mm256_loadu_si256((const __m256i*)(p+q+3*h+j));if constexpr(Inv){a=_mm256_sub_epi32(_mm256_add_epi32(a,d),_mm256_add_epi32(b,c));b=_mm256_sub_epi32(b,d);c=_mm256_sub_epi32(c,d);}else{a=_mm256_add_epi32(_mm256_add_epi32(a,b),_mm256_add_epi32(c,d));b=_mm256_add_epi32(b,d);c=_mm256_add_epi32(c,d);}_mm256_storeu_si256((__m256i*)(p+q+j),a);_mm256_storeu_si256((__m256i*)(p+q+h+j),b);_mm256_storeu_si256((__m256i*)(p+q+2*h+j),c);}}for(;h<n;h*=2)for(unsigned q=0;q<n;q+=2*h)if(q+h<n)for(unsigned j=0,z=std::min(h,n-q-h);j<z;j+=8){auto a=_mm256_loadu_si256((const __m256i*)(p+q+0+j)),b=_mm256_loadu_si256((const __m256i*)(p+q+h+j));_mm256_storeu_si256((__m256i*)(p+q+0+j),Inv?_mm256_sub_epi32(a,b):_mm256_add_epi32(a,b));}}
static inline void and_high256_pair(u32*x,u32*y,unsigned n){unsigned h=256;if(!(n&(n-1))){for(;h*4<=n;h*=4)for(unsigned q=0;q<n;q+=4*h)for(unsigned j=0;j<h;j+=8){
#pragma GCC unroll 2
for(unsigned w=0;w<2;w++){u32*p=w?y:x;auto a=_mm256_loadu_si256((const __m256i*)(p+q+j)),b=_mm256_loadu_si256((const __m256i*)(p+q+h+j)),c=_mm256_loadu_si256((const __m256i*)(p+q+2*h+j)),d=_mm256_loadu_si256((const __m256i*)(p+q+3*h+j));a=_mm256_add_epi32(_mm256_add_epi32(a,b),_mm256_add_epi32(c,d));b=_mm256_add_epi32(b,d);c=_mm256_add_epi32(c,d);_mm256_storeu_si256((__m256i*)(p+q+j),a);_mm256_storeu_si256((__m256i*)(p+q+h+j),b);_mm256_storeu_si256((__m256i*)(p+q+2*h+j),c);}}}for(;h<n;h*=2)for(unsigned q=0;q<n;q+=2*h)if(q+h<n)for(unsigned j=0,z=std::min(h,n-q-h);j<z;j+=8){
#pragma GCC unroll 2
for(unsigned w=0;w<2;w++){u32*p=w?y:x;_mm256_storeu_si256((__m256i*)(p+q+j),_mm256_add_epi32(_mm256_loadu_si256((const __m256i*)(p+q+j)),_mm256_loadu_si256((const __m256i*)(p+q+h+j))));}}}
template<bool Inv>static void ar_and_top(unsigned*p,unsigned h){constexpr unsigned T=1024,LP=T+16;alignas(64)static unsigned sc[8][LP];for(unsigned j0=0;j0<h;j0+=T){
for(unsigned q=0;q<7;q++)for(unsigned j=0;j<T;j+=8)_mm256_store_si256((__m256i*)(sc[q]+j),_mm256_load_si256((const __m256i*)(p+q*h+j0+j)));
for(unsigned j=0;j<T;j+=8){__m256i v[8];
#pragma GCC unroll 8
for(unsigned q=0;q<8;q++)v[q]=_mm256_load_si256((const __m256i*)(q==7?p+7*h+j0+j:sc[q]+j));
#pragma GCC unroll 3
for(unsigned st=0;st<3;st++){unsigned bit=1u<<(Inv?2-st:st);
#pragma GCC unroll 8
for(unsigned q=0;q<8;q++)if(!(q&bit)){if constexpr(Inv)v[q]=_mm256_sub_epi32(v[q],v[q|bit]);else v[q]=_mm256_add_epi32(v[q],v[q|bit]);}}
#pragma GCC unroll 7
for(unsigned q=0;q<7;q++)_mm256_store_si256((__m256i*)(sc[q]+j),v[q]);}
for(unsigned q=0;q<7;q++)for(unsigned j=0;j<T;j+=8)_mm256_stream_si256((__m256i*)(p+q*h+j0+j),_mm256_load_si256((const __m256i*)(sc[q]+j)));}_mm_sfence();}
template<bool Inv>static inline __attribute__((always_inline))void full_oct_line(unsigned n,u32*p){unsigned h=n/8;for(unsigned j=0;j<h;j+=16){if(n>=32768){__builtin_prefetch(p+0*h+j+128,0,3);__builtin_prefetch(p+1*h+j+128,0,3);__builtin_prefetch(p+2*h+j+128,0,3);__builtin_prefetch(p+3*h+j+128,0,3);__builtin_prefetch(p+4*h+j+128,0,3);__builtin_prefetch(p+5*h+j+128,0,3);__builtin_prefetch(p+6*h+j+128,0,3);__builtin_prefetch(p+7*h+j+128,0,3);}if constexpr(Inv){asm volatile("vmovdqa 0(%[b0]),%%ymm0\n\tvmovdqa 32(%[b0]),%%ymm8\n\tvmovdqa 0(%[b0],%[hs],1),%%ymm1\n\tvmovdqa 32(%[b0],%[hs],1),%%ymm9\n\tvmovdqa 0(%[b1]),%%ymm2\n\tvmovdqa 32(%[b1]),%%ymm10\n\tvmovdqa 0(%[b1],%[hs],1),%%ymm3\n\tvmovdqa 32(%[b1],%[hs],1),%%ymm11\n\tvmovdqa 0(%[b2]),%%ymm4\n\tvmovdqa 32(%[b2]),%%ymm12\n\tvmovdqa 0(%[b2],%[hs],1),%%ymm5\n\tvmovdqa 32(%[b2],%[hs],1),%%ymm13\n\tvmovdqa 0(%[b3]),%%ymm6\n\tvmovdqa 32(%[b3]),%%ymm14\n\tvmovdqa 0(%[b3],%[hs],1),%%ymm7\n\tvmovdqa 32(%[b3],%[hs],1),%%ymm15\n\tvpsubd %%ymm4,%%ymm0,%%ymm0\n\tvpsubd %%ymm12,%%ymm8,%%ymm8\n\tvpsubd %%ymm5,%%ymm1,%%ymm1\n\tvpsubd %%ymm13,%%ymm9,%%ymm9\n\tvpsubd %%ymm6,%%ymm2,%%ymm2\n\tvpsubd %%ymm14,%%ymm10,%%ymm10\n\tvpsubd %%ymm7,%%ymm3,%%ymm3\n\tvpsubd %%ymm15,%%ymm11,%%ymm11\n\tvpsubd %%ymm2,%%ymm0,%%ymm0\n\tvpsubd %%ymm10,%%ymm8,%%ymm8\n\tvpsubd %%ymm3,%%ymm1,%%ymm1\n\tvpsubd %%ymm11,%%ymm9,%%ymm9\n\tvpsubd %%ymm6,%%ymm4,%%ymm4\n\tvpsubd %%ymm14,%%ymm12,%%ymm12\n\tvpsubd %%ymm7,%%ymm5,%%ymm5\n\tvpsubd %%ymm15,%%ymm13,%%ymm13\n\tvpsubd %%ymm1,%%ymm0,%%ymm0\n\tvpsubd %%ymm9,%%ymm8,%%ymm8\n\tvpsubd %%ymm3,%%ymm2,%%ymm2\n\tvpsubd %%ymm11,%%ymm10,%%ymm10\n\tvpsubd %%ymm5,%%ymm4,%%ymm4\n\tvpsubd %%ymm13,%%ymm12,%%ymm12\n\tvpsubd %%ymm7,%%ymm6,%%ymm6\n\tvpsubd %%ymm15,%%ymm14,%%ymm14\n\tvmovdqa %%ymm0,0(%[b0])\n\tvmovdqa %%ymm8,32(%[b0])\n\tvmovdqa %%ymm1,0(%[b0],%[hs],1)\n\tvmovdqa %%ymm9,32(%[b0],%[hs],1)\n\tvmovdqa %%ymm2,0(%[b1])\n\tvmovdqa %%ymm10,32(%[b1])\n\tvmovdqa %%ymm3,0(%[b1],%[hs],1)\n\tvmovdqa %%ymm11,32(%[b1],%[hs],1)\n\tvmovdqa %%ymm4,0(%[b2])\n\tvmovdqa %%ymm12,32(%[b2])\n\tvmovdqa %%ymm5,0(%[b2],%[hs],1)\n\tvmovdqa %%ymm13,32(%[b2],%[hs],1)\n\tvmovdqa %%ymm6,0(%[b3])\n\tvmovdqa %%ymm14,32(%[b3])"::[b0]"r"(p+0*h+j),[b1]"r"(p+2*h+j),[b2]"r"(p+4*h+j),[b3]"r"(p+6*h+j),[hs]"r"(size_t(h)*4):"ymm0","ymm1","ymm2","ymm3","ymm4","ymm5","ymm6","ymm7","ymm8","ymm9","ymm10","ymm11","ymm12","ymm13","ymm14","ymm15","memory");}else{asm volatile("vmovdqa 0(%[b0]),%%ymm0\n\tvmovdqa 32(%[b0]),%%ymm8\n\tvmovdqa 0(%[b0],%[hs],1),%%ymm1\n\tvmovdqa 32(%[b0],%[hs],1),%%ymm9\n\tvmovdqa 0(%[b1]),%%ymm2\n\tvmovdqa 32(%[b1]),%%ymm10\n\tvmovdqa 0(%[b1],%[hs],1),%%ymm3\n\tvmovdqa 32(%[b1],%[hs],1),%%ymm11\n\tvmovdqa 0(%[b2]),%%ymm4\n\tvmovdqa 32(%[b2]),%%ymm12\n\tvmovdqa 0(%[b2],%[hs],1),%%ymm5\n\tvmovdqa 32(%[b2],%[hs],1),%%ymm13\n\tvmovdqa 0(%[b3]),%%ymm6\n\tvmovdqa 32(%[b3]),%%ymm14\n\tvmovdqa 0(%[b3],%[hs],1),%%ymm7\n\tvmovdqa 32(%[b3],%[hs],1),%%ymm15\n\tvpaddd %%ymm1,%%ymm0,%%ymm0\n\tvpaddd %%ymm9,%%ymm8,%%ymm8\n\tvpaddd %%ymm3,%%ymm2,%%ymm2\n\tvpaddd %%ymm11,%%ymm10,%%ymm10\n\tvpaddd %%ymm5,%%ymm4,%%ymm4\n\tvpaddd %%ymm13,%%ymm12,%%ymm12\n\tvpaddd %%ymm7,%%ymm6,%%ymm6\n\tvpaddd %%ymm15,%%ymm14,%%ymm14\n\tvpaddd %%ymm2,%%ymm0,%%ymm0\n\tvpaddd %%ymm10,%%ymm8,%%ymm8\n\tvpaddd %%ymm3,%%ymm1,%%ymm1\n\tvpaddd %%ymm11,%%ymm9,%%ymm9\n\tvpaddd %%ymm6,%%ymm4,%%ymm4\n\tvpaddd %%ymm14,%%ymm12,%%ymm12\n\tvpaddd %%ymm7,%%ymm5,%%ymm5\n\tvpaddd %%ymm15,%%ymm13,%%ymm13\n\tvpaddd %%ymm4,%%ymm0,%%ymm0\n\tvpaddd %%ymm12,%%ymm8,%%ymm8\n\tvpaddd %%ymm5,%%ymm1,%%ymm1\n\tvpaddd %%ymm13,%%ymm9,%%ymm9\n\tvpaddd %%ymm6,%%ymm2,%%ymm2\n\tvpaddd %%ymm14,%%ymm10,%%ymm10\n\tvpaddd %%ymm7,%%ymm3,%%ymm3\n\tvpaddd %%ymm15,%%ymm11,%%ymm11\n\tvmovdqa %%ymm0,0(%[b0])\n\tvmovdqa %%ymm8,32(%[b0])\n\tvmovdqa %%ymm1,0(%[b0],%[hs],1)\n\tvmovdqa %%ymm9,32(%[b0],%[hs],1)\n\tvmovdqa %%ymm2,0(%[b1])\n\tvmovdqa %%ymm10,32(%[b1])\n\tvmovdqa %%ymm3,0(%[b1],%[hs],1)\n\tvmovdqa %%ymm11,32(%[b1],%[hs],1)\n\tvmovdqa %%ymm4,0(%[b2])\n\tvmovdqa %%ymm12,32(%[b2])\n\tvmovdqa %%ymm5,0(%[b2],%[hs],1)\n\tvmovdqa %%ymm13,32(%[b2],%[hs],1)\n\tvmovdqa %%ymm6,0(%[b3])\n\tvmovdqa %%ymm14,32(%[b3])"::[b0]"r"(p+0*h+j),[b1]"r"(p+2*h+j),[b2]"r"(p+4*h+j),[b3]"r"(p+6*h+j),[hs]"r"(size_t(h)*4):"ymm0","ymm1","ymm2","ymm3","ymm4","ymm5","ymm6","ymm7","ymm8","ymm9","ymm10","ymm11","ymm12","ymm13","ymm14","ymm15","memory");}}}

static void and_octant_pair(unsigned n,u32*x,u32*y){if(n>=2097152){ar_and_top<false>(x,n/8);ar_and_top<false>(y,n/8);return;}full_oct_line<false>(n,x);full_oct_line<false>(n,y);}template<unsigned ar_n=0>static void paired_leaf256(unsigned n,u32*x,u32*y){if constexpr(ar_n)n=ar_n;for(unsigned j=0;j<n;j+=256){forward_half128<false>(x+j+192,nullptr);forward_half128<true>(x+j+64,x+j+192);forward_half128<true>(x+j+128,x+j+192);forward_last256(x+j+0,x+j+64,x+j+128,x+j+192);forward_half128<false>(y+j+192,nullptr);forward_half128<true>(y+j+64,y+j+192);forward_half128<true>(y+j+128,y+j+192);forward_last256(y+j+0,y+j+64,y+j+128,y+j+192);}and_high256_pair(x,y,n);for(unsigned j=0;j<n;j+=256){product_half128<false>(x+j+192,y+j+192,nullptr);product_half128<true>(x+j+64,y+j+64,x+j+192);product_half128<true>(x+j+128,y+j+128,x+j+192);product_last256(x+j+0,y+j+0,x+j+64,x+j+128,x+j+192);}high256<true>(x,n);}
static void solve(unsigned n,u32*x,u32*y);
template<bool Inverse>static void high_octants(unsigned n,u32*p){if(n>=2097152){ar_and_top<Inverse>(p,n/8);return;}full_oct_line<Inverse>(n,p);}static void ar_fast4k(u32*x,u32*y){full_oct_line<false>(4096,x);full_oct_line<false>(4096,y);for(unsigned q=0;q<8;q++)paired_leaf256<512>(512,x+q*512,y+q*512);full_oct_line<true>(4096,x);}
static void solve(unsigned n,u32*x,u32*y){if(n==4096){ar_fast4k(x,y);return;}
 if(n<=1024){if(!(n&255u)){paired_leaf256(n,x,y);return;}if(!(n&127u)){paired_leaf128_onesave(n,x,y);return;}if(n>=64 && (n&(n-1))==0){paired_leaf64_pow2(n,x,y);return;}if(!(n&63u)){paired_leaf64(n,x,y);return;}if(!(n&31u)){paired_leaf32(n,x,y);return;}if(!(n&15u)){paired_leaf16(n,x,y);return;}
  leaf32<true,false>(x,n);leaf32<true,false>(y,n);
  if(n&7u){for(unsigned j=0;j<n;j++)x[j]*=y[j];leaf32<true,true>(x,n);return;}
  for(unsigned j=0;j<n;j+=8)_mm256_storeu_si256((__m256i*)(x+j),inv8(_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+j)),_mm256_loadu_si256((const __m256i*)(y+j)))));
  for(unsigned h=8;h<n;h*=2)for(unsigned base=0;base<n;base+=2*h)if(base+h<n){unsigned z=std::min(h,n-base-h),j=0;
   for(;j+8<=z;j+=8)_mm256_storeu_si256((__m256i*)(x+base+j),_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(x+base+j)),_mm256_loadu_si256((const __m256i*)(x+base+h+j))));
   for(;j<z;j++)x[base+j]-=x[base+h+j];
  }return;
 }
 if((n&(n-1))==0 && n>=4096){
  and_octant_pair(n,x,y);
  const unsigned q=n/8;for(unsigned r=0;r<8;r++)solve(q,x+r*q,y+r*q);
  high_octants<true>(n,x);return;
 }
 const unsigned h=1u<<(30-__builtin_clz(n-1)),r2=std::min(h,n-2*h),r3=n>3*h?n-3*h:0;unsigned j=0;
 for(;j+8<=r3;j+=8){
  auto a=_mm256_loadu_si256((const __m256i*)(x+j)),b=_mm256_loadu_si256((const __m256i*)(x+h+j)),c=_mm256_loadu_si256((const __m256i*)(x+2*h+j)),d=_mm256_loadu_si256((const __m256i*)(x+3*h+j));
  auto e=_mm256_loadu_si256((const __m256i*)(y+j)),f=_mm256_loadu_si256((const __m256i*)(y+h+j)),g=_mm256_loadu_si256((const __m256i*)(y+2*h+j)),q=_mm256_loadu_si256((const __m256i*)(y+3*h+j));
  _mm256_storeu_si256((__m256i*)(x+j),_mm256_add_epi32(_mm256_add_epi32(a,b),_mm256_add_epi32(c,d)));
  _mm256_storeu_si256((__m256i*)(x+h+j),_mm256_add_epi32(b,d));_mm256_storeu_si256((__m256i*)(x+2*h+j),_mm256_add_epi32(c,d));
  _mm256_storeu_si256((__m256i*)(y+j),_mm256_add_epi32(_mm256_add_epi32(e,f),_mm256_add_epi32(g,q)));
  _mm256_storeu_si256((__m256i*)(y+h+j),_mm256_add_epi32(f,q));_mm256_storeu_si256((__m256i*)(y+2*h+j),_mm256_add_epi32(g,q));
 }
 for(;j<r3;j++){x[j]+=x[h+j]+x[2*h+j]+x[3*h+j];x[h+j]+=x[3*h+j];x[2*h+j]+=x[3*h+j];y[j]+=y[h+j]+y[2*h+j]+y[3*h+j];y[h+j]+=y[3*h+j];y[2*h+j]+=y[3*h+j];}
 for(;j+8<=r2;j+=8){
  _mm256_storeu_si256((__m256i*)(x+j),_mm256_add_epi32(_mm256_loadu_si256((const __m256i*)(x+j)),_mm256_add_epi32(_mm256_loadu_si256((const __m256i*)(x+h+j)),_mm256_loadu_si256((const __m256i*)(x+2*h+j)))));
  _mm256_storeu_si256((__m256i*)(y+j),_mm256_add_epi32(_mm256_loadu_si256((const __m256i*)(y+j)),_mm256_add_epi32(_mm256_loadu_si256((const __m256i*)(y+h+j)),_mm256_loadu_si256((const __m256i*)(y+2*h+j)))));
 }
 for(;j<r2;j++){x[j]+=x[h+j]+x[2*h+j];y[j]+=y[h+j]+y[2*h+j];}
 for(;j+8<=h;j+=8){_mm256_storeu_si256((__m256i*)(x+j),_mm256_add_epi32(_mm256_loadu_si256((const __m256i*)(x+j)),_mm256_loadu_si256((const __m256i*)(x+h+j))));_mm256_storeu_si256((__m256i*)(y+j),_mm256_add_epi32(_mm256_loadu_si256((const __m256i*)(y+j)),_mm256_loadu_si256((const __m256i*)(y+h+j))));}
 for(;j<h;j++){x[j]+=x[h+j];y[j]+=y[h+j];}
 solve(h,x,y);solve(h,x+h,y+h);solve(r2,x+2*h,y+2*h);if(r3)solve(r3,x+3*h,y+3*h);
 j=0;for(;j+8<=r3;j+=8){
  auto a=_mm256_loadu_si256((const __m256i*)(x+j)),b=_mm256_loadu_si256((const __m256i*)(x+h+j)),c=_mm256_loadu_si256((const __m256i*)(x+2*h+j)),d=_mm256_loadu_si256((const __m256i*)(x+3*h+j));
  _mm256_storeu_si256((__m256i*)(x+j),_mm256_sub_epi32(_mm256_add_epi32(a,d),_mm256_add_epi32(b,c)));
  _mm256_storeu_si256((__m256i*)(x+h+j),_mm256_sub_epi32(b,d));_mm256_storeu_si256((__m256i*)(x+2*h+j),_mm256_sub_epi32(c,d));
 }
 for(;j<r3;j++){x[j]+=x[3*h+j]-x[h+j]-x[2*h+j];x[h+j]-=x[3*h+j];x[2*h+j]-=x[3*h+j];}
 for(;j+8<=r2;j+=8)_mm256_storeu_si256((__m256i*)(x+j),_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(x+j)),_mm256_add_epi32(_mm256_loadu_si256((const __m256i*)(x+h+j)),_mm256_loadu_si256((const __m256i*)(x+2*h+j)))));
 for(;j<r2;j++)x[j]-=x[h+j]+x[2*h+j];
 for(;j+8<=h;j+=8)_mm256_storeu_si256((__m256i*)(x+j),_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(x+j)),_mm256_loadu_si256((const __m256i*)(x+h+j))));
 for(;j<h;j++)x[j]-=x[h+j];
}

}
static void ar_copy4_pair(unsigned h,unsigned r2,unsigned r3,const unsigned*a,const unsigned*b,unsigned*c,unsigned*t){unsigned j=0;
for(;j+8<=r3;j+=8){{
auto v0=_mm256_loadu_si256((const __m256i*)(a+0*h+j));
auto v1=_mm256_loadu_si256((const __m256i*)(a+1*h+j));
auto v2=_mm256_loadu_si256((const __m256i*)(a+2*h+j));
auto v3=_mm256_loadu_si256((const __m256i*)(a+3*h+j));
_mm256_storeu_si256((__m256i*)(c+0*h+j),_mm256_add_epi32(_mm256_add_epi32(v0,v1),_mm256_add_epi32(v2,v3)));
_mm256_storeu_si256((__m256i*)(c+1*h+j),_mm256_add_epi32(v1,v3));
_mm256_storeu_si256((__m256i*)(c+2*h+j),_mm256_add_epi32(v2,v3));
_mm256_storeu_si256((__m256i*)(c+3*h+j),v3);
}{
auto v0=_mm256_loadu_si256((const __m256i*)(b+0*h+j));
auto v1=_mm256_loadu_si256((const __m256i*)(b+1*h+j));
auto v2=_mm256_loadu_si256((const __m256i*)(b+2*h+j));
auto v3=_mm256_loadu_si256((const __m256i*)(b+3*h+j));
_mm256_storeu_si256((__m256i*)(t+0*h+j),_mm256_add_epi32(_mm256_add_epi32(v0,v1),_mm256_add_epi32(v2,v3)));
_mm256_storeu_si256((__m256i*)(t+1*h+j),_mm256_add_epi32(v1,v3));
_mm256_storeu_si256((__m256i*)(t+2*h+j),_mm256_add_epi32(v2,v3));
_mm256_storeu_si256((__m256i*)(t+3*h+j),v3);
}}
for(;j<r3;j++){{
unsigned v0=a[0*h+j];
unsigned v1=a[1*h+j];
unsigned v2=a[2*h+j];
unsigned v3=a[3*h+j];
c[0*h+j]=v0+v1+v2+v3;
c[1*h+j]=v1+v3;
c[2*h+j]=v2+v3;
c[3*h+j]=v3;
}{
unsigned v0=b[0*h+j];
unsigned v1=b[1*h+j];
unsigned v2=b[2*h+j];
unsigned v3=b[3*h+j];
t[0*h+j]=v0+v1+v2+v3;
t[1*h+j]=v1+v3;
t[2*h+j]=v2+v3;
t[3*h+j]=v3;
}}
for(;j+8<=r2;j+=8){{
auto v0=_mm256_loadu_si256((const __m256i*)(a+0*h+j));
auto v1=_mm256_loadu_si256((const __m256i*)(a+1*h+j));
auto v2=_mm256_loadu_si256((const __m256i*)(a+2*h+j));
_mm256_storeu_si256((__m256i*)(c+0*h+j),_mm256_add_epi32(v0,_mm256_add_epi32(v1,v2)));
_mm256_storeu_si256((__m256i*)(c+1*h+j),v1);
_mm256_storeu_si256((__m256i*)(c+2*h+j),v2);
}{
auto v0=_mm256_loadu_si256((const __m256i*)(b+0*h+j));
auto v1=_mm256_loadu_si256((const __m256i*)(b+1*h+j));
auto v2=_mm256_loadu_si256((const __m256i*)(b+2*h+j));
_mm256_storeu_si256((__m256i*)(t+0*h+j),_mm256_add_epi32(v0,_mm256_add_epi32(v1,v2)));
_mm256_storeu_si256((__m256i*)(t+1*h+j),v1);
_mm256_storeu_si256((__m256i*)(t+2*h+j),v2);
}}
for(;j<r2;j++){{
unsigned v0=a[0*h+j];
unsigned v1=a[1*h+j];
unsigned v2=a[2*h+j];
c[0*h+j]=v0+v1+v2;
c[1*h+j]=v1;
c[2*h+j]=v2;
}{
unsigned v0=b[0*h+j];
unsigned v1=b[1*h+j];
unsigned v2=b[2*h+j];
t[0*h+j]=v0+v1+v2;
t[1*h+j]=v1;
t[2*h+j]=v2;
}}
for(;j+8<=h;j+=8){{
auto v0=_mm256_loadu_si256((const __m256i*)(a+0*h+j));
auto v1=_mm256_loadu_si256((const __m256i*)(a+1*h+j));
_mm256_storeu_si256((__m256i*)(c+0*h+j),_mm256_add_epi32(v0,v1));
_mm256_storeu_si256((__m256i*)(c+1*h+j),v1);
}{
auto v0=_mm256_loadu_si256((const __m256i*)(b+0*h+j));
auto v1=_mm256_loadu_si256((const __m256i*)(b+1*h+j));
_mm256_storeu_si256((__m256i*)(t+0*h+j),_mm256_add_epi32(v0,v1));
_mm256_storeu_si256((__m256i*)(t+1*h+j),v1);
}}
for(;j<h;j++){{
unsigned v0=a[0*h+j];
unsigned v1=a[1*h+j];
c[0*h+j]=v0+v1;
c[1*h+j]=v1;
}{
unsigned v0=b[0*h+j];
unsigned v1=b[1*h+j];
t[0*h+j]=v0+v1;
t[1*h+j]=v1;
}}
}
template<unsigned FixedN>static void ar_entry(unsigned input_n,const unsigned*a,const unsigned*b,unsigned*c){const unsigned n=FixedN?FixedN:input_n;
 alignas(4096)static unsigned scratch[10000384u];if(!n)return;void*root_allocation=nullptr;unsigned*t=scratch+384;if(n>10000000u){if(posix_memalign(&root_allocation,4096,size_t(n)*4+1536))__builtin_trap();t=(unsigned*)root_allocation+384;}
 if(n<=1024){memcpy(c,a,size_t(n)*4);memcpy(t,b,size_t(n)*4);root_and::solve(n,c,t);free(root_allocation);return;}
 const unsigned h=1u<<(30-__builtin_clz(n-1)),r2=std::min(h,n-2*h),r3=n>3*h?n-3*h:0;unsigned j=0;
 ar_copy4_pair(h,r2,r3,a,b,c,t);
 root_and::solve(h,c,t);root_and::solve(h,c+h,t+h);root_and::solve(r2,c+2*h,t+2*h);if(r3)root_and::solve(r3,c+3*h,t+3*h);
 unsigned*x=c;
 j=0;for(;j+8<=r3;j+=8){
  auto a=_mm256_loadu_si256((const __m256i*)(x+j)),b=_mm256_loadu_si256((const __m256i*)(x+h+j)),c=_mm256_loadu_si256((const __m256i*)(x+2*h+j)),d=_mm256_loadu_si256((const __m256i*)(x+3*h+j));
  _mm256_storeu_si256((__m256i*)(x+j),_mm256_sub_epi32(_mm256_add_epi32(a,d),_mm256_add_epi32(b,c)));
  _mm256_storeu_si256((__m256i*)(x+h+j),_mm256_sub_epi32(b,d));_mm256_storeu_si256((__m256i*)(x+2*h+j),_mm256_sub_epi32(c,d));
 }
 for(;j<r3;j++){x[j]+=x[3*h+j]-x[h+j]-x[2*h+j];x[h+j]-=x[3*h+j];x[2*h+j]-=x[3*h+j];}
 for(;j+8<=r2;j+=8)_mm256_storeu_si256((__m256i*)(x+j),_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(x+j)),_mm256_add_epi32(_mm256_loadu_si256((const __m256i*)(x+h+j)),_mm256_loadu_si256((const __m256i*)(x+2*h+j)))));
 for(;j<r2;j++)x[j]-=x[h+j]+x[2*h+j];
 for(;j+8<=h;j+=8)_mm256_storeu_si256((__m256i*)(x+j),_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(x+j)),_mm256_loadu_si256((const __m256i*)(x+h+j))));
 for(;j<h;j++)x[j]-=x[h+j];
 free(root_allocation);
}

template<unsigned Q,bool Inv>static void arithmetic_root_band(const unsigned*a,const unsigned*b,unsigned*c,unsigned*t,unsigned begin,unsigned end){constexpr unsigned H=16777216;for(unsigned j=begin;j<end;j+=8){__m256i x[Q],y[Q];
#pragma GCC unroll 8
for(unsigned q=0;q<Q;q++){x[q]=_mm256_load_si256((const __m256i*)((Inv?c:a)+q*H+j));if constexpr(!Inv)y[q]=_mm256_load_si256((const __m256i*)(b+q*H+j));}
#pragma GCC unroll 3
for(unsigned bit=0;bit<3;bit++){
#pragma GCC unroll 8
for(unsigned q=0;q<Q;q++)if(!(q&(1u<<bit))&&((q|(1u<<bit))<Q)){if constexpr(Inv)x[q]=_mm256_sub_epi32(x[q],x[q|(1u<<bit)]);else{x[q]=_mm256_add_epi32(x[q],x[q|(1u<<bit)]);y[q]=_mm256_add_epi32(y[q],y[q|(1u<<bit)]);}}}
#pragma GCC unroll 8
for(unsigned q=0;q<Q;q++){bool changed=false;
#pragma GCC unroll 3
for(unsigned bit=0;bit<3;bit++)if(!(q&(1u<<bit))&&((q|(1u<<bit))<Q))changed=true;if(!Inv||changed)_mm256_store_si256((__m256i*)(c+q*H+j),x[q]);if constexpr(!Inv)_mm256_store_si256((__m256i*)(t+q*H+j),y[q]);}
}}
template<bool Inv,unsigned Q>static inline void ar_and_roots(__m256i(&v)[Q]){
#pragma GCC unroll 3
 for(unsigned st=0;st<3;st++){unsigned bit=Inv?2-st:st;
#pragma GCC unroll 8
 for(unsigned q=0;q<Q;q++)if(!(q&(1u<<bit))&&(q|(1u<<bit))<Q){if constexpr(Inv)v[q]=_mm256_sub_epi32(v[q],v[q|(1u<<bit)]);else v[q]=_mm256_add_epi32(v[q],v[q|(1u<<bit)]);}}
}
static void root8_fixed(const unsigned*a,const unsigned*b,unsigned*c){
constexpr unsigned H=16777216,R=16113920,L=H/8,T=1024,LP=T+16,R7=R-7*L;
alignas(4096)static unsigned work[6*H+384];unsigned*t=work+384,*x5=c+5*H;
alignas(64)static unsigned sc[6][8][LP];
for(unsigned j0=0;j0<L;j0+=T)for(unsigned side=0;side<2;side++){
 const unsigned*in=side?b:a;
 for(unsigned rr=0;rr<8;rr++)for(unsigned j=0;j<T;j+=8){unsigned off=rr*L+j0+j;__m256i v[6];
#pragma GCC unroll 6
  for(unsigned q=0;q<6;q++)v[q]=(q<5||off<R)?_mm256_load_si256((const __m256i*)(in+q*H+off)):_mm256_setzero_si256();ar_and_roots<false>(v);
#pragma GCC unroll 6
  for(unsigned q=0;q<6;q++)_mm256_store_si256((__m256i*)(sc[q][rr]+j),v[q]);
 }
 for(unsigned q=0;q<6;q++){
  for(unsigned j=0;j<T;j+=8){__m256i v[8];
#pragma GCC unroll 8
   for(unsigned rr=0;rr<8;rr++)v[rr]=_mm256_load_si256((const __m256i*)(sc[q][rr]+j));ar_and_roots<false>(v);
#pragma GCC unroll 8
   for(unsigned rr=0;rr<8;rr++)_mm256_store_si256((__m256i*)(sc[q][rr]+j),v[rr]);
  }
  unsigned*out=side?t+q*H:(q==5?x5:c+q*H);
  for(unsigned rr=0;rr<8;rr++){
#pragma GCC unroll 8
   for(unsigned j=0;j<T;j+=8)if(q<5||rr<7||j0+j<R7)_mm256_stream_si256((__m256i*)(out+rr*L+j0+j),_mm256_load_si256((const __m256i*)(sc[q][rr]+j)));
  }
 }
}
_mm_sfence();
for(unsigned q=0;q<6;q++)for(unsigned rr=0;rr<8;rr++){unsigned off=rr*L,z=q<5?L:(off<R?std::min(L,R-off):0);if(z)root_and::solve(z,(q==5?x5:c+q*H)+off,t+q*H+off);}
for(unsigned j0=0;j0<L;j0+=T){
 for(unsigned q=0;q<6;q++)for(unsigned j=0;j<T;j+=8){unsigned off=j0+j;__m256i v[8];const unsigned*base=(q==5?x5:c+q*H);
#pragma GCC unroll 7
  for(unsigned rr=0;rr<7;rr++)v[rr]=_mm256_load_si256((const __m256i*)(base+rr*L+off));v[7]=(q==5&&off>=R7)?_mm256_setzero_si256():_mm256_load_si256((const __m256i*)(base+7*L+off));ar_and_roots<true>(v);
#pragma GCC unroll 8
  for(unsigned rr=0;rr<8;rr++)_mm256_store_si256((__m256i*)(sc[q][rr]+j),v[rr]);
 }
 for(unsigned rr=0;rr<8;rr++){
  for(unsigned j=0;j<T;j+=8){__m256i v[6];
#pragma GCC unroll 6
   for(unsigned q=0;q<6;q++)v[q]=_mm256_load_si256((const __m256i*)(sc[q][rr]+j));ar_and_roots<true>(v);
#pragma GCC unroll 6
   for(unsigned q=0;q<6;q++)_mm256_store_si256((__m256i*)(sc[q][rr]+j),v[q]);
  }
  for(unsigned q=0;q<6;q++){
#pragma GCC unroll 8
   for(unsigned j=0;j<T;j+=8){unsigned off=rr*L+j0+j;if(q<5||off<R)_mm256_stream_si256((__m256i*)(c+q*H+off),_mm256_load_si256((const __m256i*)(sc[q][rr]+j)));}
  }
 }
}
_mm_sfence();}
void convolution(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){if(n==100000000u)root8_fixed(a,b,c);else ar_entry<0>(n,a,b,c);}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1562.502 ms763 MB + 216 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2026-11-18 09:37:17 | Loaded in 12 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠