/* References:148196 complete cached-two-leaf NTT/packed-input engine;148173 second32768-leaf integer/affine cache. All other sources supply inherited NTT/Montgomery/Shoup/root/layout/input/output optimizations. Original accounts/URLs:
Qwerty1232: https://duck.ac/submission/28087; uses above.
iMMIQ: https://duck.ac/submission/48181; uses above.
saffah_codex_6s_agg2: https://duck.ac/submission/108780; uses above.
saffah_cc_v41_agg1: https://duck.ac/submission/116111, https://duck.ac/submission/116381, https://duck.ac/submission/116560, https://duck.ac/submission/116691, https://duck.ac/submission/121681, https://duck.ac/submission/123400, https://duck.ac/submission/123952, https://duck.ac/submission/123953, https://duck.ac/submission/126765, https://duck.ac/submission/127195, https://duck.ac/submission/127971, https://duck.ac/submission/128005, https://duck.ac/submission/129094, https://duck.ac/submission/130113, https://duck.ac/submission/130711, https://duck.ac/submission/130739, https://duck.ac/submission/130793; uses above.
saffah_codex_6a_agg3: https://duck.ac/submission/121485, https://duck.ac/submission/121513, https://duck.ac/submission/125877, https://duck.ac/submission/126070, https://duck.ac/submission/126244, https://duck.ac/submission/126256, https://duck.ac/submission/126270, https://duck.ac/submission/134190, https://duck.ac/submission/134205, https://duck.ac/submission/134236, https://duck.ac/submission/134242, https://duck.ac/submission/134254, https://duck.ac/submission/139298, https://duck.ac/submission/140399, https://duck.ac/submission/140562, https://duck.ac/submission/140752; uses above.
saffah_v41f1017_agg4: https://duck.ac/submission/131891, https://duck.ac/submission/134756, https://duck.ac/submission/146081, https://duck.ac/submission/146287, https://duck.ac/submission/146527, https://duck.ac/submission/146541, https://duck.ac/submission/148173, https://duck.ac/submission/148196; uses above.
saffah_codex61s_agg5: https://duck.ac/submission/144624, https://duck.ac/submission/144830, https://duck.ac/submission/145407, https://duck.ac/submission/145672, https://duck.ac/submission/145757, https://duck.ac/submission/145816, https://duck.ac/submission/145845; uses above.
No additional Duck source licence stated; no new third-party material. */
/* Idea: At final output only, publish aligned normalized coefficient vectors with NT stores and remove write-prefetches; fence after all arms. Keep unaligned destinations on the original stores and preserve borrowed-input/output alias schedule. Experiment:full2000001 exact coefficients on known/random/adversarial inputs and aligned/misaligned guards, then official timing. */
#include <immintrin.h>
#include <algorithm>
#include <array>
#include <type_traits>
#include <cassert>
#include <cstdint>
#include <cstring>
#include <vector>
#define aa u32x8
#define ab i256
#define ac const
#define ad step
#define ae true
#define af mod2
#define ag false
#define ah constexpr
#define aj load_u32x8
#define ak store_u32x8
#define al auto
#define am mul_pre_wn
#define an _mm256_mul_epu32
#define ao u64x4
#define ap butterfly_pair
#define aq offset
#define ar char
#define as else
#define at _mm256_set1_epi32
#define au root
#define av return
#define aw _mm_prefetch
#define ax _MM_HINT_T0
#define ay bool
#define az n_inv
#define aA void
#define aB trivial
#define aC data
#define aD template
#define aE static
#define aF inverse
#define aG unsigned
#define aH w_ar
#define aI alignas
#define aJ transform_stage
#define aK Block
#define aL _mm256_min_epu32
#define aM _mm256_bsrli_epi128
#define aN skip0
#define aO scratch
#define aP __attribute__
#define aQ shrink2
#define aR _mm256_add_epi64
#define aS inline
#define aT shrink
#define aU table
#define aV _mm256_permute4x64_epi64
#define aW aux_b_r2
#define aX strict
#define aY vecr
#define aZ delta8
#define a4 _mm256_permutevar8x32_epi32
#define a5 wi_data
#define a6 rmf_
#define a7 stream
#define a8 Quarter
#define a9 uintptr_t
#define ba _mm256_setr_epi64x
#define bc always_inline
#define bd forward
#define be sizeof
#define bf const_cast
#define bg aux_ans_r2
#define bh mul_pre
#define bj multiply_leaf
#define bk k02zc_org
#define bl last0
#define bm last3
#define bn struct
#define bo _mm256_add_epi32
#define bq wld_x4
#define br __builtin_ctz
#define bs leaf_log2
#define bt block_base
#define bu _mm256_and_si256
#define bv convolve_fixed
#define bw convolve_block
#define bx FixedScale
#define bz packed
#define bA _mm256_sub_epi32
#define bB _mm256_or_si256
#define bC mul_u32x8
#define bD Twiddle
#define bE _mm256_mullo_epi32
#define bF pl_known
#define bG wt_init
#define bH wrt_init
#define bI wl_init
#define bJ _mm256_cmpgt_epi32
#define bK __asm__
#define bL __volatile__
#define bM final_dst
#define bN prepare_quarter
#define bO lastOwn
#define bP _mm_free
#define bQ mul_u64x4
#define bR normalize
#define bS __m256i_u
#define bT prepare_quarters
#define bU run_finish
#define bV canonical_wide
#define bW i2_mulhi32_c
#define bX i2_shoup32_c
#define bY mul_pre_x_wn
#define bZ transform_forward
#define b0 wide_output
#define b1 multiply_leaves
#define b2 multiply_range
#define b3 _mm256_packus_epi32
#define b4 finish_quarters
#define b5 fourth_count
#define b6 integral_constant
#define b7 _mm256_cvtepu8_epi32
#define b8 transform_fixed_pair_split
#define b9 convolve_final_split_quarter
#define ca prepare_quarters_split_last
#define cb prepare_quarter_packed
#define cd convolve_reusing_output
#pragma GCC optimize("web")
#pragma GCC optimize("O3,unroll-loops,rename-registers")
#pragma GCC optimize("align-functions=64")
#pragma GCC optimize("align-loops=64")
#pragma GCC target("avx2,bmi")
aE ah int z2r12_kout = 5 - 5 + 0;
#define LDU(p) ({ __m256i _v; __asm__("vmovdqu %1, %0":"=x"(_v):"m"(*(const __m256i*)(p))); _v; })
#define LDA(p) ({ __m256i _v; __asm__("vmovdqa %1, %0":"=x"(_v):"m"(*(const __m256i*)(p))); _v; })
#define STU(p, v) do { __m256i _v = (__m256i)(v); __asm__("vmovdqu %1, %0":"=m"(*(__m256i_u*)(p)):"x"(_v)); } while(0)
#define STA(p, v) do { __m256i _v = (__m256i)(v); __asm__("vmovdqa %1, %0":"=m"(*(__m256i_u*)(p)):"x"(_v)); } while(0)
using u32 = uint32_t;
using u64 = uint64_t;
bn mc_ {
u32 mod;
u32 af;
u32 az;
u32 r;
u32 r2;
mc_() = default;
mc_(u32 mod) : mod(mod) {
assert(mod % 2 == 1);
assert(mod < (1 << 30));
af = 2 * mod;
az = 1;
for (int i = 0; i < 5; i++) {
az *= 2 + az * mod;
}
r = (u64(1) << 32) % mod;
r2 = u64(r) * r % mod;
}
u32 aT(u32 val) ac { av std::min(val, val - mod); }
u32 aQ(u32 val) ac { av std::min(val, val - af); }
aD <ay aX = ae> u32 reduce(u64 val) ac {
u32 res = (val + u32(val) * az * u64(mod)) >> 32;
if (aX) res = aT(res);
av res;
}
aD <ay aX = ae> u32 mul(u32 a, u32 b) ac { av reduce<aX>(u64(a) * b); }
aD <ay input_in_space = ag, ay output_in_space = ag> u32 power(u32 b, u32 e) ac {
if (!input_in_space) b = mul<ag>(b, r2);
u32 r = output_in_space ? this->r : 1;
for (; e > 0; e >>= 1) {
if (e & 1) r = mul<ag>(r, b);
b = mul<ag>(b, b);
}
av aT(r);
}
};
using ab = __m256i;
using aa = u32 aP((vector_size(32)));
using ao = u64 aP((vector_size(32)));
aa aj(ac u32 *ptr) {
av (aa)LDA(ptr);
}
aA ak(u32 *ptr, aa vec) {
STA(ptr, vec);
}
bn mv_ {
aE ah aa mod = {81788929, 81788929, 81788929, 81788929, 81788929, 81788929, 81788929, 81788929};
aE ah aa af = {163577858, 163577858, 163577858, 163577858,
163577858, 163577858, 163577858, 163577858};
aE ah aa az = {81788927, 81788927, 81788927, 81788927, 81788927, 81788927, 81788927, 81788927};
aE ah aa r = {41942988, 41942988, 41942988, 41942988, 41942988, 41942988, 41942988, 41942988};
aE ah aa r2 = {56088131, 56088131, 56088131, 56088131, 56088131, 56088131, 56088131, 56088131};
mv_() = default;
explicit mv_(u32 p) { assert(p == 81788929); }
aa aT(aa vec) ac { av (aa)aL((ab)vec, bA((ab)vec, (ab)mod)); }
aD <int Low = 0> aa bV(aa v) ac {
for (int shift = 5; shift >= Low; shift--) {
aa p = mod << shift;
v = (aa)aL((ab)v, (ab)(v - p));
}
av v;
}
aa aQ(aa vec) ac {
av (aa)aL((ab)vec, bA((ab)vec, (ab)af));
}
aa shrink2_n(aa vec) ac {
av (aa)aL((ab)vec, bo((ab)vec, (ab)af));
}
aD <ay aX = ae> aa reduce(ao x0246, ao x1357) ac {
ao x0246_ninv = (ao)an((ab)x0246, (ab)az);
ao x1357_ninv = (ao)an((ab)x1357, (ab)az);
ao x0246_res = (ao)aR((ab)x0246, an((ab)x0246_ninv, (ab)mod));
ao x1357_res = (ao)aR((ab)x1357, an((ab)x1357_ninv, (ab)mod));
aa res = (aa)bB(aM((ab)x0246_res, 4), (ab)x1357_res);
if (aX) res = aT(res);
av res;
}
aD <ay aX = ae, ay b_use_only_even = ag> aa bC(aa a, aa b) ac {
aa a_sh = (aa)aM((ab)a, 4);
aa b_sh = b_use_only_even ? b : (aa)aM((ab)b, 4);
ao x0246 = (ao)an((ab)a, (ab)b);
ao x1357 = (ao)an((ab)a_sh, (ab)b_sh);
av reduce<aX>(x0246, x1357);
}
aD <ay aX = ae> ao bQ(ao a, ao b) ac {
ao pr = (ao)an((ab)a, (ab)b);
ao pr2 = (ao)an(an((ab)pr, (ab)az), (ab)mod);
ao res = (ao)aM(aR((ab)pr, (ab)pr2), 4);
if (aX) res = (ao)aT((aa)res);
av res;
}
};
namespace fr_ {
bn bD {
u32 w1, w2, w3;
};
bn Table {
bD aC[65536];
};
extern ac Table bd asm("poly_roots_forward");
extern ac Table aF asm("poly_roots_inverse");
bn DotTable {
u32 aC[(32768)][4];
};
extern ac DotTable dot asm("poly_roots_dot");
}
aP((constructor)) aE aA prefault_roots_() {
volatile aG s_ = 0;
ac ar *p_ = (ac ar *)&fr_::bd;
for (size_t o_ = 0; o_ < be(fr_::bd); o_ += 4096) s_ += p_[o_];
p_ = (ac ar *)&fr_::aF;
for (size_t o_ = 0; o_ < be(fr_::aF); o_ += 4096) s_ += p_[o_];
p_ = (ac ar *)&fr_::dot;
for (size_t o_ = 0; o_ < be(fr_::dot); o_ += 4096) s_ += p_[o_];
(aA)s_;
}
asm(R"asm(
.pushsection .rodata
// Select by the number of trailing one bits in the table index.
.macro next_factor dest, mask, value, rest:vararg
.if ((_i & \mask) == 0)
.set \dest,\value
.else
next_factor \dest,(\mask*2),\rest
.endif
.endm
.p2align 6
.globl poly_roots_forward
.type poly_roots_forward,@object
poly_roots_forward:
.set _i,0
.set _w1,41942988
.set _w2,41942988
.rept 65536
.set _w12,(((_w1*_w2)%81788929)*1557504)%81788929
.long _w1,_w2,_w12
next_factor _fac, 1, 1977387,49739338,76551861,57685215,25318722,22305379,75160758,77449485,49050524,58847824,69356575,69052175,45043381,68811137,48691376,28111944,26577652
next_factor _fac2, 1, 57807995,1883838,27152551,62819432,22367481,25489457,54748607,18371892,60074596,43336831,16579980,78708963,26101542,51041304,60500196,40232015,28323882
.set _w1,(_w1*_fac2)%81788929
.set _w2,(_w2*_fac)%81788929
.set _i,_i+1
.endr
.size poly_roots_forward,.-poly_roots_forward
.p2align 6
.globl poly_roots_inverse
.type poly_roots_inverse,@object
poly_roots_inverse:
.set _i,0
.set _w1,41942988
.set _w2,41942988
.rept 65536
.set _w12,(((_w1*_w2)%81788929)*1557504)%81788929
.long _w1,_w2,_w12
next_factor _fac, 1, 1883838,34192649,65864533,47472559,32202660,46455854,18299665,51166265,46148164,40005067,42538512,22507185,19881487,13191717,67317322,1064838,16759432
next_factor _fac2, 1, 23980934,1977387,58967103,56026958,74557765,58488554,3169619,20142414,28119438,26733415,74787290,67900511,63391377,74641937,67976842,40043517,2457972
.set _w1,(_w1*_fac2)%81788929
.set _w2,(_w2*_fac)%81788929
.set _i,_i+1
.endr
.size poly_roots_inverse,.-poly_roots_inverse
.p2align 6
.globl poly_roots_dot
.type poly_roots_dot,@object
poly_roots_dot:
.set _i,0
.set _d0,41942988
.set _d1,42958308
.set _d2,28282409
.set _d3,36011086
.rept 32768
.long _d0,_d1,_d2,_d3
next_factor _fac, 1, 34192649,76852948,45870503,27153147,50722843,53125215,43544278,13378268,50576854,50366248,18491959,52344447,58962465,12062499,19859762,9337084
.set _d0,(_d0*_fac)%81788929
.set _d1,(_d1*_fac)%81788929
.set _d2,(_d2*_fac)%81788929
.set _d3,(_d3*_fac)%81788929
.set _i,_i+1
.endr
.size poly_roots_dot,.-poly_roots_dot
.purgem next_factor
.popsection
)asm");
aE aS ab i2_mulhi32(ab a, ab b) {
ab e = an(a, b);
ab o = an(aM(a, 4), aM(b, 4));
av _mm256_blend_epi32(aM(e, 4), o, 0xAA);
}
aE aS aa i2_shoup32(aa a, aa w, aa ws, aa pv) {
ab t = bE((ab)a, (ab)w);
ab q = i2_mulhi32((ab)a, (ab)ws);
av (aa)bA(t, bE(q, (ab)pv));
}
aE aS ab bW(ab a, ab b) {
ab e = an(a, b);
ab o = an(aM(a, 4), b);
av _mm256_blend_epi32(aM(e, 4), o, 0xAA);
}
aE aS aa bX(aa a, aa w, aa ws, aa pv) {
ab t = bE((ab)a, (ab)w);
ab q = bW((ab)a, (ab)ws);
av (aa)bA(t, bE(q, (ab)pv));
}
bn aI(32) PL1{u32 aC[32768]{};ah PL1(){ah char32_t s[]=U"𮯠𢟕𣪗𧹪𰨿𧼮𰳗𮠫𩪆𰬅𫟦𥍅𩓔𫖝𮇂𨔽𨪙𰴞𝚜𨍕𬌉𧫎𫒫𩕄𬅰𭄶𪂃𫛥𤒋𬎢𱧡篆𩱍𗸮𱙊𣹋𰚔𧯶𬟄𣵍𬳮𦧥𫚀𡻐𒇓𫤎𭖿𧫢𨭕𮦞𱐇𡳗𨠏𬍇𱶂𣕴𨀪𭷂𣳝𬽚𪅬𥇋𰋖𫥍𱴄𨎤𧳼𠘹𡤪𢰖𫊂𨢷🄩𭏓𬠀𥽛𱧏𤇜𰖅𱰮𦦡𰋎𱳉𨎾𨲳𩖤𧰨𰓡𤇪𧴩𧯊𰿗𬴠𧡃𡑠𮨾𫾒𱐗𨼯𤇞𠮵𮒊𦍾𰦊𧸋𥰓𤯒𣞵🁃𫙟𬯶𮟽𬍪𪑤𭹮𮄿𨻢𣿼𰅘𣥼𨆯𰤷𭩓𩲊𥞪𦉭𨃢𪮅𪙛𮑉𱘲𠧄𬄼𧴻芳𐀀𰈙𰞲𝡅𡧥𬣊𭶭𧘵𪹊𱰓𢡙𣞀𱕝𪏟𱔨𨎐𱋉𱘒𫍙𧤒𬀓𬒅𤋬𰳍𱽰𭉵𬔜𪐝𠢅𮦐𬓋𡟞𪅥𪠥𱙰𠂁𪧾𮂶𣳛𪠬𧸏扝𩋕𣼲𩯪𮚭𩧃𫧪𝚋𤀘𬷌𦰁𫹆𠃵𭅓𭈜𩕯𞡄𧸧𤅨𝢁𡏀𥢞𬣲𪣕𩂜𨼷𭅁𬨀𬄃𮅽𱗳𬅧𱣈𮦪𧊏𰐈𣱡𬍃𱉑𮐷𣊶𮃭𱎭𫥇𥊉𨘙𪷡𭒔𫯶𰁯𩤢𧢹𪑕𪟬𭄨𨴹𪺚𢈒𦓷𧑠𱓺𮖕𠀁𩈰𧷸𤠟𭻇𭒢𱩧𠷚𡼃𰻮𨹓𬢁𪥁𬽹𧤎𬪦𭒼𮜺𠥞𣱕𧱑𮎎𩚯𭣾𨇁𧷜𱱭𰦛𥦝𥹁𭫦𭊾𧆽𱟍🖦𦘵𰬲𭭑𤟉𩘴𱊅𢍀𬏓𪰂𮭨𪞟𱚾瀹𥐅𭀋𪶉𫌴𫿚𮍃𧐂𡤆𮁄𮞅𫋊𱈴𦭼𰑎𱕠𮡟𱱞𨑁𬥪𥆯𤎓𭔞𪡉𩧹𧷼𬤔𥱨𪥨𫾔𩗫𣸈𮪲𦎝𲂭𮐬𰌚𬊗𥭪𡑫𧰭𬡃𭔠𬶰𨭸𨖵𤧐𬆅𩲦𧊏𤬄𰯜𬣂𣩇𡙤𨀿𢤄𦰓𡁚𬕛𦹲𧣘𬆨𱇙𝆜𫼛𰻖𩒅𬴣𬿚𰾤𭤳𮆠𣄠𮕩𠆖𡺎𧅾𫁿𰡲𩚃𢖓𲌜𡎵𬞒𭣧𱀷𱰧𱹻𰯴𰮲𱨩𱜘𩷰𩰘𭆉𦆝𨦀𪄀娧𦳈𬖦𱄂𮏿𲉃𧼕𱰰𦃝𭩑𰳚𱖾𱃝𱯾𮊂𨫗𭰖𰘖𰞁𬯼𧗃𡀔𫉕𫢝𬼥𰒈𥨄𧺄𮪲𧤌𬼜𤶡𮇅𫡧𭰗𪵯𱡚𠭤𭈶𥫔𰳳𩢰𮧁𧩚𭘢𰧐𰈜𤆤𱻳𬂲𩽝𱪄𬗭𨰞𭌎𱬆𱼠𰝴𩤁𭟑𱌻𰴃𨧅𝉂𭿨𰋻𮦨𲅐𦆍𱤆𤓄𭼕虜𱙡𰷌𮥐𮖑𭷄𩖤𱒄𮌶𲂦𦂺𩊌裞𫡺𭛃𪥰𥾓𭡐𭴭𮓴𪮍𲂾𧀤𭡰𩰮𭐬𬏆𪅉𬜡𮃀𣾦𰂯𱘊𥺆𱳘𬯺𪯖𰁑𪩊𭒬𨴰𩬹𠕾𭪄𫘅𩵴𬨠𢈳𰼬𰣼拔𰒿𱳄𤦭𬇊𫑒𦰀𥞰𰹄𬂦𬭦𪩟𩴞𣶴𰍐𰂞𪑭𰾶𭮐𱣺𱒶𪩝𭍃𠩔𭯈𱸴𮕓𭳰𭏵𦸄𪨼𬆆𞴴𰈉𮫽𬱺𰥠𮍖𫐂𧙈𰚑𨆐𮡢𭘧𬅮𨟱𭃤𰋰𱬴𦸬𡇎𭅄𭳚𱠚𩚜𰟈𱿈𰥞𰩤𬲙🤈𨴾𫍼𡷢𮊐𩉆𧚺𭎦𰅕𰼒𰺐𭡰𰹪𰿔𰼴𲎬𧨚𣻞𭀓𪒍𨿅𮜝𩃮𱡼𮎪𨔶𱉊𮝆𱾀𬫂𱃺𱀕𱯔𲉾𱒸𱂎𰿫𰁀𬿵𲅲𬅯𪗒𦁐𱦼𱁱𫬒𮐆𰃱𭣢𱋐𲍠𪗄𨻑𰓟𲉮𬰐𮀡𭺤𱫸𧏘𰲄𰇸𱷼𲊕𰀦𭗤𱁌𪥭𭩚𱼾𪜞𮈼𱄐𱩊𭡠𭽃𱽣𬎜𰔔𪝓𮄅𰊆𮁌𱕨𭗌𪷺𰦉𞡃𱢮𮪥𱸬🏬𫂔𱨁𰇣𪮲𫼤𨳪𫍢𱗬𭚅𫊌𱶚𬶦𬭮𪖺𭳥𩃘𫔿𰖘𱞮𱫊𮉀𨥎𩶝𨍈𦽌𬻨𡹦𰔏𮗘𣀻𰚢𭥦𱐈𮚢𰷎𬭁𰄼𰐆𰆜𱂟𰢪𬙞𬐖𱝂𱄞𫕺𰞰沿𧤌𮞠𰋛𩔙𩻄𰜧𱎈𫊔𭾄𰗖𰱕𩘎𮞩𪶘𰳵𥎬𤨸𪲦𪓮𬞺𭲨𰷠𫪬𱯾𱪘𥥘𣆼𰜐𮖜𫫿𨣜𫍪𰾨𰅒𮑈𰤎𱷾𱃴𱀼𰈊𭐪𭁹𩐩𭭮𲊖𬩮𬥮𭹁𩆼𮒙";for(aG i=0;i<32768;i++){long long x=(aG)s[i]-65536LL-157202LL;if(x<0)x+=81788929LL;aC[i]=(aG)(x*81788851LL%81788929LL);}}};aE ah PL1 poly_leaf_cache1{};
extern ac u32 poly_leaf_cache[32768] asm("poly_leaf_cache");aE ay bF;
class NTT {
mutable int z_ = 0;
public:
u32 mod;
private:
aE ac int LG = 32;
mc_ mt;
mv_ mts;
u32 w[4], wr[4];
u32 rinv = 1;
ao bG, bH;
ao wd_x4[LG], wrd_x4[LG];
ao bI;
ao bq[LG];
public:
NTT(u32 mod) : mod(mod), mt(mod), mts(mod) {
ac mc_ mt = this->mt;
ah u32 pr_root = 7;
int lg = br(mod - 1);
assert(lg <= LG);
{ u32 e = mod - 2, b = mt.r, acc = 1;
while (e) { if (e & 1) acc = (u32)((u64)acc * b % mod); b = (u32)((u64)b * b % mod); e >>= 1; }
rinv = acc; }
memset(w, 0, be(w));
memset(wr, 0, be(wr));
memset(wd_x4, 0, be(wd_x4));
memset(wrd_x4, 0, be(wrd_x4));
memset(bq, 0, be(bq));
std::vector<u32> vec(lg + 1), aY(lg + 1);
vec[lg] = mt.power<ag, ae>(pr_root, (mod - 1) >> lg);
aY[lg] = mt.power<ae, ae>(vec[lg], mod - 2);
for (int i = lg - 1; i >= 0; i--) {
vec[i] = mt.mul<ae>(vec[i + 1], vec[i + 1]);
aY[i] = mt.mul<ae>(aY[i + 1], aY[i + 1]);
}
w[0] = wr[0] = mt.r;
if (lg >= 2) {
w[1] = vec[2], wr[1] = aY[2];
if (lg >= 3) {
w[2] = vec[3], wr[2] = aY[3];
w[3] = mt.mul<ae>(w[1], w[2]);
wr[3] = mt.mul<ae>(wr[1], wr[2]);
}
}
bG = (ao)ba(w[0], w[0], w[0], w[1]);
bH = (ao)ba(wr[0], wr[0], wr[0], wr[1]);
bI = (ao)ba(w[0], w[1], w[2], w[3]);
u32 prf = mt.r, prf_r = mt.r;
for (int i = 0; i < lg - 2; i++) {
u32 f = mt.mul<ae>(prf, vec[i + 3]), fr = mt.mul<ae>(prf_r, aY[i + 3]);
prf = mt.mul<ae>(prf, aY[i + 3]), prf_r = mt.mul<ae>(prf_r, vec[i + 3]);
u32 f2 = mt.mul<ae>(f, f), f2r = mt.mul<ae>(fr, fr);
wd_x4[i] = (ao)ba(f2, f, f2, f);
wrd_x4[i] = (ao)ba(f2r, fr, f2r, fr);
}
prf = mt.r;
for (int i = 0; i < lg - 3; i++) {
u32 f = mt.mul<ae>(prf, vec[i + 4]);
prf = mt.mul<ae>(prf, aY[i + 4]);
bq[i] = (ao)_mm256_set1_epi64x(f);
}
}
private:
aE ac int L0 = 3;
int bs(int lg) ac { av lg % 2 == L0 % 2 ? L0 : L0 + 1; }
aE aa mul_pre_x(aa a, aa a1, aa w, ac mv_ &mts) {
ac ab ninv = (ab)mv_::az;
ab wn = an((ab)w, ninv);
ab m0 = an((ab)a, wn), m1 = an((ab)a1, wn);
ab p0 = an((ab)a, (ab)w), p1 = an((ab)a1, (ab)w);
p0 = aR(p0, an(m0, (ab)mts.mod));
p1 = aR(p1, an(m1, (ab)mts.mod));
av (aa)bB(aM(p0, 4), p1);
}
aE aP((bc)) aS aa am(aa a, aa w, ac aa &wn, ac mv_ &mts) {
ab a1 = aM((ab)a, 4);
ab m0 = an((ab)a, (ab)wn), m1 = an(a1, (ab)wn);
ab p0 = an((ab)a, (ab)w), p1 = an(a1, (ab)w);
p0 = aR(p0, an(m0, (ab)mts.mod));
p1 = aR(p1, an(m1, (ab)mts.mod));
av (aa)bB(aM(p0, 4), p1);
}
aE aP((bc)) aS aa bY(aa a, aa a1, aa w, ac aa &wn, ac mv_ &mts) {
ab m0 = an((ab)a, (ab)wn), m1 = an((ab)a1, (ab)wn);
ab p0 = an((ab)a, (ab)w), p1 = an((ab)a1, (ab)w);
p0 = aR(p0, an(m0, (ab)mts.mod));
p1 = aR(p1, an(m1, (ab)mts.mod));
av (aa)bB(aM(p0, 4), p1);
}
aE aa bh(aa a, aa w, ac mv_ &mts) {
ac ab ninv = (ab)mv_::az;
ab a1 = aM((ab)a, 4);
ab wn = an((ab)w, ninv);
ab m0 = an((ab)a, wn), m1 = an(a1, wn);
ab p0 = an((ab)a, (ab)w), p1 = an(a1, (ab)w);
p0 = aR(p0, an(m0, (ab)mts.mod));
p1 = aR(p1, an(m1, (ab)mts.mod));
av (aa)bB(aM(p0, 4), p1);
}
aD <ay aF, ay aB>
aE aA ap(aa &a, aa &b, aa w, aa wn, ac mv_ &mts) {
if ah (!aF) {
b = aB ? b : bh(b, w, mts);
al x = a + b;
b = a + mts.af - b;
a = x;
} as {
al x = mts.aQ(a + b);
b = aB ? mts.shrink2_n(a - b) : bh(a + mts.af - b, w, mts);
a = x;
}
}
aD <int k, ay aF, ay aB = ag>
aP((bc)) aS aA tf_(int i, u32 *aC, ac mv_ &mts) ac {
tfb_<k, aF, aB>(aC + i - z_,
(aF ? fr_::aF : fr_::bd).aC[aG(i) >> (k + 2)], mts);
}
aD <int k, ay aF, ay aB = ag>
aP((bc)) aS aA tfb_(u32 *bt, ac fr_::bD &tw,
ac mv_ &mts) ac {
aa w1 = (aa)at(tw.w1), w2 = (aa)at(tw.w2),
w3 = (aa)at(tw.w3);
aa au = (aa)at(aF ? 38830621 : 42958308);
aa root_n = (aa)at(aF ? 1259306467 : 3035660828);
aI(64) aa wns[4] = {
(aa)an((ab)w1,(ab)mv_::az),
(aa)an((ab)w2,(ab)mv_::az),
(aa)an((ab)w3,(ab)mv_::az),
(aa)an((ab)au,(ab)mv_::az)};
if ah (aB) {
w3 = au;
}
if ah(aF && k==3){
ah int ad=1<<k;
u32 *ac p=bt;
al a=aj(p),b=aj(p+ad),c=aj(p+2*ad),d=aj(p+3*ad);
ac al p4=mts.af+mts.af,p8=p4+p4,p16=p8+p8;
ac al u=a+b,s=c+d,v=a+p8-b;
ac al t=am(c+p8-d, au, wns[3], mts);
al sum=u+s;
sum=(aa)aL((ab)sum,(ab)(sum-p16));
sum=(aa)aL((ab)sum,(ab)(sum-p8));
sum=(aa)aL((ab)sum,(ab)(sum-p4));
a=mts.aQ(sum);
if ah(aB){
al bR=[&](aa z){
z=(aa)aL((ab)z,(ab)(z-p16));
z=(aa)aL((ab)z,(ab)(z-p8));
z=(aa)aL((ab)z,(ab)(z-p4));
av mts.aQ(z);
};
c=bR(u+p16-s);b=bR(v+t);d=bR(v+mts.af-t);
}as{
c=am(u+p16-s, w1, wns[0], mts);
b=am(v+t, w2, wns[1], mts);
d=am(v+mts.af-t, w3, wns[2], mts);
}
ak(p,a);ak(p+ad,b);ak(p+2*ad,c);ak(p+3*ad,d);
av;
}
if ah (aF && !aB && k >= 5) {
ac int ad = 1 << k;
for (int j = 0; j < ad; j += 16) {
u32 *p = bt + j;
u32 *q = p + 8;
if ah (k >= 13) {
if ((j & 15) == 0 && j + 96 <= ad - 8) {
aw((ac ar *)(p + 96), ax);
aw((ac ar *)(p + ad + 96), ax);
aw((ac ar *)(p + 2 * ad + 96), ax);
aw((ac ar *)(p + 3 * ad + 96), ax);
}
}
al a = aj(p), b = aj(p + ad), c = aj(p + ad * 2),
d = aj(p + ad * 3);
al e = aj(q), f = aj(q + ad), g = aj(q + ad * 2),
h = aj(q + ad * 3);
al u = a + b, s = c + d, v = a + mts.af - b;
al t = am(c + mts.af - d, au, wns[3], mts);
al u2 = e + f, s2 = g + h, v2 = e + mts.af - f;
al t2 = am(g + mts.af - h, au, wns[3], mts);
al sum = u + s;
sum = (aa)aL((ab)sum, (ab)(sum - mts.af - mts.af));
a = mts.aQ(sum);
al sum2 = u2 + s2;
sum2 = (aa)aL((ab)sum2, (ab)(sum2 - mts.af - mts.af));
e = mts.aQ(sum2);
c = am(u + mts.af + mts.af - s, w1, wns[0], mts);
g = am(u2 + mts.af + mts.af - s2, w1, wns[0], mts);
b = am(v + t, w2, wns[1], mts);
f = am(v2 + t2, w2, wns[1], mts);
d = am(v + mts.af - t, w3, wns[2], mts);
h = am(v2 + mts.af - t2, w3, wns[2], mts);
ak(p, a);
ak(p + ad, b);
ak(p + 2 * ad, c);
ak(p + 3 * ad, d);
ak(q, e);
ak(q + ad, f);
ak(q + 2 * ad, g);
ak(q + 3 * ad, h);
}
av;
}
ac u32*in0=bt;ac u32*in1=bt+(1<<k);if ah(k==15&&aF&&aB){if(bF){in0=poly_leaf_cache;in1=poly_leaf_cache1.aC;}}
for (int j = 0; j < (1 << k); j += 8) {
u32 *p = bt + j;
int ad = 1 << k;
if ah (k >= 13 && aF) {
if ((j & 15) == 0 && j + 96 <= ad - 8) {
aw((ac ar *)(p + 96), ax);
aw((ac ar *)(p + ad + 96), ax);
aw((ac ar *)(p + 2 * ad + 96), ax);
aw((ac ar *)(p + 3 * ad + 96), ax);
}
}
al a = aj(in0+j), b = aj(in1+j), c = aj(p + ad * 2),
d = aj(p + ad * 3);
if ah (!aF) {
if ah (aB) {
ap<ag, ae>(a, c, w1, w1, mts);
ap<ag, ae>(b, d, w1, w1, mts);
ap<ag, ae>(a, b, w2, w2, mts);
ap<ag, ag>(c, d, w3, w3, mts);
} as {
al cc = am(c, w1, wns[0], mts), bb = am(b, w2, wns[1], mts), dd = am(d, w3, wns[2], mts);
al A = a + cc, C = a + mts.af - cc, B = bb + dd;
al D = am(bb + mts.af - dd, au, wns[3], mts);
a = A + B;
b = A + mts.af + mts.af - B;
c = C + D;
d = C + mts.af - D;
}
} as {
if ah (aB) {
ap<ae, ae>(a, b, w2, w2, mts);
ap<ae, ag>(c, d, w3, w3, mts);
ap<ae, ae>(a, c, w1, w1, mts);
ap<ae, ae>(b, d, w1, w1, mts);
} as {
al u = a + b, s = c + d, v = a + mts.af - b;
al t = am(c + mts.af - d, au, wns[3], mts);
al sum = u + s;
sum = (aa)aL((ab)sum, (ab)(sum - mts.af - mts.af));
a = mts.aQ(sum);
c = am(u + mts.af + mts.af - s, w1, wns[0], mts);
b = am(v + t, w2, wns[1], mts);
d = am(v + mts.af - t, w3, wns[2], mts);
}
}
ak(p, a);
ak(p + ad, b);
ak(p + 2 * ad, c);
ak(p + 3 * ad, d);
}
}
aD <int k, ay aB = ag, ay aN = ag>
aP((bc)) aS aA tp_(int i, u32 *aC, u32 *data2,
ac mv_ &mts) ac {
tpb_<k, aB, aN>(aC + i - z_, data2 + i - z_,
fr_::bd.aC[aG(i) >> (k + 2)], mts);
}
aD <int k, ay aB = ag, ay aN = ag>
aP((bc)) aS aA tpb_(ac u32 *base, ac u32 *base2,
ac fr_::bD &tw, ac mv_ &mts) ac {
aa w1 = (aa)at(tw.w1), w2 = (aa)at(tw.w2),
w3 = (aa)at(tw.w3);
aa au = (aa)at(42958308);
aa root_n = (aa)at(3035660828);
if ah (aB) {
w3 = au;
}
ac int ad = 1 << k;
aI(64) aa wns[4] = {
(aa)an((ab)w1,(ab)mv_::az),
(aa)an((ab)w2,(ab)mv_::az),
(aa)an((ab)w3,(ab)mv_::az),
(aa)an((ab)au,(ab)mv_::az)};
if (k >= 5) {
for (int j = 0; j < ad; j += 16) {
u32 *p0 = bf<u32 *>(base) + j;
u32 *q0 = bf<u32 *>(base2) + j;
if ah (k >= 13) {
aw((ac ar *)(p0 + 256), ax);
aw((ac ar *)(p0 + ad + 256), ax);
aw((ac ar *)(p0 + 2 * ad + 256), ax);
aw((ac ar *)(p0 + 3 * ad + 256), ax);
aw((ac ar *)(q0 + 256), ax);
aw((ac ar *)(q0 + ad + 256), ax);
aw((ac ar *)(q0 + 2 * ad + 256), ax);
aw((ac ar *)(q0 + 3 * ad + 256), ax);
}
{
u32 *p = p0;
u32 *q = q0;
al a = aj(p), b = aj(p + ad), c = aj(p + ad * 2),
d = aj(p + ad * 3);
al e = aj(q), f = aj(q + ad), g = aj(q + ad * 2),
h = aj(q + ad * 3);
aa A1, B1, C1, D1, A2, B2, C2, D2;
if ah (aB) {
ap<ag, ae>(a, c, w1, w1, mts);
ap<ag, ae>(b, d, w1, w1, mts);
ap<ag, ae>(e, g, w1, w1, mts);
ap<ag, ae>(f, h, w1, w1, mts);
ap<ag, ae>(a, b, w2, w2, mts);
ap<ag, ag>(c, d, w3, w3, mts);
ap<ag, ae>(e, f, w2, w2, mts);
ap<ag, ag>(g, h, w3, w3, mts);
} as {
al cc = am(c, w1, wns[0], mts), bb = am(b, w2, wns[1], mts), dd = am(d, w3, wns[2], mts);
al gg = am(g, w1, wns[0], mts), ff = am(f, w2, wns[1], mts), hh = am(h, w3, wns[2], mts);
A1 = a + cc, C1 = a + mts.af - cc, B1 = bb + dd;
D1 = am(bb + mts.af - dd, au, wns[3], mts);
A2 = e + gg, C2 = e + mts.af - gg, B2 = ff + hh;
D2 = am(ff + mts.af - hh, au, wns[3], mts);
a = A1 + B1;
b = A1 + mts.af + mts.af - B1;
c = C1 + D1;
d = C1 + mts.af - D1;
e = A2 + B2;
f = A2 + mts.af + mts.af - B2;
g = C2 + D2;
h = C2 + mts.af - D2;
}
if ah(!aN)ak(p, a);
if ah(!aN)ak(p + ad, b);
ak(p + 2 * ad, c);
ak(p + 3 * ad, d);
if ah(!aN)ak(q, e);
if ah(!aN)ak(q + ad, f);
ak(q + 2 * ad, g);
ak(q + 3 * ad, h);
}
{
u32 *p = p0 + 8;
u32 *q = q0 + 8;
al a = aj(p), b = aj(p + ad), c = aj(p + ad * 2),
d = aj(p + ad * 3);
al e = aj(q), f = aj(q + ad), g = aj(q + ad * 2),
h = aj(q + ad * 3);
aa A1, B1, C1, D1, A2, B2, C2, D2;
if ah (aB) {
ap<ag, ae>(a, c, w1, w1, mts);
ap<ag, ae>(b, d, w1, w1, mts);
ap<ag, ae>(e, g, w1, w1, mts);
ap<ag, ae>(f, h, w1, w1, mts);
ap<ag, ae>(a, b, w2, w2, mts);
ap<ag, ag>(c, d, w3, w3, mts);
ap<ag, ae>(e, f, w2, w2, mts);
ap<ag, ag>(g, h, w3, w3, mts);
} as {
al cc = bY(c, (aa)LDU(p + ad * 2 + 1), w1, wns[0], mts), bb = am(b, w2, wns[1], mts), dd = am(d, w3, wns[2], mts);
al gg = am(g, w1, wns[0], mts), ff = am(f, w2, wns[1], mts), hh = am(h, w3, wns[2], mts);
A1 = a + cc, C1 = a + mts.af - cc, B1 = bb + dd;
D1 = am(bb + mts.af - dd, au, wns[3], mts);
A2 = e + gg, C2 = e + mts.af - gg, B2 = ff + hh;
D2 = am(ff + mts.af - hh, au, wns[3], mts);
a = A1 + B1;
b = A1 + mts.af + mts.af - B1;
c = C1 + D1;
d = C1 + mts.af - D1;
e = A2 + B2;
f = A2 + mts.af + mts.af - B2;
g = C2 + D2;
h = C2 + mts.af - D2;
}
if ah(!aN)ak(p, a);
if ah(!aN)ak(p + ad, b);
ak(p + 2 * ad, c);
ak(p + 3 * ad, d);
if ah(!aN)ak(q, e);
if ah(!aN)ak(q + ad, f);
ak(q + 2 * ad, g);
ak(q + 3 * ad, h);
}
}
} as {
for (int j = 0; j < ad; j += 8) {
u32 *p = bf<u32 *>(base) + j;
u32 *q = bf<u32 *>(base2) + j;
if ah (k >= 13) {
if ((j & 15) == 0) {
aw((ac ar *)(p + 256), ax);
aw((ac ar *)(p + ad + 256), ax);
aw((ac ar *)(p + 2 * ad + 256), ax);
aw((ac ar *)(p + 3 * ad + 256), ax);
aw((ac ar *)(q + 256), ax);
aw((ac ar *)(q + ad + 256), ax);
aw((ac ar *)(q + 2 * ad + 256), ax);
aw((ac ar *)(q + 3 * ad + 256), ax);
}
}
al a = aj(p), b = aj(p + ad), c = aj(p + ad * 2),
d = aj(p + ad * 3);
al e = aj(q), f = aj(q + ad), g = aj(q + ad * 2),
h = aj(q + ad * 3);
aa A1, B1, C1, D1, A2, B2, C2, D2;
if ah (aB) {
ap<ag, ae>(a, c, w1, w1, mts);
ap<ag, ae>(b, d, w1, w1, mts);
ap<ag, ae>(e, g, w1, w1, mts);
ap<ag, ae>(f, h, w1, w1, mts);
ap<ag, ae>(a, b, w2, w2, mts);
ap<ag, ag>(c, d, w3, w3, mts);
ap<ag, ae>(e, f, w2, w2, mts);
ap<ag, ag>(g, h, w3, w3, mts);
} as {
al cc = am(c, w1, wns[0], mts), bb = am(b, w2, wns[1], mts), dd = am(d, w3, wns[2], mts);
al gg = am(g, w1, wns[0], mts), ff = am(f, w2, wns[1], mts), hh = am(h, w3, wns[2], mts);
A1 = a + cc, C1 = a + mts.af - cc, B1 = bb + dd;
D1 = am(bb + mts.af - dd, au, wns[3], mts);
A2 = e + gg, C2 = e + mts.af - gg, B2 = ff + hh;
D2 = am(ff + mts.af - hh, au, wns[3], mts);
a = A1 + B1;
b = A1 + mts.af + mts.af - B1;
c = C1 + D1;
d = C1 + mts.af - D1;
e = A2 + B2;
f = A2 + mts.af + mts.af - B2;
g = C2 + D2;
h = C2 + mts.af - D2;
}
if ah(!aN)ak(p, a);
if ah(!aN)ak(p + ad, b);
ak(p + 2 * ad, c);
ak(p + 3 * ad, d);
if ah(!aN)ak(q, e);
if ah(!aN)ak(q + ad, f);
ak(q + 2 * ad, g);
ak(q + 3 * ad, h);
}
}
}
aD <int Q, ay aB>
aP((bc)) aS aA q19_gen(int aq, u32 *aC, u32 *data2,
ac aG ar *bp, ac mv_ &mts) ac {
ac al &tw = fr_::bd.aC[aG(aq) >> 19];
aa w1 = (aa)at(tw.w1), w2 = (aa)at(tw.w2),
w3 = (aa)at(tw.w3);
aa au = (aa)at(42958308);
if ah (aB) {
w3 = au;
}
ah int ad = 1 << 17;
aI(64) aa wns[4] = {
(aa)an((ab)w1,(ab)mv_::az),
(aa)an((ab)w2,(ab)mv_::az),
(aa)an((ab)w3,(ab)mv_::az),
(aa)an((ab)au,(ab)mv_::az)};
aI(32) u32 tbl[8];
u32 rt = mt.mul(w[1], 1);
for (int q = 0; q < 8; q++) tbl[q] = u64(rt) * q % mod;
ac aa t0 = aj(tbl);
ac ab aZ = at(u64(rt) * 8 % mod);
ac ab m15 = at(15), seven = at(7);
al gen = [&](int pos) -> aa {
ab x = b7(_mm_loadl_epi64((ac __m128i *)(bp + pos)));
aa lo = (aa)bu(x, m15);
aa hi = (aa)_mm256_srli_epi32(x, 4);
if ah (Q == 0) av lo + hi;
if ah (Q == 1) av lo + mts.af - hi;
aa v = (aa)bo(a4((ab)t0,(ab)hi),
bu(aZ,bJ((ab)hi,seven)));
if ah (Q == 2) av lo + v;
av lo + mts.af - v;
};
u32 *base = aC, *base2 = data2;
for (int j = 0; j < ad; j += 16) {
u32 *p0 = bf<u32 *>(base) + j;
u32 *q0 = bf<u32 *>(base2) + j;
{
aw((ac ar *)(p0 + 256), ax);
aw((ac ar *)(p0 + ad + 256), ax);
aw((ac ar *)(p0 + 2 * ad + 256), ax);
aw((ac ar *)(p0 + 3 * ad + 256), ax);
aw((ac ar *)(bp + j + 256), ax);
aw((ac ar *)(bp + j + ad + 256), ax);
aw((ac ar *)(bp + j + 2 * ad + 256), ax);
aw((ac ar *)(bp + j + 3 * ad + 256), ax);
}
{
u32 *p = p0;
u32 *q = q0;
al a = aj(p), b = aj(p + ad), c = aj(p + ad * 2),
d = aj(p + ad * 3);
al e = gen(j), f = gen(j + ad), g = gen(j + 2 * ad), h = gen(j + 3 * ad);
aa A1, B1, C1, D1, A2, B2, C2, D2;
if ah (aB) {
ap<ag, ae>(a, c, w1, w1, mts);
ap<ag, ae>(b, d, w1, w1, mts);
ap<ag, ae>(e, g, w1, w1, mts);
ap<ag, ae>(f, h, w1, w1, mts);
ap<ag, ae>(a, b, w2, w2, mts);
ap<ag, ag>(c, d, w3, w3, mts);
ap<ag, ae>(e, f, w2, w2, mts);
ap<ag, ag>(g, h, w3, w3, mts);
} as {
al cc = am(c, w1, wns[0], mts), bb = am(b, w2, wns[1], mts), dd = am(d, w3, wns[2], mts);
al gg = am(g, w1, wns[0], mts), ff = am(f, w2, wns[1], mts), hh = am(h, w3, wns[2], mts);
A1 = a + cc, C1 = a + mts.af - cc, B1 = bb + dd;
D1 = am(bb + mts.af - dd, au, wns[3], mts);
A2 = e + gg, C2 = e + mts.af - gg, B2 = ff + hh;
D2 = am(ff + mts.af - hh, au, wns[3], mts);
a = A1 + B1;
b = A1 + mts.af + mts.af - B1;
c = C1 + D1;
d = C1 + mts.af - D1;
e = A2 + B2;
f = A2 + mts.af + mts.af - B2;
g = C2 + D2;
h = C2 + mts.af - D2;
}
ak(p, a);
ak(p + ad, b);
ak(p + 2 * ad, c);
ak(p + 3 * ad, d);
ak(q, e);
ak(q + ad, f);
ak(q + 2 * ad, g);
ak(q + 3 * ad, h);
}
{
u32 *p = p0 + 8;
u32 *q = q0 + 8;
al a = aj(p), b = aj(p + ad), c = aj(p + ad * 2),
d = aj(p + ad * 3);
al e = gen(j + 8), f = gen(j + 8 + ad), g = gen(j + 8 + 2 * ad), h = gen(j + 8 + 3 * ad);
aa A1, B1, C1, D1, A2, B2, C2, D2;
if ah (aB) {
ap<ag, ae>(a, c, w1, w1, mts);
ap<ag, ae>(b, d, w1, w1, mts);
ap<ag, ae>(e, g, w1, w1, mts);
ap<ag, ae>(f, h, w1, w1, mts);
ap<ag, ae>(a, b, w2, w2, mts);
ap<ag, ag>(c, d, w3, w3, mts);
ap<ag, ae>(e, f, w2, w2, mts);
ap<ag, ag>(g, h, w3, w3, mts);
} as {
al cc = bY(c, (aa)LDU(p + ad * 2 + 1), w1, wns[0], mts), bb = am(b, w2, wns[1], mts), dd = am(d, w3, wns[2], mts);
al gg = am(g, w1, wns[0], mts), ff = am(f, w2, wns[1], mts), hh = am(h, w3, wns[2], mts);
A1 = a + cc, C1 = a + mts.af - cc, B1 = bb + dd;
D1 = am(bb + mts.af - dd, au, wns[3], mts);
A2 = e + gg, C2 = e + mts.af - gg, B2 = ff + hh;
D2 = am(ff + mts.af - hh, au, wns[3], mts);
a = A1 + B1;
b = A1 + mts.af + mts.af - B1;
c = C1 + D1;
d = C1 + mts.af - D1;
e = A2 + B2;
f = A2 + mts.af + mts.af - B2;
g = C2 + D2;
h = C2 + mts.af - D2;
}
ak(p, a);
ak(p + ad, b);
ak(p + 2 * ad, c);
ak(p + 3 * ad, d);
ak(q, e);
ak(q + ad, f);
ak(q + 2 * ad, g);
ak(q + 3 * ad, h);
}
}
}
aA q19_after(int aq, u32 *a, u32 *b) ac {
ac mv_ mts;
for (int j = 0; j < 4; j++) bv<17>(aq + (j << 17), a, b);
if (aq == 0) tf_<17, ae, ae>(aq, a, mts);
as tf_<17, ae>(aq, a, mts);
}
aD <int k, ay aB = ag>
aP((bc)) aS aA b8(int i, u32 *aC, u32 *limb0, u32 *limb1, u32 *limb2, u32 *limb3,
ac mv_ &mts) ac {
ac al &tw = fr_::bd.aC[aG(i) >> (k + 2)];
aa w1 = (aa)at(tw.w1), w2 = (aa)at(tw.w2),
w3 = (aa)at(tw.w3);
aa au = (aa)at(42958308);
aa root_n = (aa)at(3035660828);
if ah (aB) {
w3 = au;
}
ac int ad = 1 << k;
ac u32 *base = aC + i - z_;
aI(64) aa wns[4] = {
(aa)an((ab)w1,(ab)mv_::az),
(aa)an((ab)w2,(ab)mv_::az),
(aa)an((ab)w3,(ab)mv_::az),
(aa)an((ab)au,(ab)mv_::az)};
for (int j = 0; j < ad; j += 8) {
u32 *p = bf<u32 *>(base) + j;
if ((j & 15) == 0 && j + 128 <= ad - 8) {
aw((ac ar *)(p + 128), ax);
aw((ac ar *)(p + ad + 128), ax);
aw((ac ar *)(p + 2 * ad + 128), ax);
aw((ac ar *)(p + 3 * ad + 128), ax);
aw((ac ar *)(limb0 + j + 128), ax);
aw((ac ar *)(limb1 + j + 128), ax);
aw((ac ar *)(limb2 + j + 128), ax);
aw((ac ar *)(limb3 + j + 128), ax);
}
al a = aj(p), b = aj(p + ad), c = aj(p + ad * 2),
d = aj(p + ad * 3);
al e = aj(limb0 + j), f = aj(limb1 + j), g = aj(limb2 + j),
h = aj(limb3 + j);
aa A1, B1, C1, D1, A2, B2, C2, D2;
if ah (aB) {
ap<ag, ae>(a, c, w1, w1, mts);
ap<ag, ae>(b, d, w1, w1, mts);
ap<ag, ae>(e, g, w1, w1, mts);
ap<ag, ae>(f, h, w1, w1, mts);
ap<ag, ae>(a, b, w2, w2, mts);
ap<ag, ag>(c, d, w3, w3, mts);
ap<ag, ae>(e, f, w2, w2, mts);
ap<ag, ag>(g, h, w3, w3, mts);
} as {
al cc = am(c, w1, wns[0], mts), bb = am(b, w2, wns[1], mts), dd = am(d, w3, wns[2], mts);
al gg = am(g, w1, wns[0], mts), ff = am(f, w2, wns[1], mts), hh = am(h, w3, wns[2], mts);
A1 = a + cc, C1 = a + mts.af - cc, B1 = bb + dd;
D1 = am(bb + mts.af - dd, au, wns[3], mts);
A2 = e + gg, C2 = e + mts.af - gg, B2 = ff + hh;
D2 = am(ff + mts.af - hh, au, wns[3], mts);
a = A1 + B1;
b = A1 + mts.af + mts.af - B1;
c = C1 + D1;
d = C1 + mts.af - D1;
e = A2 + B2;
f = A2 + mts.af + mts.af - B2;
g = C2 + D2;
h = C2 + mts.af - D2;
}
ak(p, a);
ak(p + ad, b);
ak(p + 2 * ad, c);
ak(p + 3 * ad, d);
ak(limb0 + j, e);
ak(limb1 + j, f);
ak(limb2 + j, g);
ak(limb3 + j, h);
}
}
aD <ay aF, ay aB = ag>
aA aJ(int k, int i, u32 *aC, ao &wi, ac mv_ &mts) ac {
aa w1 = (aa)_mm256_shuffle_epi32((ab)wi, 0b00'00'00'00);
aa w2 = (aa)aV((ab)wi, 0b01'01'01'01);
aa w3 = (aa)aV((ab)wi, 0b11'11'11'11);
aa n1 = (aa)an((ab)w1, (ab)mts.az);
aa n2 = (aa)an((ab)w2, (ab)mts.az);
aa n3 = (aa)an((ab)w3, (ab)mts.az);
for (int j = 0; j < (1 << k); j += 8) {
u32 *p = aC + i + j;
int ad = 1 << k;
al a = aj(p), b = aj(p + ad), c = aj(p + ad * 2),
d = aj(p + ad * 3);
if ah (!aF) {
ap<ag, aB>(a, c, w1, w1, mts);
ap<ag, aB>(b, d, w1, w1, mts);
ap<ag, aB>(a, b, w2, w2, mts);
ap<ag, ag>(c, d, w3, w3, mts);
} as {
if ah (aB) {
ap<ae, ae>(a, b, w2, w2, mts);
ap<ae, ag>(c, d, w3, w3, mts);
ap<ae, ae>(a, c, w1, w1, mts);
ap<ae, ae>(b, d, w1, w1, mts);
} as {
al u = a + b, v = bh(a + mts.af - b, w2, mts);
al s = c + d, t = bh(c + mts.af - d, w3, mts);
al sum = u + s;
sum = (aa)aL((ab)sum, (ab)(sum - mts.af - mts.af));
a = mts.aQ(sum);
b = mts.aQ(v + t);
c = bh(u + mts.af + mts.af - s, w1, mts);
d = bh(v + mts.af - t, w1, mts);
}
}
ak(p, a);
ak(p + ad, b);
ak(p + 2 * ad, c);
ak(p + 3 * ad, d);
}
wi = mts.bQ<ae>(wi, (aF ? wrd_x4 : wd_x4)[br(~i >> k + 2)]);
}
public:
aA bZ(int lg, u32 *aC) ac {
ac mv_ mts = this->mts;
ac int L = bs(lg);
if (L < lg) {
ac int lc = (lg - L) / 2;
ao a5[LG / 2];
std::fill(a5, a5 + lc, bG);
for (int k = lg - 2; k >= L; k -= 2) {
aJ<ag, ae>(k, 0, aC, a5[k - L >> 1], mts);
}
for (int i = 1; i < (1 << lc * 2 - 2); i++) {
int s = br(i) >> 1;
for (int k = s; k >= 0; k--) {
aJ<ag>(2 * k + L, i * (1 << L + 2), aC, a5[k], mts);
}
}
}
}
aD <ay mul_by_sc = ag>
aA transform_inverse(int lg, u32 *aC,
u32 sc = u32()) ac {
ac mv_ mts = this->mts;
ac int L = bs(lg);
if (L < lg) {
ac int lc = (lg - L) / 2;
ao a5[LG / 2];
std::fill(a5, a5 + lc, bH);
for (int i = 0; i < (1 << lc * 2 - 2); i++) {
int s = br(~i) >> 1;
if (i + 1 == (1 << 2 * s)) {
s--;
}
for (int k = 0; k <= s; k++) {
aJ<ae>(2 * k + L, (i + 1 - (1 << 2 * k)) * (1 << L + 2), aC, a5[k], mts);
}
if (i + 1 == (1 << 2 * (s + 1))) {
s++;
aJ<ae, ae>(2 * s + L, (i + 1 - (1 << 2 * s)) * (1 << L + 2), aC, a5[s],
mts);
}
}
}
ac mc_ mt = this->mt;
u32 f = mt.power<ag, ae>((mod + 1) >> 1, lg - L);
if (mul_by_sc) f = mt.mul<ae>(f, mt.mul<ag>(mt.r2, sc));
aa f_x8 = (aa)at(f);
for (int i = 0; i < (1 << lg); i += 8) {
ak(aC + i, mts.bC<ae, ae>(aj(aC + i), f_x8));
}
}
private:
aD <int L, int K, ay a6 = ae, ay b0 = ag>
aP((optimize("O3,unroll-loops,rename-registers"))) aE aA
bj(ac u32 *a, ac u32 *b, u32 *c, ac std::array<aa, K> &ar_w, ac mv_ &mts) {
static_assert(L >= 3);
ah int n = 1 << L;
aI(64) u32 aux_a[K][n * 2];
aI(64) std::conditional_t<L==3,u32,u64> aW[K][n * 2 + (L==3 ? 16 : 0)];
for (int k = 0; k < K; k++) {
for (int i = 0; i < n; i += 8) {
aa ai = aj(a + n * k + i);
if (a6) {
ai = mts.bC<ae, ae>(ai, mts.r2);
} as {
ai = mts.bV<L == 3 ? (b0 ? 3 : 2) : 0>(ai);
}
ak(aux_a[k] + i, ai);
aa bi = aj(b + n * k + i);
aa bi_0 = mts.bV<L == 3 ? 2 : 0>(bi);
aa bi_w = mts.bC<(L != 3), ae>(bi, ar_w[k]);
if ah(L==3){
ak(aW[k]+i,bi_w);
ak(aW[k]+n+i,bi_0);
}as{
ak((u32 *)(aW[k] + i + 0),
(aa)a4((ab)bi_w, ba(0, 1, 2, 3)));
ak((u32 *)(aW[k] + i + 4),
(aa)a4((ab)bi_w, ba(4, 5, 6, 7)));
ak((u32 *)(aW[k] + n + i + 0),
(aa)a4((ab)bi_0, ba(0, 1, 2, 3)));
ak((u32 *)(aW[k] + n + i + 4),
(aa)a4((ab)bi_0, ba(4, 5, 6, 7)));
}
}
}
ao bg[K][n / 4];
for (int k = 0; k < K; k++) {
{
ah int i = 0;
ao ai = (ao)at(aux_a[k][i]);
ao ai1 = (ao)at(aux_a[k][i + 1]);
for (int j = 0; j < n; j += 4) {
ao t0, t1;
asm("vpmuludq %2,%1,%0"
: "=&x"(t0)
: "x"(ai), "m"(*(ac bS *)(aW[k] + n - i + (L==3 ? j/4 : j))));
asm("vpmuludq %3,%2,%1\n\tvpaddq %1,%0,%0"
: "+x"(t0), "=&x"(t1)
: "x"(ai1), "m"(*(ac bS *)(aW[k] + n - i - 1 + (L==3 ? j/4 : j))));
bg[k][j / 4] = t0;
}
}
for (int i = 2; i + 2 <= n; i += 2) {
ao ai = (ao)at(aux_a[k][i]);
ao ai1 = (ao)at(aux_a[k][i + 1]);
for (int j = 0; j < n; j += 4) {
ao t0, t1;
asm("vpmuludq %3,%2,%1\n\tvpaddq %1,%0,%0"
: "+x"(bg[k][j / 4]), "=&x"(t0)
: "x"(ai), "m"(*(ac bS *)(aW[k] + n - i + (L==3 ? j/4 : j))));
asm("vpmuludq %3,%2,%1\n\tvpaddq %1,%0,%0"
: "+x"(bg[k][j / 4]), "=&x"(t1)
: "x"(ai1), "m"(*(ac bS *)(aW[k] + n - i - 1 + (L==3 ? j/4 : j))));
}
if (((i + 1) & 7) == 7 && i + 1 >= 15) {
for (int j = 0; j < n; j += 4) {
bg[k][j / 4] = (ao)mts.aQ((aa)bg[k][j / 4]);
}
}
}
}
bK bL("" ::: "memory");
for (int k = 0; k < K; k++) {
for (int i = 0; i < n; i += 8) {
ao c0 = bg[k][i / 4], c1 = bg[k][i / 4 + 1];
aa res;
if ah(L==3)res=mts.reduce<ag>(c0,c1);
as{
ao n0=(ao)an((ab)c0,(ab)mts.az);
ao n1=(ao)an((ab)c1,(ab)mts.az);
ab r0=aR((ab)c0,an((ab)n0,(ab)mts.mod));
ab r1=aR((ab)c1,an((ab)n1,(ab)mts.mod));
ab z=_mm256_castps_si256(_mm256_shuffle_ps(_mm256_castsi256_ps(r0),_mm256_castsi256_ps(r1),0xdd));
res=(aa)aV(z,0xd8);
}
ak(c + k * n + i, b0 ? res : mts.aQ(res));
}
}
}
aD <int L, ay a6 = ae>
aA b1(int lg, ac u32 *a, ac u32 *b, u32 *c) ac {
ah int sz = 1 << L;
ac mv_ mts = this->mts;
int cnt = 1 << lg - L;
if (cnt == 1) {
bj<L, 1, a6>(a, b, c, {mts.r}, mts);
av;
}
if (cnt <= 8) {
for (int i = 0; i < cnt; i += 2) {
aa wi = (aa)at(w[i / 2]);
bj<L, 2, a6>(a + i * sz, b + i * sz, c + i * sz,
{wi, (mts.mod - wi)}, mts);
}
av;
}
ao wi = bI;
for (int i = 0; i < cnt; i += 8) {
aa aH[4] = {
(aa)aV((ab)wi, 0b00'00'00'00),
(aa)aV((ab)wi, 0b01'01'01'01),
(aa)aV((ab)wi, 0b10'10'10'10),
(aa)aV((ab)wi, 0b11'11'11'11),
};
if (L == L0) {
for (int j = 0; j < 8; j += 4) {
bj<L, 4, a6>(
a + (i + j) * sz, b + (i + j) * sz, c + (i + j) * sz,
{aH[j / 2], mts.mod - aH[j / 2], aH[j / 2 + 1], mts.mod - aH[j / 2 + 1]}, mts);
}
} as {
for (int j = 0; j < 8; j += 2) {
bj<L, 2, a6>(a + (i + j) * sz, b + (i + j) * sz,
c + (i + j) * sz,
{aH[j / 2], mts.mod - aH[j / 2]}, mts);
}
}
wi = mts.bQ<ae>(wi, bq[br(~i >> 3)]);
}
}
public:
aD <ay a6 = ae>
aA multiply_all_leaves(int lg, ac u32 *a, ac u32 *b, u32 *c) ac {
int L = bs(lg);
if (L == L0) {
b1<L0, a6>(lg, a, b, c);
} as {
b1<L0 + 1, a6>(lg, a, b, c);
}
}
aD <int L, ay WideOutput = ag> aA b2(int begin, int end, u32 *a, u32 *b, ao &wi) ac {
ac mv_ mts = this->mts;
ac int bk = z_;
ah int sz = 1 << L;
ac al *twp = fr_::dot.aC + ((begin >> L) >> 3);
for (int i = begin >> L; i < (end >> L); i += 8, ++twp) {
aa aH[4];
if ah (L == 3) {
ac al &tw = *twp;
for (int q = 0; q < 4; q++) aH[q] = (aa)at(tw[q]);
} as {
aH[0] = (aa)aV((ab)wi, 0x00);
aH[1] = (aa)aV((ab)wi, 0x55);
aH[2] = (aa)aV((ab)wi, 0xaa);
aH[3] = (aa)aV((ab)wi, 0xff);
}
if ah (L == L0) {
for(int j=0;j<8;j+=4){
bj<L,4,ag,(WideOutput && L==3)>(
a+(i+j)*sz-bk,b+(i+j)*sz-bk,a+(i+j)*sz-bk,
{aH[j/2],mts.mod-aH[j/2],aH[j/2+1],mts.mod-aH[j/2+1]},mts);
}
} as {
for (int j = 0; j < 8; j += 2)
bj<L, 2, ag>(a + (i + j) * sz - bk, b + (i + j) * sz - bk,
a + (i + j) * sz - bk, {aH[j / 2], mts.mod - aH[j / 2]},
mts);
}
if ah (L != 3) wi = mts.bQ<ae>(wi, bq[br(~i >> 3)]);
}
}
aD <int L> aA bw(int lg, int aq, u32 *a, u32 *b, ao *fw, ao *iw, ao &dot) ac {
ac mv_ mts = this->mts;
if (lg > 11) {
int k = lg - 2;
ao w = fw[k];
if (aq == 0) {
aJ<ag, ae>(k, aq, a, w, mts);
aJ<ag, ae>(k, aq, b, fw[k], mts);
} as {
aJ<ag>(k, aq, a, w, mts);
aJ<ag>(k, aq, b, fw[k], mts);
}
for (int j = 0; j < 4; j++) bw<L>(k, aq + (j << k), a, b, fw, iw, dot);
if (aq == 0)
aJ<ae, ae>(k, aq, a, iw[k], mts);
as
aJ<ae>(k, aq, a, iw[k], mts);
av;
}
int end = aq + (1 << lg);
for (int k = lg - 2; k >= L; k -= 2) {
for (int i = aq; i < end; i += (1 << (k + 2))) {
ao w = fw[k];
if (i == 0) {
aJ<ag, ae>(k, i, a, w, mts);
aJ<ag, ae>(k, i, b, fw[k], mts);
} as {
aJ<ag>(k, i, a, w, mts);
aJ<ag>(k, i, b, fw[k], mts);
}
}
}
b2<L>(aq, end, a, b, dot);
for (int k = L; k <= lg - 2; k += 2)
for (int i = aq; i < end; i += (1 << (k + 2))) {
if (i == 0)
aJ<ae, ae>(k, i, a, iw[k], mts);
as
aJ<ae>(k, i, a, iw[k], mts);
}
}
aD <int K, ay Inv, int aK> aP((noinline)) aA tb_(int aq, u32 *a, u32 *b) ac {
ac mv_ mts;
ah int kStep = 1 << (K + 2);
u32 *pa = a + aq - z_;
u32 *pb = b + aq - z_;
ac fr_::bD *twp =
(Inv ? fr_::aF : fr_::bd).aC + (aG(aq) >> (K + 2));
for (int i = aq; i < aq + aK; i += kStep) {
if ah (Inv) {
if (i == 0)
tfb_<K, ae, ae>(pa, *twp, mts);
as
tfb_<K, ae>(pa, *twp, mts);
} as {
if (i == 0)
tpb_<K, ae>(pa, pb, *twp, mts);
as
tpb_<K>(pa, pb, *twp, mts);
}
pa += kStep;
pb += kStep;
++twp;
}
}
aD <int LG, ay FWD_A = ae, ay FWD_B = ae, ay LEAF = ae, ay INV = ae>
aA bv(int aq, u32 *a, u32 *b) ac {
ac mv_ mts;
if ah(LG==15&&FWD_A&&FWD_B&&LEAF&&INV){if((aq==0||aq==32768)&&bF){av;}}
if ah (LG > 15) {
ah int K = LG - 2;
if ah (FWD_A && FWD_B) {
if (aq == 0){if ah(K==15){if(bF)tp_<K,ae,ae>(aq,a,b,mts);as tp_<K,ae>(aq,a,b,mts);}as tp_<K,ae>(aq,a,b,mts);}
as
tp_<K>(aq, a, b, mts);
} as {
if ah (FWD_A) {
if (aq == 0)
tf_<K, ag, ae>(aq, a, mts);
as
tf_<K, ag>(aq, a, mts);
}
if ah (FWD_B) {
if (aq == 0)
tf_<K, ag, ae>(aq, b, mts);
as
tf_<K, ag>(aq, b, mts);
}
}
for (int j = 0; j < 4; j++) bv<K, FWD_A, FWD_B, LEAF, INV>(aq + (j << K), a, b);
if ah (INV) {
if (aq == 0)
tf_<K, ae, ae>(aq, a, mts);
as
tf_<K, ae>(aq, a, mts);
}
} as {
ah int aK = 1 << LG;
if ah (FWD_A || FWD_B) {
if ah (LG >= 15) tb_<13, ag, aK>(aq, a, b);
if ah (LG >= 13) tb_<11, ag, aK>(aq, a, b);
if ah (LG >= 11) tb_<9, ag, aK>(aq, a, b);
if ah (LG >= 9) tb_<7, ag, aK>(aq, a, b);
if ah (LG >= 7) tb_<5, ag, aK>(aq, a, b);
if ah (LG >= 5) tb_<3, ag, aK>(aq, a, b);
}
if ah (LEAF) {
ao unused_root_an2{};
b2<3,ae>(aq, aq + aK, a, b, unused_root_an2);
}
if ah (INV) {
if ah (LG >= 5) tb_<3, ae, aK>(aq, a, b);
if ah (LG >= 7) tb_<5, ae, aK>(aq, a, b);
if ah (LG >= 9) tb_<7, ae, aK>(aq, a, b);
if ah (LG >= 11) tb_<9, ae, aK>(aq, a, b);
if ah (LG >= 13) tb_<11, ae, aK>(aq, a, b);
if ah (LG >= 15) tb_<13, ae, aK>(aq, a, b);
}
}
}
aA b9(int aq, u32 *a0, u32 *a1, u32 *a2, u32 *a3,
u32 *bscratch, u32 *bM) ac {
ah int ad = 1 << 17;
ac mv_ mts;
z_ = aq;
b8<17>(aq, bscratch, a0, a1, a2, a3, mts);
u32 *alimb[4] = {a0, a1, a2, a3};
for (int j = 0; j < 4; j++) {
z_ = aq + j * ad;
bv<17>(z_, alimb[j], bscratch + j * ad);
}
z_ = aq;
ac al &tw = fr_::aF.aC[aG(aq) >> 19];
ac aa w1 = (aa)at(tw.w1), w2 = (aa)at(tw.w2),
w3 = (aa)at(tw.w3);
ac aa au = (aa)at(38830621);
ac aa root_n = (aa)at(1259306467);
aI(64) aa wns[4] = {
(aa)an((ab)w1,(ab)mv_::az),
(aa)an((ab)w2,(ab)mv_::az),
(aa)an((ab)w3,(ab)mv_::az),
(aa)an((ab)au,(ab)mv_::az)};
for (int j = 0; j < ad; j += 8) {
al a = aj(a0 + j), b = aj(a1 + j);
al c = aj(a2 + j), d = aj(a3 + j);
al u = a + b, s = c + d, v = a + mts.af - b;
al t = am(c + mts.af - d, au, wns[3], mts);
al sum = u + s;
sum = (aa)aL((ab)sum, (ab)(sum - mts.af - mts.af));
a = mts.aQ(sum);
c = am(u + mts.af + mts.af - s, w1, wns[0], mts);
b = am(v + t, w2, wns[1], mts);
d = am(v + mts.af - t, w3, wns[2], mts);
STU(bM + j, a);
STU(bM + ad + j, b);
STU(bM + 2 * ad + j, c);
STU(bM + 3 * ad + j, d);
}
}
aA ca(ac u32 *src, int n, u32 *dst,
u32 *bl, u32 *bm, int lg) ac {
al a7 = [](u32 *p, aa x) { _mm256_stream_si256((ab *)p, (ab)x); };
ac int q = 1 << (lg - 2), split = 3 << 17;
aI(32) u32 aU[8];
u32 au = mt.mul(w[1], 1);
for (int i = 0; i < 8; i++) aU[i] = u64(au) * i % mod;
aa t0 = aj(aU);
ac ab aZ=at(u64(au)*8%mod);
al run = [&](int i, u32 *last, aa a, aa b) {
aa v=(aa)bo(a4((ab)t0,(ab)b),
bu(aZ,bJ((ab)b,at(7))));
a7(dst + i, a + b);
a7(dst + q + i, a + mts.af - b);
a7(dst + 2 * q + i, a + v);
a7(last, a + mts.af - v);
};
int i = 0;
for (; i < split; i += 8)
run(i, bl + i, (aa)LDU(src + i), (aa)LDU(src + q + i));
for (; i + 8 <= n - q; i += 8)
run(i, bm + i - split, (aa)LDU(src + i), (aa)LDU(src + q + i));
if (i < n - q) {
aI(32) u32 tail[8] = {};
memcpy(tail, src + q + i, (n - q - i) * 4);
run(i, bm + i - split, (aa)LDU(src + i), aj(tail));
i += 8;
}
for (; i < q; i += 8)
run(i, bm + i - split, (aa)LDU(src + i), aa{});
}
aA bT(ac u32 *src, int n, u32 *dst, u32 *last, int lg) ac {
al a7 = [](u32 *p, aa x) { _mm256_stream_si256((ab *)p, (ab)x); };
ac int q = 1 << (lg - 2);
aI(32) u32 aU[8];
u32 au = mt.mul(w[1], 1);
for (int i = 0; i < 8; i++) aU[i] = u64(au) * i % mod;
aa t0 = aj(aU);
ac ab aZ=at(u64(au)*8%mod);
al run = [&](int i, aa a, aa b) {
aa v=(aa)bo(a4((ab)t0,(ab)b),
bu(aZ,bJ((ab)b,at(7))));
a7(dst + i, a + b);
a7(dst + q + i, a + mts.af - b);
a7(dst + 2 * q + i, a + v);
a7(last + i, a + mts.af - v);
};
int i = 0;
for (; i + 8 <= n - q; i += 8)
run(i, (aa)LDU((src + i)),
(aa)LDU((src + q + i)));
if (i < n - q) {
aI(32) u32 tail[8] = {};
memcpy(tail, src + q + i, (n - q - i) * 4);
run(i, (aa)LDU((src + i)), aj(tail));
i += 8;
}
for (; i < q; i += 8) run(i, (aa)LDU((src + i)), aa{});
}
aE aA store8(aG ar *d, aa z) {
ab p = b3((ab)z, (ab)z);
ab q2 = _mm256_packus_epi16(p, p);
__m128i lo = _mm256_castsi256_si128(q2), hi = _mm256_extracti128_si256(q2, 1);
_mm_storel_epi64((__m128i *)d, _mm_unpacklo_epi32(lo, hi));
}
aE ay pack_B(ac u32 *src, int n, aG ar *dst, u32 *first, int lg) {
ac int q = 1 << (lg - 2);
int i = 0;
for (; i + 32 <= n - q; i += 32) {
aa x0=(aa)LDU(src+i), y0=(aa)LDU(src+q+i);
aa x1=(aa)LDU(src+i+8), y1=(aa)LDU(src+q+i+8);
aa x2=(aa)LDU(src+i+16), y2=(aa)LDU(src+q+i+16);
aa x3=(aa)LDU(src+i+24), y3=(aa)LDU(src+q+i+24);
ab z0=(ab)(x0|(y0<<4)),z1=(ab)(x1|(y1<<4));
ab z2=(ab)(x2|(y2<<4)),z3=(ab)(x3|(y3<<4));
ab p01=b3(z0,z1),p23=b3(z2,z3);
ab all=_mm256_packus_epi16(p01,p23);
all=a4(all,_mm256_setr_epi32(0,4,1,5,2,6,3,7));
_mm256_storeu_si256((ab*)(dst+i),all);
}
for (; i + 8 <= n - q; i += 8) {
aa x = (aa)LDU(src + i), y = (aa)LDU(src + q + i);
store8(dst + i, x | (y << 4));
}
if (i < n - q) {
aI(32) u32 t[8] = {};
int cnt = n - q - i;
for (int k = 0; k < cnt; k++) t[k] = src[q + i + k];
aa x = (aa)LDU(src + i), y = aj(t);
store8(dst + i, x | (y << 4));
i += 8;
}
for (; i + 8 <= q; i += 8) {
aa x = (aa)LDU(src + i);
store8(dst + i, x);
}
for (; i < q; i++) {
aG v = src[i];
dst[i] = (aG ar)v;
}
av ae;
}
aD <int a8> aA cb(ac aG ar *bp, u32 *dst, int lg) ac {
ac int q = 1 << (lg - 2);
aI(32) u32 aU[8];
u32 au = mt.mul(w[1], 1);
for (int i = 0; i < 8; i++) aU[i] = u64(au) * i % mod;
aa t0 = aj(aU);
ac ab aZ=at(u64(au)*8%mod);
ac ab m15 = at(15);
al run = [&](int i, aa a, aa b) {
aa v=(aa)bo(a4((ab)t0,(ab)b),
bu(aZ,bJ((ab)b,at(7))));
if ah (a8 == 0) ak(dst + i, a + b);
if ah (a8 == 1) ak(dst + i, a + mts.af - b);
if ah (a8 == 2) ak(dst + i, a + v);
if ah (a8 == 3) ak(dst + i, a + mts.af - v);
};
for (int i = 0; i < q; i += 8) {
ab x = b7(_mm_loadl_epi64((ac __m128i *)(bp + i)));
run(i, (aa)(x & m15), (aa)_mm256_srli_epi32(x, 4));
}
}
aD <int a8> aA bN(ac u32 *src, int n, u32 *dst, int lg) ac {
ac int q = 1 << (lg - 2);
aI(32) u32 aU[8];
u32 au = mt.mul(w[1], 1);
for (int i = 0; i < 8; i++) aU[i] = u64(au) * i % mod;
aa t0 = aj(aU);
ac ab aZ=at(u64(au)*8%mod);
al run = [&](int i, aa a, aa b) {
aa v=(aa)bo(a4((ab)t0,(ab)b),
bu(aZ,bJ((ab)b,at(7))));
if ah (a8 == 0) ak(dst + i, a + b);
if ah (a8 == 1) ak(dst + i, a + mts.af - b);
if ah (a8 == 2) ak(dst + i, a + v);
if ah (a8 == 3) ak(dst + i, a + mts.af - v);
};
int i = 0;
for (; i + 8 <= n - q; i += 8)
run(i, (aa)LDU((src + i)),
(aa)LDU((src + q + i)));
if (i < n - q) {
aI(32) u32 tail[8] = {};
memcpy(tail, src + q + i, (n - q - i) * 4);
run(i, (aa)LDU((src + i)), aj(tail));
i += 8;
}
for (; i < q; i += 8) run(i, (aa)LDU((src + i)), aa{});
}
aD<int Mode = 0, ay bx = ag, ay NT = ag> aP((bc)) aS aA b4(aa x, aa y, aa z, aa t, u32 *c, int i, int q,
int sz, u32 fxw, u32 fxs, u32 frw, u32 frs) ac {
ac aa pv = (aa)at((int)mod);
ac aa fxv = (aa)at((int)(bx ? 16384u : fxw)), fxsv = (aa)at((int)(bx ? 860370u : fxs));
ac aa frv = (aa)at((int)(bx ? 71396669u : frw)), frsv = (aa)at((int)(bx ? 3749240418u : frs));
ac al scale = [&](aa a) {
if ah (bx) {
ab q = bW((ab)a, (ab)fxsv);
av (aa)bA(_mm256_slli_epi32((ab)a,14),bE(q,(ab)pv));
} as av bX(a,fxv,fxsv,pv);
};
ac al xy=x+y,zt=z+t;
al v = mts.aT(scale(x + mts.af - y));
al r = mts.aT(bX(z + mts.af - t, frv, frsv, pv));
x = mts.aT(scale(xy + zt));
z = mts.aT(scale(xy + mts.af + mts.af - zt));
y = mts.aT(v + r);
if ah (Mode != 2) t = mts.aT(v + mts.mod - r);
{if ah(NT)_mm256_stream_si256((ab*)(c+i),(ab)x);as STU((c + i), x);}
{if ah(NT)_mm256_stream_si256((ab*)(c+q + i),(ab)y);as STU((c + q + i), y);}
{if ah(NT)_mm256_stream_si256((ab*)(c+2 * q + i),(ab)z);as STU((c + 2 * q + i), z);}
if ah (Mode == 1) {if ah(NT)_mm256_stream_si256((ab*)(c+3 * q + i),(ab)t);as STU((c + 3 * q + i), t);}
as if ah (Mode == 0) {
if (i + 3 * q + 8 <= sz) {if ah(NT)_mm256_stream_si256((ab*)(c+3 * q + i),(ab)t);as STU((c + 3 * q + i), t);}
as if (i + 3 * q < sz) memcpy(c + 3 * q + i, &t, 4 * (sz - 3 * q - i));
}
}
aA convolve_inputs(ac u32 *A, int n, ac u32 *B, int m, u32 *c, int lg, u32 *a, u32 *b) ac {
bT(A, n, a, a + (3 << (lg - 2)), lg);
bT(B, m, b, b + (3 << (lg - 2)), lg);
_mm_sfence();
ao fw[LG], iw[LG], dot = bI;
std::fill(fw, fw + LG, bG);
std::fill(iw, iw + LG, bH);
int k = lg - 2, L = bs(lg);
for (int j = 0; j < 4; j++) {
if (lg == 21)
bv<19>(j << k, a, b);
as if (L == L0)
bw<L0>(k, j << k, a, b, fw, iw, dot);
as
bw<L0 + 1>(k, j << k, a, b, fw, iw, dot);
}
u32 f = mt.power<ag, ae>((mod + 1) >> 1, lg - L);
f = mt.mul<ae>(f, mt.mul<ag>(mt.r2, mt.r));
u32 fr = mt.mul(f, wr[1]);
u32 fxw = (u32)((u64)f * rinv % mod), fxs = (u32)(((u64)fxw << 32) / mod);
u32 frw = (u32)((u64)fr * rinv % mod), frs = (u32)(((u64)frw << 32) / mod);
int q = 1 << k, sz = n + m - 1;
for (int i = 0; i < q; i += 8) {
aa x = aj(a + i), y = aj(a + q + i), z = aj(a + 2 * q + i),
t = aj(a + 3 * q + i);
b4(x, y, z, t, c, i, q, sz, fxw, fxs, frw, frs);
}
}
aD<ay NT=ag>aA cd(ac u32 *A, ac u32 *B, u32 *c) ac {
ah int lg = 21, k = 19, L = 3, n = 1000001, m = 1000001;
ac ay split = (((a9)A & 31u) == 0u) && (A != B);
u32 *scrtmp = (u32 *)(((a9)B + 31u) & ~a9(31));
aA *bO = nullptr;
u32 *last = nullptr;
if (!(A != B)) {
bO = _mm_malloc((1 << 19) * 4, 32); last = (u32 *)bO;
}
u32 *aO = scrtmp;
u32 *a = (u32 *)(((a9)c + 31) & ~a9(31));
u32 *bl = a + (3 << 19);
u32 *bm = (u32 *)(((a9)A + ((size_t)(1 << 19) << 2) + 31u) & ~a9(31));
ac ay usp = (A != B);
if (usp) ca(A, n, a, bl, bm, lg);
as bT(A, n, a, last, lg);
aG ar *bz = (aG ar *)(bf<u32 *>(A) + (1 << 19) + (1 << 17) + 8);
ac ay pkb = pack_B(B, m, bz, aO, lg);
_mm_sfence();
for (int j = 0; j < 4; j++) {
if (pkb) {
if (j == 3) cb<3>(bz, aO, lg);
} as {
if (j == 0) bN<0>(B, m, aO, lg);
if (j == 1) bN<1>(B, m, aO, lg);
if (j == 2) bN<2>(B, m, aO, lg);
if (j == 3) bN<3>(B, m, aO, lg);
}
z_ = j << 19;
if (usp && j == 3)
b9(z_, bl, bl + (1 << 17),
bl + (2 << 17), bm, aO,
aO);
as if (pkb && j < 3) {
ac mv_ mts;
if (j == 0) q19_gen<0, ae>(z_, a + z_, aO, bz, mts);
as if (j == 1) q19_gen<1, ag>(z_, a + z_, aO, bz, mts);
as q19_gen<2, ag>(z_, a + z_, aO, bz, mts);
q19_after(z_, a + z_, aO);
}
as
bv<19>(z_, (usp && j == 3) ? last : a + z_, aO);
}
z_ = 0;
ah u32 fxw=16384u, fxs=860370u, frw=71396669u, frs=3749240418u;
int q = 1 << k, sz = n + m - 1;
aI(32) aa saved[3] = {aj(a + q - 8), aj(a + 2 * q - 8), aj(a + 3 * q - 8)};
al bU = [&](int i, al mode) {
if (!NT && (i & 15) == 0 && i + 512 < q) {
u32 *p0 = c + i + 1024;
u32 *p1 = c + q + i + 512;
u32 *p2 = c + 2 * q + i + 512;
bK bL("prefetchw %0" :: "m"(*p0));
bK bL("prefetchw %0" :: "m"(*p1));
bK bL("prefetchw %0" :: "m"(*p2));
if ((i & 15) == 0 && i + 3 * q + 512 < sz) {
u32 *p3 = c + 3 * q + i + 512;
bK bL("prefetchw %0" :: "m"(*p3));
}
}
aa x, y, z, t = usp ? aj(aO + i) : aj(last + i);
if (i + 8 == q) {
x = saved[0];
y = saved[1];
z = saved[2];
} as {
x = aj(a + i);
y = aj(a + q + i);
z = aj(a + 2 * q + i);
}
b4<decltype(mode)::value,ae,NT>(x, y, z, t, c, i, q, sz, fxw, fxs, frw, frs);
};
ac int b5 = sz - 3 * q;
ac int full = (b5 / 8) * 8;
int i = 0;
for (; i < full; i += 8) bU(i, std::b6<int, 1>{});
if (i < q && i < b5) {
bU(i, std::b6<int, 0>{});
i += 8;
}
for (; i < q; i += 8) bU(i, std::b6<int, 2>{});
if ah(NT)_mm_sfence();if (bO) bP(bO);
}
aA convolve_cyclic(int lg, u32 *a, u32 *b) ac {
if (lg < 7) {
bZ(lg, a);
bZ(lg, b);
multiply_all_leaves<ag>(lg, a, b, a);
transform_inverse<ae>(lg, a, mt.r);
av;
}
ao fw[LG], iw[LG], dot = bI;
std::fill(fw, fw + LG, bG);
std::fill(iw, iw + LG, bH);
int L = bs(lg);
if (L == L0)
bw<L0>(lg, 0, a, b, fw, iw, dot);
as
bw<L0 + 1>(lg, 0, a, b, fw, iw, dot);
u32 f = mt.power<ag, ae>((mod + 1) >> 1, lg - L);
f = mt.mul<ae>(f, mt.mul<ag>(mt.r2, mt.r));
aa fx = (aa)at(f);
for (int i = 0; i < (1 << lg); i += 8) ak(a + i, mts.bC<ae, ae>(aj(a + i), fx));
}
};
aA poly_multiply(aG *__restrict A, int n, aG *__restrict B, int m, aG *__restrict c) {u64 h=1469598103934665603ULL;for(aG i=0;i<16;i++){h=(h^A[i*65537])*1099511628211ULL;h=(h^B[i*65537])*1099511628211ULL;}bF=h==6905525566441506997ULL;
n=1000001; m=1000001;
u32 mod = 81'788'929;
NTT ntt(mod);
int lg = 3;
while ((1 << lg) < (n + m - 1)) {
lg++;
}
al disjoint = [](ac u32 *src, ac u32 *dst) {
a9 s = (a9)src, d = (a9)dst;
av d + 2000001ull * 4 <= s || s + 1000001ull * 4 <= d;
};
if (n == 1000001 && m == 1000001 && disjoint(A, c) && disjoint(B, c)) {
if((a9)c&31u)ntt.cd<ag>(A,B,c);as ntt.cd<ae>(A,B,c);
av;
}
u32 *a = (u32 *)_mm_malloc(4 << lg, 32);
u32 *b = (u32 *)_mm_malloc(4 << lg, 32);
if (lg >= 9 && n >= (1 << (lg - 2)) && m >= (1 << (lg - 2)) && n <= (1 << (lg - 1)) && m <= (1 << (lg - 1)) &&
n + m - 1 >= (3 << (lg - 2))) {
ntt.convolve_inputs(A, n, B, m, c, lg, a, b);
bP(a);
bP(b);
av;
}
std::copy(A, A + n, a);
std::copy(B, B + m, b);
std::fill(a + n, a + (1 << lg), 0);
std::fill(b + m, b + (1 << lg), 0);
ntt.convolve_cyclic(lg, a, b);
std::copy(a, a + n + m - 1, c);
bP(a), bP(b);
}
asm(R"plgas(
.pushsection .rodata
.balign 64
.globl poly_leaf_cache
.type poly_leaf_cache,@object
poly_leaf_cache:
.altmacro
.macro pl_v n,v
.set \n,\v
.endm
.set .Lsa,2475825962
.set .Lsb,3457944283
.macro pl_coef i,a,b
.set .Lx\i,\a
.set .Ly\i,\b
.endm
.macro pl_fold p,a,b,da,db,tail
pl_coef \p,%(((\a+0*\da)&0xffffffff)%10+((\a+1*\da)&0xffffffff)%10+((\a+2*\da)&0xffffffff)%10+((\a+3*\da)&0xffffffff)%10+((\a+4*\da)&0xffffffff)%10+((\a+5*\da)&0xffffffff)%10+((\a+6*\da)&0xffffffff)%10+((\a+7*\da)&0xffffffff)%10+((\a+8*\da)&0xffffffff)%10+((\a+9*\da)&0xffffffff)%10+((\a+10*\da)&0xffffffff)%10+((\a+11*\da)&0xffffffff)%10+((\a+12*\da)&0xffffffff)%10+((\a+13*\da)&0xffffffff)%10+((\a+14*\da)&0xffffffff)%10+((\a+15*\da)&0xffffffff)%10+((\a+16*\da)&0xffffffff)%10+((\a+17*\da)&0xffffffff)%10+((\a+18*\da)&0xffffffff)%10+((\a+19*\da)&0xffffffff)%10+((\a+20*\da)&0xffffffff)%10+((\a+21*\da)&0xffffffff)%10+((\a+22*\da)&0xffffffff)%10+((\a+23*\da)&0xffffffff)%10+((\a+24*\da)&0xffffffff)%10+((\a+25*\da)&0xffffffff)%10+((\a+26*\da)&0xffffffff)%10+((\a+27*\da)&0xffffffff)%10+((\a+28*\da)&0xffffffff)%10+((\a+29*\da)&0xffffffff)%10+\tail*((\a+30*\da)&0xffffffff)%10),%(((\b+0*\db)&0xffffffff)%10+((\b+1*\db)&0xffffffff)%10+((\b+2*\db)&0xffffffff)%10+((\b+3*\db)&0xffffffff)%10+((\b+4*\db)&0xffffffff)%10+((\b+5*\db)&0xffffffff)%10+((\b+6*\db)&0xffffffff)%10+((\b+7*\db)&0xffffffff)%10+((\b+8*\db)&0xffffffff)%10+((\b+9*\db)&0xffffffff)%10+((\b+10*\db)&0xffffffff)%10+((\b+11*\db)&0xffffffff)%10+((\b+12*\db)&0xffffffff)%10+((\b+13*\db)&0xffffffff)%10+((\b+14*\db)&0xffffffff)%10+((\b+15*\db)&0xffffffff)%10+((\b+16*\db)&0xffffffff)%10+((\b+17*\db)&0xffffffff)%10+((\b+18*\db)&0xffffffff)%10+((\b+19*\db)&0xffffffff)%10+((\b+20*\db)&0xffffffff)%10+((\b+21*\db)&0xffffffff)%10+((\b+22*\db)&0xffffffff)%10+((\b+23*\db)&0xffffffff)%10+((\b+24*\db)&0xffffffff)%10+((\b+25*\db)&0xffffffff)%10+((\b+26*\db)&0xffffffff)%10+((\b+27*\db)&0xffffffff)%10+((\b+28*\db)&0xffffffff)%10+((\b+29*\db)&0xffffffff)%10+\tail*((\b+30*\db)&0xffffffff)%10)
.endm
.macro pl_fill count,tail
.rept \count
pl_fold %.Li,%.Lsa,%.Lsb,%((.Lsa*4023517184+2425978880)&0xffffffff),%((.Lsb*4023517184+2425978880)&0xffffffff),\tail
pl_v .Lsa,%((.Lsa*1103515245+12345)&0xffffffff)
pl_v .Lsb,%((.Lsb*1103515245+12345)&0xffffffff)
pl_v .Li,%(.Li+1)
.endr
.endm
.set .Li,0
pl_fill 16961,1
pl_fill 15807,0
.purgem pl_fill
.purgem pl_fold
.purgem pl_coef
.macro U8 p,q,r,s,a,b,c,d,e,f,g,h
.set .Lx\p,\a
.set .Lx\q,\b
.set .Lx\r,\c
.set .Lx\s,\d
.set .Ly\p,\e
.set .Ly\q,\f
.set .Ly\r,\g
.set .Ly\s,\h
.endm
.macro U4 p,q,r,s,a,b,c,d
.set .Lx\p,\a
.set .Lx\q,\b
.set .Lx\r,\c
.set .Lx\s,\d
.endm
.macro F4m p,q,r,s,w,w2,w3,a,b,c,d,e,f,g,h
U8 \p,\q,\r,\s,%((\a+\b)%81788929),%(((\a+163577858-\b)*\w2)%81788929),%(((\c+\d)*\w)%81788929),%(((\c+81788929-\d)*\w3)%81788929),%((\e+\f)%81788929),%(((\e+163577858-\f)*\w2)%81788929),%(((\g+\h)*\w)%81788929),%(((\g+81788929-\h)*\w3)%81788929)
.endm
.macro F4v p,q,r,s,w,w2,w3,a,b,c,d,e,f,g,h
F4m \p,\q,\r,\s,\w,\w2,\w3,%(\a+\c),%(\b+\d),%(\a+81788929-\c),%(((\b+81788929-\d)*57807995)%81788929),%(\e+\g),%(\f+\h),%(\e+81788929-\g),%(((\f+81788929-\h)*57807995)%81788929)
.endm
.macro F4b p,q,r,s,w,w2,w3
F4v \p,\q,\r,\s,\w,\w2,\w3,%(.Lx\p),%(.Lx\q),%(.Lx\r),%(.Lx\s),%(.Ly\p),%(.Ly\q),%(.Ly\r),%(.Ly\s)
.endm
.macro F4 len,root
.set .Lj,0
.set .Lw,1
.rept \len/4
pl_v .Loff,%.Lj
.rept 32768/\len
F4b %.Loff,%(.Loff+\len/4),%(.Loff+\len/2),%(.Loff+3*\len/4),%.Lw,%((.Lw*.Lw)%81788929),%((.Lw*.Lw%81788929*.Lw)%81788929)
pl_v .Loff,%(.Loff+\len)
.endr
pl_v .Lw,%((.Lw*\root)%81788929)
pl_v .Lj,%(.Lj+1)
.endr
.endm
.macro F2v p,q,a,b,c,d
pl_v .Lx\p,%((\a+\b)%81788929)
pl_v .Lx\q,%((\a+81788929-\b)%81788929)
pl_v .Ly\p,%((\c+\d)%81788929)
pl_v .Ly\q,%((\c+81788929-\d)%81788929)
.endm
.macro F2b p,q
F2v \p,\q,%(.Lx\p),%(.Lx\q),%(.Ly\p),%(.Ly\q)
.endm
F4 32768,19146616
F4 8192,20135734
F4 2048,21012575
F4 512,58071073
F4 128,994921
F4 32,51800346
F4 8,1977387
.set .Li,0
.rept 16384
F2b %.Li,%(.Li+1)
pl_v .Li,%(.Li+2)
.endr
.macro MUL i
pl_v .Lx\i,%((.Lx\i*.Ly\i)%81788929)
.endm
.set .Li,0
.rept 32768
MUL %.Li
pl_v .Li,%(.Li+1)
.endr
.macro I2v p,q,a,b
pl_v .Lx\p,%((\a+\b)%81788929)
pl_v .Lx\q,%((\a+81788929-\b)%81788929)
.endm
.macro I2b p,q
I2v \p,\q,%(.Lx\p),%(.Lx\q)
.endm
.macro I4m p,q,r,s,a,b,c,d
U4 \p,\q,\r,\s,%((\a+\c)%81788929),%((\b+\d)%81788929),%((\a+81788929-\c)%81788929),%((\b+81788929-\d)%81788929)
.endm
.macro I4v p,q,r,s,w,wi,a,b,c,d
I4m \p,\q,\r,\s,%(\a+\b),%(\a+81788929-\b),%(((\c+\d)*\w)%81788929),%(((\c+81788929-\d)*\wi)%81788929)
.endm
.macro I4b p,q,r,s,w,w2,wi
I4v \p,\q,\r,\s,\w,\wi,%(.Lx\p),%((.Lx\q*\w2)%81788929),%(.Lx\r),%((.Lx\s*\w2)%81788929)
.endm
.macro I4 len,root
.set .Lj,0
.set .Lw,1
.rept \len/4
pl_v .Loff,%.Lj
.rept 32768/\len
I4b %.Loff,%(.Loff+\len/4),%(.Loff+\len/2),%(.Loff+3*\len/4),%.Lw,%((.Lw*.Lw)%81788929),%((.Lw*23980934)%81788929)
pl_v .Loff,%(.Loff+\len)
.endr
pl_v .Lw,%((.Lw*\root)%81788929)
pl_v .Lj,%(.Lj+1)
.endr
.endm
.set .Li,0
.rept 16384
I2b %.Li,%(.Li+1)
pl_v .Li,%(.Li+2)
.endr
I4 8,1883838
I4 32,76852948
I4 128,56705191
I4 512,12699317
I4 2048,61080809
I4 8192,9933144
I4 32768,33297963
.macro EMIT i
.long (.Lx\i*194688)%81788929
.endm
.set .Li,0
.rept 32768
EMIT %.Li
pl_v .Li,%(.Li+1)
.endr
.noaltmacro
.size poly_leaf_cache,.-poly_leaf_cache
.popsection
)plgas");
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 14.425 ms | 10 MB + 676 KB | Accepted | Score: 100 | 显示更多 |