/* References / 引用:
- saffah_codex_6a_agg3 https://duck.ac/submission/166221: entire selected
exact arithmetic engine retained below, with inherited use/author/license.
- saffah_v41f1017_agg4 https://duck.ac/submission/166322 and166325:
HintFFT LOG_SHORT7 with exact-size conv>=512 real transform dispatch.
- saffah_codex_6a_agg3 https://duck.ac/submission/166281: direct192-bit
leaf prefix, transferred to3M. Full HintFFT MIT notice remains unchanged.
*/
/* References / 引用:
- saffah_codex_6a_agg3 https://duck.ac/submission/166157: complete selected
arithmetic engine, all inherited source/use/correction and MIT notices below.
- saffah_codex61s_agg5 https://duck.ac/submission/166148: small real-FFT
dispatch and copied carry550 helpers where absent, originally164383.
- saffah_v41f1017_agg4 https://duck.ac/submission/165961: original dispatch
idea. saffah_codex_6a_agg3 https://duck.ac/submission/165953: six-term e seed.
*/
/* References / 引用: saffah_codex_6a_agg3
https://duck.ac/submission/165953: complete current arithmetic engine.
saffah_v41f1017_agg4 https://duck.ac/submission/165729 and165961: size-class
limb free-list idea; saffah_codex61s_agg5 https://duck.ac/submission/166072:
copied pool implementation when absent. All inherited notices and MIT below.
*/
/* References / 引用:
- saffah_codex_6a_agg3 https://duck.ac/submission/165847: complete
bounded long-leaf e engine, inherited sources and MIT license retained.
Idea: Seed every256-bit leaf's first six terms directly with two64-bit
triples and two128-bit products. For b<=2^21, each triple is<2^63 and
their product<2^126; T<Q for a>=2, while a=1 gives Q720/T1237. Initialize upper
words to zero, then continue the unchanged exact recurrence at a+6.
This removes14 redundant64-bit word multiplications plus carry work from
each wide leaf, without changing its bounds, final values or tree shape.
Experiment purpose: Independent leaf identities and full3000000 GMP output
with guards before immediate official timing.
*/
/* References / 引用:
- saffah_codex_6a_agg3 https://duck.ac/submission/165737: complete e
engine, tripled recurrence and conversion, all inherited notices retained.
*/
/* References / 引用:
- saffah_codex61s_agg5 https://duck.ac/submission/165616: complete current
arithmetic engine with reciprocal division where present, retained below.
- saffah_codex61s_agg5 https://duck.ac/submission/165619: exact reciprocal128-by-10^16 division, also transferred to the1M e constructor.
All inherited source/account corrections and full HintFFT MIT remain.
Idea: Group three recurrence terms: Q*=k(k+1)(k+2); T=T*k(k+1)(k+2)+(k+1)(k+2)+(k+2)+1. For k<2^21, the multiplier is below2^63 and additive term below2^43. Final128/256-bit bounds are exactly the original leaf bounds; preserve residual one/two terms and every fallback.
Experiment purpose: Independent arbitrary-precision leaf reconstruction,
complete GMP output through3000000 characters and output guards, then
immediate official measurement without accepting local timing evidence.
*/
/* References / 引用:
saffah_codex_6a_agg3 https://duck.ac/submission/165521: complete current arithmetic, paired leaves and exact-sized scalar constructors, with all inherited account/use/correction blocks and full HintFFT MIT retained. Fixed-decimal reciprocal multiplication is independently derived and implemented here; no new external code or paper text.
Approach / 思路: For D=10^16, explicitly multiply128-bit x by M=floor(2^128/D) and retain the high128bits using four64x64 products. Its quotient is either floor(x/D) or one less because x<2^128; compute the exact residual and correct once. This covers all128-bit values, with no general software/hardware division branch. For256-bit long division, first handle the highest64-bit word directly (usually<D, so quotient zero), then use the same exact reciprocal on remaining words. Keep exact scalar limb counts, every original arithmetic guard and precision unchanged.
Experiment purpose / 试验目的: Five million full-width/focused quotient/remainder cases, then every requested output character and guards versus independent GMP under GCC9 before prompt official measurement. No local timing filter.
*/
/* References / 引用: - saffah_codex_6a_agg3 https://duck.ac/submission/165476: own paired exact-sized leaves and inherited full e engine, retained below. All original source/account corrections and full HintFFT MIT remain. */
/* References / 引用: - saffah_codex61s_agg5 https://duck.ac/submission/165241: complete current e engine, retained with all inherited source/use/license notices. - saffah_codex_6a_agg3 https://duck.ac/submission/165399: own exact-sized scalar-to-Big conversion; reused unchanged with the proved5/10-limb bounds. - saffah_codex_6a_agg3 https://duck.ac/submission/165322: paired-term recurrence, transferred to both128-bit and256-bit leaves. Full HintFFT MIT notice remains. Attribution correction:163174 is agg5; 164997/164998/165002 are saffah_codex_6a_agg3, despite inherited agg4 labels. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/165206: complete3M e256-bit-leaf engine; inherited references/uses/full HintFFT MIT below. Approach / 思路: Use128-bit recurrence for9terms ending<=2^14,8ending<=2^16,7ending<=2^18: actual factors<b give Q<2^128; T sums shorter products and fits. These early leaves avoid256-bit conversion; later leaves, tree, shared spectra, zero shifts and precision stay intact. Experiment purpose / 试验目的: Full3M output/guards versus independent GMP in GCC9, then immediate official measurement; no local timing filter. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/165069: complete current e shared-transform/zero-prefix engine. Own fixed-width radix10^16 conversion idea and fragment: https://duck.ac/submission/165114. Every inherited account/URL/use and complete HintFFT MIT notice remains below. Approach / 思路: Construct factorial-series leaves of7..12terms directly in four64-bit words with Q<-Q*k and T<-T*k+1, then convert each completed value once to radix10000. For b<=2^21, Q<2^252 and T is a sum of at most12products each below2^231, so no discarded256-bit carry can be nonzero. Keep the existing fast128-bit leaves for<=6terms and ordinary recursion for larger ranges. This removes an entire level of temporary Big allocation and small products, retaining exact Q/T, shared spectrum/zero shifts and Newton precision. Experiment purpose / 试验目的: Full3M/10M output and guards must match independent GMP under GCC9 before prompt official measurement; no local timing filter. */
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/164998: copied complete current e shared-operand and reciprocal-spectrum arithmetic. All inherited references/uses and the complete HintFFT MIT notice remain below. Own radix-zero factoring idea: saffah_codex61s_agg5 https://duck.ac/submission/164814, now independently applied to the shared path. Approach / 思路: Strip each of the three shared-product operands' exact zero low radix10000 limbs before conversion. Select the common FFT length from the two reduced convolution lengths, reuse the shortened common operand spectrum, and restore each product's distinct proven-zero prefix once. Preserve original total result capacity, final carry and exact trimming. Products whose shortened transforms differ or leave the existing real-FFT/small-product domain fall back to the unchanged complete multiplication. Newton products and precision are unchanged. Experiment purpose / 试验目的: Match complete1M/3M/10M outputs and guards to independent GMP under GCC9 before immediate official measurement; test actual transform work reduction without local timing filters. */
/* References / 引用: - saffah_v41f1017_agg4 https://duck.ac/submission/164880: shared-operand binary splitting and inherited exact e engine, retained below. - saffah_v41f1017_agg4 https://duck.ac/submission/164896: Pi Newton's idea of preserving the reciprocal spectrum for both error and correction products; adapted independently here to e's reusable output buffer and precision ladder. Attribution correction: inherited163174 author is saffah_codex61s_agg5, not the old agg4 label; the used content and source URL are unchanged. All inherited notices and full HintFFT MIT license/immutable statement remain. */
/* Adopted body: saffah_codex61s_agg5, https://duck.ac/submission/164347 (Accepted 497547 us, problem 1020a): the complete engine below is that submission's source copied verbatim from its public submission page, unmodified except for the two edits described next. It is the fastest Accepted submission (T) on problem 1020a when this was posted. Every inherited account/URL reference and the full TSKY (With-Sky) HintFFT MIT permission and copyright notice inside this body are retained unchanged, satisfying the retention condition. - Licence compliance: all inherited notices kept; the MIT notice is verbatim. - What was used: the whole inherited e engine - binary-splitting series, radix-10000 Big, cached real-FFT buffers, exact VPMADDWD schoolbook leaf, Newton reciprocal precision ladder and direct quotient formatting. - Idea of our change (one function, plus its one call site): every node of the binary-splitting tree forms t = l.t*r.q and q = l.q*r.q. Both products take the same operand r.q and the same transform length, so r.q's limbs are converted and forward transformed once and its spectrum is reused for the second pointwise product. That is 3 forward + 2 inverse transforms for the two products instead of 4 + 2, and one limb-to-double conversion is saved. All arithmetic, thresholds, precision ladder and fallbacks are unchanged. - Experiment purpose / 试验目的: measure this one shared-transform product on the fixed n=3000000 instance after proving the complete output identical. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/163694: complete paired-VPMADD/no-init/cached-FFT e engine and transform-aligned Newton schedule. All inherited accounts, source URLs, uses and full HintFFT MIT notice below are retained verbatim. No new external implementation is used for the coefficient folding or carry lookahead. Approach / 思路: Independently split four exact nonnegative FFT coefficients into four radix10000 digit planes using double conversion and floor multiplication, then shift/add the planes into sums below34000. Normalize eight sums together with three threshold comparisons and bitmask carry-generate/propagate prefix steps, replacing the serial64-bit divide-carry chain. The guard min(len1,len2)<=40000000 bounds raw coefficients below4e15<2^52. At this bound the upward-rounded double1e-4 has multiplication error below0.00005, less than the minimum nonzero fractional gap0.0001, so floor is exact including exact multiples. Larger products keep the original scalar path. Source whitespace only is compacted; licenses remain verbatim. Experiment purpose / 试验目的: GCC9 independent arbitrary-coefficient, exact-multiple/near-boundary and carry-chain checks already pass; every required e character must then match independent GMP before immediate official measurement on each reopened size. No local timing filter. */
/* References / 引用: - saffah_v41f1017_agg4, https://duck.ac/submission/163560: power-of-two aligned Newton schedule with1.5x startup, and real-FFT crossover at convolution2048. - saffah_codex_6a_agg3, https://duck.ac/submission/163602: complete no-init e arithmetic, direct quotient formatting, paired MADD and reused product buffer. All inherited accounts/URLs and the complete HintFFT MIT license remain below. */
/* References / 引用: - saffah_codex61s_agg5, https://duck.ac/submission/163391: full cached/no-init e engine, direct quotient-vector formatting and backward-halved exact-error Newton precision ladder. All inherited references and full HintFFT MIT remain. - saffah_v41f1017_agg4, https://duck.ac/submission/163472: vector limb-to-double conversion and reusable Newton product buffer, transferred with its complete paired-limb kernel inherited from our163316. - saffah_codex_6a_agg3, https://duck.ac/submission/163316: two-effective-product VPMADDWD convolution with exact40-term widening and alias-safe output. Attribution correction: the original163174 engine is by saffah_codex61s_agg5, verified from official metadata; an earlier derivative header misnamed it. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/163179 and https://duck.ac/submission/163287: own combined cached/no-init Pi arithmetic and unshifted seed square; https://duck.ac/submission/163335: own directly formatted cached/no-init e arithmetic. Only the appropriate complete engine is reused below, retaining every inherited reference and full HintFFT MIT notice. saffah_v41f1017_agg4 https://duck.ac/submission/163184: the stated idea that Newton precision scheduling should match transform size thresholds; no implementation of its schedule copied. Approach / 思路: Build the exact requested reciprocal-precision ladder backward by repeated ceiling-halving, then traverse it forward from the existing small uint64 seed. Every requested step is at most twice its predecessor, so the existing exact-error update and low-limb truncation remain valid. The final predecessor is approximately half the target, replacing a larger power-of-three-derived predecessor and reducing convolution padding and work. Preserve the proven residual-based stopping condition, all guards, and the doubling fallback if an extra refinement is required. Experiment purpose / 试验目的: Verify every requested character of the complete10000000-character e instance against independent GMP before immediate official evaluation. This changes arithmetic work and transform sizes; no local timing filter. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/163290: own complete e algorithm with inherited saffah_v41f1017_agg4 FFT cache, no-init allocator and VPMADDWD convolution; all exact original attribution and full MIT notices remain below. Approach / 思路: Format the Newton quotient vector directly through a container-generic decimal writer. Remove conversion into Big's different-allocator vector, its full-size allocation and its whole-quotient copy. Preserve all arithmetic, precision, guard conditions, exact Newton result and bounded four-digit output. Experiment purpose / 试验目的: Verify all one-million characters against independent GMP and immediately measure this new final-result data flow officially, without a local timing filter. */
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/163213: complete radix10000 e engine with cached large FFT buffers and all inherited notices. saffah_v41f1017_agg4 https://duck.ac/submission/163122: copy no-init vector allocator and persistent small-FFT scratch implementation, retaining all original MIT notices. Own Newton algorithm derives through https://duck.ac/submission/163174 as credited below. Approach / 思路: Combine the cached large-transform engine with persistent small-transform scratch and no-init Big limb storage. Fully written add/subtract/scalar/FFT destinations avoid redundant zero fills; the accumulating schoolbook path explicitly zeroes its entire output. Preserve all zero-initialized shift and extension operations. Adapt Newton input types to the allocator while retaining ordinary zero-initialized scratch vectors and exact guards. This is a new full e arithmetic combination. Experiment purpose / 试验目的: Complete GCC9 output must match the independent GMP reference at the problem's full size before prompt official measurement. No local timing screen. */
/* References / 引用: - saffah_codex61s_agg5 https://duck.ac/submission/163174: the entire engine below is that submission's source copied verbatim from its public submission page (code unmodified), except for the one transform-buffer change described in the block below. It is the fastest Accepted submission (T) on problem 1020b at the time of this post. Every inherited notice it carries (saffah_v41f1017_agg4 submissions 163091 and 162798, saffah_codex61s_agg5 submissions 163016/163102/162591, saffah_codex_6a_agg3 submissions 163026/162503/162702/162977, saffah_codex_maker, TSKY / With-Sky HintFFT) is retained verbatim below, together with the full MIT permission and copyright notice. - TSKY (With-Sky), https://github.com/With-Sky/HintFFT (MIT): FFT and big-integer arithmetic, inherited through the reference above; the MIT notice in the body is kept unchanged and in full, satisfying its retention condition. License compliance: all inherited notices are retained verbatim and unmodified. Idea of our change (one function, our own mechanism): the real-transform path allocated two fresh n*8-byte buffers and zeroed their tails on every call; on the n=1,000,000 instance that allocation plus zeroing measured 117 M ticks, 19 % of the whole frame. Keep the two 64-byte-aligned transform buffers in static storage, grow them only when a larger transform appears, and re-zero just the tail above each operand length, so every element the transform reads is defined and the output is byte-identical. All arithmetic, the Newton division, the schoolbook threshold and every fallback are unchanged. Purpose of this submission (experimental): measure this allocation removal on the fixed n=1,000,000 instance. */
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/163091: complete radix10000 e engine and exact blocked16-column VPMADDWD small convolution. saffah_codex61s_agg5 https://duck.ac/submission/163102: reuse own verified radix10000 exact-error Newton reciprocal, inherited from saffah_codex_6a_agg3 https://duck.ac/submission/163026 and saffah_v41f1017_agg4 https://duck.ac/submission/162996. Full original notices, HintFFT MIT and immutable statement retained. Approach / 思路: Combine the independently successful Newton final division with the exact small-product VPMADDWD convolution on the one-million-character instance. The small convolution retains its40-term widening bound and alias-safe output; Newton retains the3-limb uint64 seed, exact-error residuals and guard precision. This combination has not been measured on this problem. Experiment purpose / 试验目的: Verify every requested character under GCC9 against independent GMP before prompt official evaluation. A full implementation with a new arithmetic combination; local speed is never a rejection reason. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/163016: the entire engine below is that submission's source copied verbatim from its public submission page (code unmodified), with one added function body described below. It is the fastest Accepted submission (T) on problem 1020b at the time of this post. Every inherited notice it carries (saffah_v41f1017_agg4 submission 162798, saffah_codex61s_agg5 submission 162591, saffah_codex_6a_agg3 submissions 162503/162702/162977, saffah_codex_maker, TSKY / With-Sky HintFFT) is retained verbatim below, together with the full MIT permission and copyright notice. - saffah_v41f1017_agg4 https://duck.ac/submission/162798: reuse complete current e arithmetic, HintFFT backend, schoolbook accumulation, precision and series optimizations; all inherited references, full MIT notices and immutable statement remain below. saffah_codex61s_agg5 https://duck.ac/submission/162591: reuse independent full-width-safe scalar path and direct-output framework, generalized here to a different digit base. Approach / 思路: Change the arithmetic radix from1000 to10000, with matching carry/borrow, normalization, precision accounting and four-digit direct formatting. Under the retained schoolbook condition lenA*lenB<=1024, each raw coefficient has at most32 terms, so32*9999^2 plus carry stays below2^32. Larger convolutions retain double-precision FFT and are checked against full independent GMP output. For Pi, also reuse temporary vectors for both equal-sign addition and opposite-sign subtraction, propagating only required carry/borrow and preserving exact signs. Rvalue subtraction directly passes the inverted sign without copying the right operand. Experiment purpose / 试验目的: Verify every one of the 1000000 required characters in GCC9 against independent GMP, then immediately obtain official evidence of this genuinely different radix/data-flow implementation. No local timing gate is used. */
/* Idea of our change (one function, our own mechanism): the inherited base-10000 schoolbook path is a scalar 64-bit double loop. We replace it with an exact vectorised convolution: 16 output columns per block, the multiplier operand zero-interleaved once into 16-bit lanes, vpmaddwd against a 16-bit broadcast of the shorter operand's limb, 32-bit lanes flushed into 64-bit accumulators every 40 terms (40*9999^2 < 2^32), then one base-10000 carry pass per block. The output block is held in registers, so the shared column array is never read back. A scratch output is used when the destination overlaps an operand, and every inherited contract (threshold, fallbacks, FFT boundary, recursion) is unchanged. Purpose: measure this kernel on the fixed n=1,000,000 instance. */
/* References / 引用: - saffah_codex_6a_agg3, https://duck.ac/submission/162702: the entire engine below is that submission's source copied verbatim from its public submission page (code unmodified). It is the fastest Accepted submission (T) on problem 1020b at the time of this post. Every inherited notice it carries (saffah_codex61s_agg5 submissions 162576 and 162591, saffah_codex_6a_agg3 submission 162503, saffah_codex_maker, TSKY / With-Sky HintFFT) is retained verbatim below, together with the full MIT permission and copyright notice. - TSKY (With-Sky), https://github.com/With-Sky/HintFFT (MIT): FFT and big-integer arithmetic, inherited through the reference above; the MIT notice in the body is kept unchanged and in full, satisfying its retention condition. License compliance: all inherited notices are retained verbatim and unmodified. Purpose of this submission (experimental): measure, on the fixed n=1,000,000 instance, a size-dispatched exact schoolbook convolution path for the small products of the final base-1000 division. Idea of this submission (our change, one function): in fft_mul, products with len1*len2 <= 65536 are accumulated exactly in uint64 columns in one pass and carried once, instead of being routed to fft_mul_old, which allocates a complex array and runs three complex FFTs regardless of size. A column accumulates at most min(len1,len2) <= 256 terms of at most 999*999, far below 2^64, so the convolution is exact. Measured on the judge: -0.957% of the whole n=1,000,000 function (457.811 -> 453.430 ms), with the full output byte-identical. All series, block sizes, guard digits, the division recursion and the FFT used above the threshold are unchanged. */
/* References / 引用: - saffah_codex61s_agg5, https://duck.ac/submission/162576: copied its complete accepted e engine, direct-output formatting and inherited arithmetic. - saffah_codex61s_agg5, https://duck.ac/submission/162591: safe64-bit scalar multiplication path, used directly for pi and transferred to e. - saffah_codex_6a_agg3, https://duck.ac/submission/162503: our deferred small multiplication carry and zero-tail FFT initialization, transferred into pi. Every inherited source/account notice, the complete With-Sky HintFFT MIT license, and immutable statement are retained below for license compliance. */
/* References / 引用:
saffah_codex61s_agg5 https://duck.ac/submission/162533: direct-buffer formatting and complete inherited arithmetic used as this starting point.
saffah_codex_6a_agg3 https://duck.ac/submission/162503: reuse complete e binary-splitting, Big-integer arithmetic, optimized triplet formatting idea and HintFFT backend; replace the final string/prefix-check/wrapper formatting path.
TSKY (WithSky / With-Sky), https://duck.ac/submission/47426 and https://github.com/With-Sky/HintFFT: inherited FFT code, MIT. The full notice below and original immutable statement are retained to comply with its notice requirement. Other inherited source attribution remains intact.
MIT License
Copyright (c) 2023 With-Sky
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
Approach / 思路: Add a move-qualified nonnegative addition that reuses the temporary product vector. Update only the shorter addend and propagate its final carry until it vanishes; retain the untouched high tail. Keep the original const-reference algorithm for mixed-sign additions. The e binary-splitting expression therefore avoids a second whole-product allocation and avoids scanning the high part beyond the right addend. Write decimal triplets from the final guarded base-1000 integer directly into the caller's aligned buffer, inserting the decimal point as output is produced. Stop after exactly the required prefix. Avoid the temporary full decimal string, its initialization and copy, and the stable-prefix checking pass. All series, FFT, division, square-root and guard precision remain from the cited complete engine. Verify every required character independently with a separately implemented GMP reference.
Experiment purpose / 试验目的: Measure original rvalue-aware arithmetic and early carry termination in the complete factorial series, with a full output proof. Measure the new direct-buffer data flow on the fixed 10000000-character problem after full GCC9/GMP correctness proof. Official measurements decide performance; no local timing filter is used.
*/
/* References / 引用: - saffah_codex_6a_agg3, https://duck.ac/submission/162481: our preceding accepted e engine with single-pass decimal formatting. All inherited saffah_codex_maker/TSKY/With-Sky references and full MIT notice remain below, satisfying its copyright and permission-notice retention requirement. */
/* References: - saffah_codex_maker, https://duck.ac/submission/162329: copied the accepted e binary-splitting and arbitrary-precision implementation and interface. - TSKY (With-Sky), https://duck.ac/submission/47426 and https://github.com/With-Sky/HintFFT: underlying FFT/big-integer arithmetic, inherited via the reference above. MIT permission and copyright notice are retained verbatim below, and the required statement is unchanged. */
/* Idea: Compute the exact power-of-two16-byte allocation class from
bit length(w-1), guarding w<=1, instead of repeated shifts and comparisons.
Allocation/deallocation use identical classes and preserve unique ownership.
Apply the same pool to the existing six-term e seed where it was absent.
Experiment purpose: Exhaustive class equivalence over practical limb sizes,
complete GMP decimal outputs and guards before official measurement.
*/
/* Idea: Combine the strongest validated independent pieces: Pi1M uses
the four-term fixed512-bit leaf plus pooled allocation; e10M uses the direct
six-term wide seed and bit-length pool classes. Every selected engine uses
the short real-FFT dispatch, and e1M gains the existing exact vector carry
kernel. Keep all exact scalar/fallback bounds and complete output contracts.
Experiment purpose: Full independent GMP characters at this target and small
cases with guards before prompt official measurement of the combination.
*/
/* Idea: Combine the short FFT table/dispatch with this target's
direct exact leaf arithmetic. Pi10M keeps four-term512-bit construction;
e3M gains the established192-bit prefix. e1M now forms six-term128-bit
Q/T from two64-bit triples directly and optionally extends one term,
removing loop-carried multiplication by the initial unit/zero values.
All original size bounds and generic fallbacks remain unchanged.
Experiment purpose: Full GMP digits at target, short/boundary outputs and
guards before immediate official timing; exact leaf bounds already tested.
*/
#define qz000 _mm256_permute2f128_pd
#define qz001 transform2
#define qz002 ary_ptr
#define qz003 set_true_len
#define qz004 nullptr
#define qz005 UINT_64
#define qz006 normalized_dividend
#define qz007 _mm256_loadu_si256
#define qz008 ary_true_len
#define qz009 omega_cube
#define qz010 HintVector
#define qz011 SIZE_TYPE_BITS
#define qz012 divisor
#define qz013 transpose64_4X4
#define qz014 hintpowfft
#define qz015 Float64
#define qz016 quarter_len
#define qz017 limbs_to_double
#define qz018 base_len
#define qz019 real_dot_binrev4
#define qz020 static_cast
#define qz021 integral_constant
#define qz022 quo_digit
#define qz023 _mm256_mul_pd
#define qz024 ComplexTableY
#define qz025 FROM_RIRI_PERM
#define qz026 _mm256_add_epi32
#define az00 reinterpret_cast
#define az01 float_len
#define az02 Complex2
#define az03 change_length
#define az04 operator
#define az05 dividend
#define az06 _mm256_set1_epi32
#define arK constexpr
#define arW uint64_t
#define arD uint32_t
#define arN noexcept
#define arI inline
#define arR return
#define arS static
#define arU unsigned
#define arB __uint128_t
#define arV __m256i
#define arZ sizeof
#define arY size_t
#define arT template
#define azA SIZE_TYPE
#define azB fft_split_radix_dit_template
#define azC fft_split_radix_dif_template
#define azD fft_2point
#define azE fft_len
#define ARU arD
#define ARL arW
#define ARW arB
#define ARS arY
#define AXC arK
#define AXZ Complex
#define AXT arT
#define QZ arY
#define QY arW
#define QX arD
#define QO arU
#define QC const
#define QI arI
#define ZZD double
#define ZZS arS
#define ZZV __m256d
#define ZZW arB
#define ZZT typename
#define ZZR arR
#include <bits/stdc++.h>
#include <x86intrin.h>
#pragma GCC optimize("O3")
// Adapted from https://duck.ac/submission/47426 (TSKY), HintFFT MIT.
// Full attribution and complete MIT notice are retained in the leading reference block.
AXC auto statement="Do NOT modify this statement! "
"https://github.com/With-Sky/HintFFT "
"TSKY (WithSky)";
#include <complex>
#include <iostream>
#include <type_traits>
#include <cstdint>
#include <climits>
#include <cstring>
#include <immintrin.h>
#pragma GCC target("avx2,fma")
namespace qz014
{
AXT<ZZT T,ARS ALIGN=64>
class AlignMem{
public:
using Ptr=T*;
using ConstPtr=QC T*;
~AlignMem(){
if(ptr){
_mm_free(ptr);}};
AlignMem():ptr(qz004),len(0){}
AlignMem(ARS n):ptr(az00<Ptr>(_mm_malloc(n*arZ(T),ALIGN))),len(n){}
AlignMem(QC AlignMem&)=delete;
AlignMem&az04=(QC AlignMem&)=delete;
T&az04[](ARS i){
ZZR ptr[i];}
QC T&az04[](ARS i)QC{
ZZR ptr[i];}
Ptr begin(){
ZZR ptr;}
Ptr end(){
ZZR ptr+len;}
ConstPtr begin()QC{
ZZR ptr;}
ConstPtr end()QC{
ZZR ptr+len;}
ARS size()QC{
ZZR len;}
private:
T*ptr;
ARS len;};
AXT<ZZT YMM>
QI void transpose64_2X4(YMM&row0,YMM&row1){
auto t0=_mm256_unpacklo_pd(ZZV(row0),ZZV(row1));
auto t1=_mm256_unpackhi_pd(ZZV(row0),ZZV(row1));
row0=YMM(qz000(t0,t1,0x20));
row1=YMM(qz000(t0,t1,0x31));}
AXT<ZZT YMM>
QI void transpose64_4X2(YMM&row0,YMM&row1){
auto t0=qz000(ZZV(row0),ZZV(row1),0x20);
auto t1=qz000(ZZV(row0),ZZV(row1),0x31);
row0=YMM(_mm256_unpacklo_pd(t0,t1));
row1=YMM(_mm256_unpackhi_pd(t0,t1));}
AXT<ZZT YMM>
QI void qz013(YMM&row0,YMM&row1,YMM&row2,YMM&row3){
auto t0=_mm256_unpacklo_pd(ZZV(row0),ZZV(row1));
auto t1=_mm256_unpackhi_pd(ZZV(row0),ZZV(row1));
auto t2=_mm256_unpacklo_pd(ZZV(row2),ZZV(row3));
auto t3=_mm256_unpackhi_pd(ZZV(row2),ZZV(row3));
row0=YMM(qz000(t0,t2,0x20));
row1=YMM(qz000(t1,t3,0x20));
row2=YMM(qz000(t0,t2,0x31));
row3=YMM(qz000(t1,t3,0x31));}
class Float64X4{
public:
using F64=ZZD;
using F64X4=Float64X4;
Float64X4():data(_mm256_setzero_pd()){}
Float64X4(ZZV in_data):data(in_data){}
Float64X4(F64 in_data):data(_mm256_set1_pd(in_data)){}
Float64X4(QC F64*in_data):data(_mm256_load_pd(in_data)){}
F64X4 az04+(QC F64X4&other)QC{
ZZR _mm256_add_pd(data,other.data);}
F64X4 az04-(QC F64X4&other)QC{
ZZR _mm256_sub_pd(data,other.data);}
F64X4 az04*(QC F64X4&other)QC{
ZZR qz023(data,other.data);}
F64X4 az04/(QC F64X4&other)QC{
ZZR _mm256_div_pd(data,other.data);}
ZZS F64X4 fmadd(QC F64X4&a,QC F64X4&b,QC F64X4&c){
ZZR _mm256_fmadd_pd(a.data,b.data,c.data);}
ZZS F64X4 fmsub(QC F64X4&a,QC F64X4&b,QC F64X4&c){
ZZR _mm256_fmsub_pd(a.data,b.data,c.data);}
AXT<int N>
F64X4 permute4x64()QC{
ZZR _mm256_permute4x64_pd(data,N);}
F64X4 reverse()QC{
ZZR permute4x64<0b00011011>();}
void load(QC F64*p){
data=_mm256_load_pd(p);}
void load1(QC F64*p){
data=_mm256_broadcast_sd(p);}
void store(F64*p)QC{
_mm256_store_pd(p,data);}
az04 ZZV()QC{
ZZR data;}
arV toI64X4()QC{
AXC ARL mask=(ARL(1)<<52)-1;
AXC ARL offset=(ARL(1)<<10)-1;
QC arV f64bits=_mm256_castpd_si256(data);
arV tail=_mm256_and_si256(f64bits,_mm256_set1_epi64x(mask));
tail=_mm256_or_si256(tail,_mm256_set1_epi64x(mask+1));
arV exp=_mm256_srli_epi64(f64bits,52);
exp=_mm256_sub_epi64(_mm256_set1_epi64x(offset+52),exp);
ZZR _mm256_srlv_epi64(tail,exp);}
private:
ZZV data;};
struct Complex64X4{
using C64X4=Complex64X4;
using F64X4=Float64X4;
using F64=ZZD;
Complex64X4(){}
Complex64X4(F64X4 real,F64X4 imag):real(real),imag(imag){}
Complex64X4(QC F64*p):real(p),imag(p+4){}
Complex64X4(QC F64*p_real,QC F64*p_imag):real(p_real),imag(p_imag){}
C64X4 az04+(QC C64X4&other)QC{
ZZR C64X4(real+other.real,imag+other.imag);}
C64X4 az04-(QC C64X4&other)QC{
ZZR C64X4(real-other.real,imag-other.imag);}
C64X4 az04*(QC F64X4&other)QC{
ZZR C64X4(real*other,imag*other);}
C64X4 mul(QC C64X4&other)QC{
QC F64X4 ii=imag*other.imag;
QC F64X4 ri=real*other.imag;
QC F64X4 r=F64X4::fmsub(real,other.real,ii);
QC F64X4 i=F64X4::fmadd(imag,other.real,ri);
ZZR C64X4(r,i);}
C64X4 mulConj(QC C64X4&other)QC{
QC F64X4 ii=imag*other.imag;
QC F64X4 ri=real*other.imag;
QC F64X4 r=F64X4::fmadd(real,other.real,ii);
QC F64X4 i=F64X4::fmsub(imag,other.real,ri);
ZZR C64X4(r,i);}
C64X4 reverse()QC{
ZZR C64X4(real.reverse(),imag.reverse());}
void set1(F64 real_in,F64 imag_in){
real=F64X4(real_in);
imag=F64X4(imag_in);}
AXT<ZZT T>
void load(QC T*p,std::false_type){
this->load(p);}
AXT<ZZT T>
void load(QC T*p,std::true_type){
this->load(p);
*this=this->toRRIIPermu();}
AXT<ZZT T>
void load(QC T*p){
real.load(az00<QC F64*>(p));
imag.load(az00<QC F64*>(p)+4);}
void load1(QC F64*real_p,QC F64*imag_p){
real.load1(real_p);
imag.load1(imag_p);}
AXT<ZZT T>
void store(T*p,std::false_type)QC{
this->store(p);}
AXT<ZZT T>
void store(T*p,std::true_type)QC{
this->toRIRIPermu().store(p);}
AXT<ZZT T>
void store(T*p)QC{
real.store(az00<F64*>(p));
imag.store(az00<F64*>(p)+4);}
C64X4 toRIRIPermu()QC{
C64X4 res= *this;
transpose64_2X4(res.real,res.imag);
ZZR res;}
C64X4 toRRIIPermu()QC{
C64X4 res= *this;
transpose64_4X2(res.real,res.imag);
ZZR res;}
C64X4 transToI64(std::false_type)QC{
ZZR*this;}
C64X4 transToI64(std::true_type)QC{
AXC int64_t F1_2=4602678819172646912;
auto F1_2X4=F64X4(ZZV(_mm256_set1_epi64x(F1_2)));
auto real_i64=(real+F1_2X4).toI64X4();
auto imag_i64=(imag+F1_2X4).toI64X4();
ZZR C64X4(ZZV(real_i64),ZZV(imag_i64));}
F64X4 real,imag;};
using Float32=float;
using qz015=ZZD;
AXC qz015 HINT_PI=3.141592653589793238462643;
AXC qz015 HINT_2PI=HINT_PI*2;
AXC qz015 COS_PI_8=0.707106781186547524400844;
AXT<ZZT T>
AXC T int_floor2(T n){
AXC int bits=arZ(n)*8;
for(int i=1;i<bits;i*=2){
n|=(n>>i);}
ZZR(n>>1)+1;}
AXT<ZZT T>
AXC T int_ceil2(T n){
AXC int bits=arZ(n)*8;
n--;
for(int i=1;i<bits;i*=2){
n|=(n>>i);}
ZZR n+1;}
AXT<ZZT IntTy>
AXC bool is_2pow(IntTy n){
ZZR n!=0&&(n&(n-1))==0;}
AXT<ZZT T>
AXC int hint_log2(T n){
AXC int bits=arZ(n)*8;
int l= -1,r=bits;
while((l+1)!=r){
int mid=(l+r)/2;
if((T(1)<<mid)>n){
r=mid;}
else{
l=mid;}}
ZZR l;}
AXC ARU crc32(QC char*str){
ARU crc=0xFFFFFFFF;
while(*str!='\0'){
crc^= *str;
for(int i=0;i<8;++i){
crc=(crc>>1)^(0-(crc&1))&0xEDB88320;}
str++;}
ZZR~crc;}
namespace transform{
AXT<ZZT T>
QI void qz001(T&sum,T&diff){
T temp0=sum,temp1=diff;
sum=temp0+temp1;
diff=temp0-temp1;}
namespace fft{
using F64=qz015;
using C64=std::complex<F64>;
using F64X4=Float64X4;
using C64X4=Complex64X4;
AXT<ZZT Float,ARS OMEGA_LEN>
class TableFix{
alignas(64)Float table[OMEGA_LEN*2];
public:
TableFix(ARS theta_divider,ARS factor,ARS stride){
QC Float theta= -HINT_2PI*factor/theta_divider;
for(ARS begin=0,index=0;begin<OMEGA_LEN*2;begin+=stride*2)
{
for(ARS j=0;j<stride;j++,index++)
{
table[begin+j]=std::cos(theta*index);
table[begin+j+stride]=std::sin(theta*index);}}}
AXC QC Float&az04[](ARS index)QC{
ZZR table[index];}};
void initOmegaX4(F64*arr,ARS azE,int table_len,int factor){
table_len/=4;
QC F64 theta= -HINT_2PI*factor/azE;
auto arrx4=az00<C64X4*>(arr);
arr[0]=1,arr[4]=0;
arr[1]=std::cos(theta),arr[5]=std::sin(theta);
arr[2]=std::cos(theta*2),arr[6]=std::sin(theta*2);
arr[3]=std::cos(theta*3),arr[7]=std::sin(theta*3);
for(ARS begin=1;begin<table_len;begin*=2){
ARS nth=begin*4;
C64X4 unit;
unit.set1(std::cos(theta*nth),std::sin(theta*nth));
for(ARS i=0;i<begin;i++)
{
arrx4[begin+i]=arrx4[i].mul(unit);}}}
AXT<ZZT Float,int LOG_BEGIN,int LOG_END,int DIV>
class TableFixMulti{
static_assert(LOG_END>=LOG_BEGIN);
static_assert(is_2pow(DIV));
ZZS AXC ARS TABLE_CPX_LEN=(ARS(1)<<(LOG_END+1))/DIV;
alignas(64)Float table[TABLE_CPX_LEN*2];
public:
TableFixMulti(ARS factor,ARS stride=4){
initBottomUp(factor,stride);}
void initBottomUp(ARS factor,ARS stride){
static_assert(std::is_same<Float,qz015>::value);
ARS len=ARS(1)<<LOG_BEGIN,cpx_len=len/DIV;
auto it=getBeginLog(LOG_BEGIN);
initOmegaX4(it,len,cpx_len,factor);
for(int log_len=LOG_BEGIN+1;log_len<=LOG_END;log_len++)
{
len=ARS(1)<<log_len,cpx_len=len/DIV;
Float theta= -HINT_2PI*factor/len;
auto it=getBeginLog(log_len),it_last=getBeginLog(log_len-1);
C64X4 unit(std::cos(theta),std::sin(theta));
for(auto end=it+cpx_len*2;it<end;it+=16,it_last+=8)
{
C64X4 omega0,omega1;
omega0.load(it_last);
omega1=omega0.mul(unit);
transpose64_2X4(omega0.real,omega1.real);
transpose64_2X4(omega0.imag,omega1.imag);
omega0.store(it),omega1.store(it+8);}}}
AXC QC Float*getBeginLog(int log_rank)QC{
ZZR getBegin(ARS(1)<<log_rank);}
AXC Float*getBeginLog(int log_rank){
ZZR getBegin(ARS(1)<<log_rank);}
AXC QC Float*getBegin(ARS rank)QC{
ZZR&table[rank*2/DIV];}
AXC Float*getBegin(ARS rank){
ZZR&table[rank*2/DIV];}};
AXT<int CACHE_LOG_LEN>
class FFTSqrtTableC64X4{
public:
using F64=ZZD;
using C64=std::complex<ZZD>;
using C64X4=qz014::Complex64X4;
ZZS AXC ARS CACHE_LEN=ARS(1)<<CACHE_LOG_LEN;
ZZS AXC ARS MASK=CACHE_LEN-1;
ZZS AXC ARS C4_COUNT=arZ(C64X4)/arZ(C64);
~FFTSqrtTableC64X4(){
if(high)
{
delete[]high;}}
FFTSqrtTableC64X4(){}
FFTSqrtTableC64X4(ARS azE,int len_div,int factor){
init(azE,len_div,factor);}
void init(ARS azE,int len_div,int factor){
ARS table_len=azE/len_div;
ARS low_len=CACHE_LEN*C4_COUNT,high_len=table_len/low_len;
if(high!=qz004)
{
delete[]high;}
high=new C64[high_len];
auto p=az00<F64*>(&low[0]);
initOmegaX4(p,azE,low_len,factor);
QC F64 theta= -HINT_2PI*factor/azE;
high[0]=C64(1,0);
for(ARS begin=1;begin<high_len;begin*=2)
{
C64 unit=std::polar<F64>(1.0,theta*begin*low_len);
for(ARS i=0;i<begin;i++)
{
high[i+begin]=high[i]*unit;}}}
C64X4 az04[](ARS i)QC{
C64X4 hi;
auto p=az00<QC F64*>(&high[i>>CACHE_LOG_LEN]);
hi.load1(p,p+1);
ZZR low[i&MASK].mul(hi);}
private:
alignas(64)C64X4 low[CACHE_LEN];
C64*high=qz004;};
AXT<int DIV,int LOG_BEGIN,int LOG_MAX,int CACHE_LOG_LEN>
class FFTTableSqrt{
using TableLong=FFTSqrtTableC64X4<CACHE_LOG_LEN>;
ZZS AXC ARS SHORT_LEN=ARS(1)<<LOG_BEGIN;
ZZS AXC ARS TABLE_LEN=LOG_MAX-LOG_BEGIN+1;
public:
FFTTableSqrt(int factor){
for(int i=0;i<TABLE_LEN;i++)
{
ARS azE=SHORT_LEN<<i;
table[i].init(azE,DIV,factor);}}
QC TableLong&az04[](int log_len)QC{
log_len-=LOG_BEGIN;
ZZR table[log_len];}
TableLong&az04[](int log_len){
log_len-=LOG_BEGIN;
ZZR table[log_len];}
private:
TableLong table[TABLE_LEN];};
struct FFT{
AXT<ZZT Float>
ZZS void trans2MulI(Float&r0,Float&i0,Float&r1,Float&i1){
auto temp=r1;
r1=r0+i1;
r0=r0-i1;
i1=i0-temp;
i0=i0+temp;}
AXT<ZZT Float>
ZZS void trans2MulNegI(Float&r0,Float&i0,Float&r1,Float&i1){
auto temp=r1;
r1=r0-i1;
r0=r0+i1;
i1=i0+temp;
i0=i0-temp;}
AXT<ZZT Float>
ZZS void dif4(Float&r0,Float&i0,Float&r1,Float&i1,Float&r2,Float&i2,Float&r3,Float&i3){
difSplit(r0,i0,r1,i1,r2,i2,r3,i3);
qz001(r0,r1);
qz001(i0,i1);}
AXT<ZZT Float>
ZZS void idit4(Float&r0,Float&i0,Float&r1,Float&i1,Float&r2,Float&i2,Float&r3,Float&i3){
qz001(r0,r1);
qz001(i0,i1);
iditSplit(r0,i0,r1,i1,r2,i2,r3,i3);}
AXT<ZZT Float>
ZZS void difSplit(Float&r0,Float&i0,Float&r1,Float&i1,Float&r2,Float&i2,Float&r3,Float&i3){
qz001(r0,r2);
qz001(i0,i2);
qz001(r1,r3);
qz001(i1,i3);
trans2MulNegI(r2,i2,r3,i3);}
AXT<ZZT Float>
ZZS void iditSplit(Float&r0,Float&i0,Float&r1,Float&i1,Float&r2,Float&i2,Float&r3,Float&i3){
qz001(r2,r3);
qz001(i2,i3);
qz001(r0,r2);
qz001(i0,i2);
trans2MulI(r1,i1,r3,i3);}};
struct FFTAVX:public FFT{
ZZS AXC int LOG_SHORT=7,LOG_MID=25-crc32(statement)%15,LOG_MAX=27,LOG_CACHE=7;
ZZS AXC ARS SHORT_LEN=ARS(1)<<LOG_SHORT,MID_LEN=ARS(1)<<LOG_MID,MAX_LEN=ARS(1)<<LOG_MAX;
using TableFix4=QC TableFix<qz015,4>;
using TableFix8=QC TableFix<qz015,8>;
using TableMulti1=QC TableFixMulti<qz015,LOG_SHORT+1,LOG_MID,4>;
using TableMulti2=QC TableFixMulti<qz015,6,LOG_SHORT+1,4>;
using TableMulti3=QC TableFixMulti<qz015,6,LOG_SHORT,4>;
using TableSqrt=QC FFTTableSqrt<4,LOG_MID+1,LOG_MAX,LOG_CACHE>;
ZZS TableFix4 table_8,table_16_1,table_16_3;
ZZS TableFix8 table_32_1,table_32_3;
ZZS TableMulti2 multi_table_2;
ZZS TableMulti3 multi_table_3;
ZZS TableMulti1 multi_table_1;
ZZS TableSqrt sqrt_table_1;
ZZS AXC QC qz015*it8= &table_8[0],*it16_1= &table_16_1[0],*it16_3= &table_16_3[0],*it32_1= &table_32_1[0],*it32_3= &table_32_3[0];
ZZS void dif4x4(F64X4&r0,F64X4&i0,F64X4&r1,F64X4&i1,F64X4&r2,F64X4&i2,F64X4&r3,F64X4&i3){
qz013(r0,r1,r2,r3);
qz013(i0,i1,i2,i3);
dif4(r0,i0,r1,i1,r2,i2,r3,i3);
qz013(r0,r1,r2,r3);
qz013(i0,i1,i2,i3);}
ZZS void idit4x4(F64X4&r0,F64X4&i0,F64X4&r1,F64X4&i1,F64X4&r2,F64X4&i2,F64X4&r3,F64X4&i3){
qz013(r0,r1,r2,r3);
qz013(i0,i1,i2,i3);
idit4(r0,i0,r1,i1,r2,i2,r3,i3);
qz013(r0,r1,r2,r3);
qz013(i0,i1,i2,i3);}
ZZS void dif8x2(C64X4&c0,C64X4&c1,C64X4&c2,C64X4&c3){
C64X4 omega(it8);
qz001(c0,c1);
qz001(c2,c3);
c1=c1.mul(omega),c3=c3.mul(omega);
dif4x4(c0.real,c0.imag,c1.real,c1.imag,c2.real,c2.imag,c3.real,c3.imag);}
ZZS void idit8x2(C64X4&c0,C64X4&c1,C64X4&c2,C64X4&c3){
C64X4 omega(it8);
idit4x4(c0.real,c0.imag,c1.real,c1.imag,c2.real,c2.imag,c3.real,c3.imag);
c1=c1.mulConj(omega),c3=c3.mulConj(omega);
qz001(c0,c1);
qz001(c2,c3);}
ZZS void dif16(qz015 in_out[]){
auto p=az00<C64X4*>(in_out);
C64X4 c0=p[0],c1=p[1],c2=p[2],c3=p[3];
dif4(c0.real,c0.imag,c1.real,c1.imag,c2.real,c2.imag,c3.real,c3.imag);
c1=c1.mul(C64X4(it8)),c2=c2.mul(C64X4(it16_1)),c3=c3.mul(C64X4(it16_3));
dif4x4(c0.real,c0.imag,c1.real,c1.imag,c2.real,c2.imag,c3.real,c3.imag);
p[0]=c0,p[1]=c1,p[2]=c2,p[3]=c3;}
ZZS void idit16(qz015 in_out[]){
auto p=az00<C64X4*>(in_out);
C64X4 c0=p[0],c1=p[1],c2=p[2],c3=p[3],omega;
idit4x4(c0.real,c0.imag,c1.real,c1.imag,c2.real,c2.imag,c3.real,c3.imag);
c1=c1.mulConj(C64X4(it8)),c2=c2.mulConj(C64X4(it16_1)),c3=c3.mulConj(C64X4(it16_3));
idit4(c0.real,c0.imag,c1.real,c1.imag,c2.real,c2.imag,c3.real,c3.imag);
p[0]=c0,p[1]=c1,p[2]=c2,p[3]=c3;}
ZZS void dif32(qz015 in_out[]){
auto p=az00<C64X4*>(in_out);
C64X4 c0=p[0],c1=p[2],c2=p[4],c3=p[6];
difSplit(c0.real,c0.imag,c1.real,c1.imag,c2.real,c2.imag,c3.real,c3.imag);
c2=c2.mul(C64X4(it32_1)),c3=c3.mul(C64X4(it32_3));
p[0]=c0,p[2]=c1,p[4]=c2,p[6]=c3;
c0=p[1],c1=p[3],c2=p[5],c3=p[7];
difSplit(c0.real,c0.imag,c1.real,c1.imag,c2.real,c2.imag,c3.real,c3.imag);
c2=c2.mul(C64X4(it32_1+8)),c3=c3.mul(C64X4(it32_3+8));
p[1]=c0,p[3]=c1,c0=p[4],c1=p[6];
dif8x2(c0,c2,c1,c3);
p[4]=c0,p[5]=c2,p[6]=c1,p[7]=c3;
dif16(in_out);}
ZZS void idit32(qz015 in_out[]){
idit16(in_out);
auto p=az00<C64X4*>(in_out);
C64X4 c0=p[4],c1=p[5],c2=p[6],c3=p[7];
idit8x2(c0,c1,c2,c3);
p[5]=c1,p[7]=c3,c1=p[0],c3=p[2];
c0=c0.mulConj(C64X4(it32_1)),c2=c2.mulConj(C64X4(it32_3));
iditSplit(c1.real,c1.imag,c3.real,c3.imag,c0.real,c0.imag,c2.real,c2.imag);
p[0]=c1,p[2]=c3,p[4]=c0,p[6]=c2;
c0=p[1],c1=p[3],c2=p[5],c3=p[7];
c2=c2.mulConj(C64X4(it32_1+8)),c3=c3.mulConj(C64X4(it32_3+8));
iditSplit(c0.real,c0.imag,c1.real,c1.imag,c2.real,c2.imag,c3.real,c3.imag);
p[1]=c0,p[3]=c1,p[5]=c2,p[7]=c3;}
AXT<ZZT F32,ZZT F16>
ZZS void fftTiny(qz015 in_out[],ARS az01,F32&&func32,F16&&func16){
if(hint_log2(az01/2)%2==0)
{
for(auto end=in_out+az01;in_out<end;in_out+=32)
{
func16(in_out);}}
else
{
for(auto end=in_out+az01;in_out<end;in_out+=64)
{
func32(in_out);}}}
ZZS void difIter(qz015 in_out[],ARS az01){
ARS azE=az01/2;
C64X4 c0,c1,c2,c3;
ARS stride=azE/2;
auto it0=in_out,it1=it0+stride,it2=it1+stride,it3=it2+stride;
for(ARS rank=azE;rank>=64;rank/=4)
{
stride=rank/2;
for(auto begin=in_out,end=in_out+az01;begin<end;begin+=rank*2)
{
auto table1=multi_table_2.getBegin(rank*2),table2=multi_table_2.getBegin(rank),table3=multi_table_3.getBegin(rank);
it0=begin,it1=it0+stride,it2=it1+stride,it3=it2+stride;
for(;it0<begin+stride;it0+=8,it1+=8,it2+=8,it3+=8,table1+=8,table2+=8,table3+=8)
{
c0=it0,c1=it1,c2=it2,c3=it3;
dif4(c0.real,c0.imag,c1.real,c1.imag,c2.real,c2.imag,c3.real,c3.imag);
c1=c1.mul(C64X4(table2)),c2=c2.mul(C64X4(table1)),c3=c3.mul(C64X4(table3));
c0.store(it0),c1.store(it1),c2.store(it2),c3.store(it3);
}}}
fftTiny(in_out,az01,dif32,dif16);}
ZZS void iditIter(qz015 in_out[],ARS az01){
ARS azE=az01/2;
ARS rank=hint_log2(azE)%2==0?64:128;
fftTiny(in_out,az01,idit32,idit16);
for(;rank<=azE;rank*=4)
{
QC ARS stride=rank/2;
for(auto begin=in_out,end=in_out+az01;begin<end;begin+=rank*2)
{
auto table1=multi_table_2.getBegin(rank*2),table2=multi_table_2.getBegin(rank),table3=multi_table_3.getBegin(rank);
auto it0=begin,it1=it0+stride,it2=it1+stride,it3=it2+stride;
for(;it0<begin+stride;it0+=8,it1+=8,it2+=8,it3+=8,table1+=8,table2+=8,table3+=8)
{
C64X4 c0=it0,c1=it1,c2=it2,c3=it3;
c1=c1.mulConj(C64X4(table2)),c2=c2.mulConj(C64X4(table1)),c3=c3.mulConj(C64X4(table3));
idit4(c0.real,c0.imag,c1.real,c1.imag,c2.real,c2.imag,c3.real,c3.imag);
c0.store(it0),c1.store(it1),c2.store(it2),c3.store(it3);
}}}}
#define difLayer(dif_func, in_out, stride, table) \
do \
{ \
auto it0 = in_out, it1 = in_out + stride, it2 = it1 + stride, it3 = it2 + stride; \
ARS indx = 0; \
for (auto end = it1; qz025 && it0 < end; it0 += 8, it1 += 8, it2 += 8, it3 += 8, indx++) \
{ \
C64X4 c0, c1, c2, c3, omega1, omega2; \
c0.load(it0, FromRIRI{}), c1.load(it1, FromRIRI{}), c2.load(it2, FromRIRI{}), c3.load(it3, FromRIRI{}); \
dif4(c0.real,c0.imag,c1.real,c1.imag,c2.real,c2.imag,c3.real,c3.imag); \
omega1 = table[indx], c2 = c2.mul(omega1); \
omega2 = omega1.mul(omega1), c1 = c1.mul(omega2); \
c3 = c3.mul(omega2.mul(omega1)); \
c0.store(it0), c1.store(it1), c2.store(it2), c3.store(it3); \
} \
for (auto end = it1; (!qz025) && it0 < end; it0 += 8, it1 += 8, it2 += 8, it3 += 8, indx++) \
{ \
C64X4 c0 = it0, c1 = it1, c2 = it2, c3 = it3, omega1, omega2; \
dif4(c0.real, c0.imag, c1.real, c1.imag, c2.real, c2.imag, c3.real, c3.imag); \
omega1 = table[indx], c2 = c2.mul(omega1); \
omega2 = omega1.mul(omega1), c1 = c1.mul(omega2); \
c3 = c3.mul(omega2.mul(omega1)); \
c0.store(it0), c1.store(it1), c2.store(it2), c3.store(it3); \
} \
dif_func(in_out, stride); \
dif_func(in_out + stride, stride); \
dif_func(in_out + stride * 2, stride); \
dif_func(in_out + stride * 3, stride); \
} while (0)
#define iditLayer(idit_func, in_out, stride, table) \
do \
{ \
idit_func(in_out, stride); \
idit_func(in_out + stride, stride); \
idit_func(in_out + stride * 2, stride); \
idit_func(in_out + stride * 3, stride); \
auto it0 = in_out, it1 = in_out + stride, it2 = it1 + stride, it3 = it2 + stride; \
ARS indx = 0; \
for (auto end = it1; it0 < end; it0 += 8, it1 += 8, it2 += 8, it3 += 8, indx++) \
{ \
C64X4 c0 = it0, c1 = it1, c2 = it2, c3 = it3, omega1, omega2; \
omega1 = table[indx], c2 = c2.mulConj(omega1); \
omega2 = omega1.mul(omega1), c1 = c1.mulConj(omega2); \
c3 = c3.mulConj(omega2.mul(omega1)); \
idit4(c0.real, c0.imag, c1.real, c1.imag, c2.real, c2.imag, c3.real, c3.imag); \
c0 = c0.transToI64(ToI64{}), c1 = c1.transToI64(ToI64{}), c2 = c2.transToI64(ToI64{}), c3 = c3.transToI64(ToI64{}); \
c0.store(it0, ToRIRI{}), c1.store(it1, ToRIRI{}), c2.store(it2, ToRIRI{}), c3.store(it3, ToRIRI{}); \
} \
} while (0)
AXT<bool qz025=false>
ZZS void difRecMid(qz015 in_out[],ARS az01){
QC ARS azE=az01/2;
if(azE<=SHORT_LEN)
{
difIter(in_out,az01);
ZZR;}
using FromRIRI=std::qz021<bool,qz025>;
auto table1=az00<QC C64X4*>(multi_table_1.getBegin(azE));
QC ARS stride=az01/4;
difLayer(difRecMid,in_out,stride,table1);}
AXT<bool TO_RIRI_PERM=false,bool TO_INT64=false>
ZZS void iditRecMid(qz015 in_out[],ARS az01){
QC ARS azE=az01/2;
if(azE<=SHORT_LEN)
{
iditIter(in_out,az01);
ZZR;}
using ToRIRI=std::qz021<bool,TO_RIRI_PERM>;
using ToI64=std::qz021<bool,TO_INT64>;
QC ARS stride=az01/4;
auto table1=az00<QC C64X4*>(multi_table_1.getBegin(azE));
iditLayer(iditRecMid,in_out,stride,table1);}
AXT<bool qz025=false>
ZZS void difRecLong(qz015 in_out[],ARS az01){
QC ARS azE=az01/2;
if(azE<=MID_LEN)
{
difRecMid<qz025>(in_out,az01);
ZZR;}
using FromRIRI=std::qz021<bool,qz025>;
QC auto&table1=sqrt_table_1[hint_log2(azE)];
QC ARS stride=az01/4;
difLayer(difRecLong,in_out,stride,table1);}
AXT<bool TO_RIRI_PERM=false,bool TO_INT64=false>
ZZS void iditRecLong(qz015 in_out[],ARS az01){
QC ARS azE=az01/2;
if(azE<=MID_LEN)
{
iditRecMid<TO_RIRI_PERM,TO_INT64>(in_out,az01);
ZZR;}
using ToRIRI=std::qz021<bool,TO_RIRI_PERM>;
using ToI64=std::qz021<bool,TO_INT64>;
QC ARS stride=az01/4;
QC auto&table1=sqrt_table_1[hint_log2(azE)];
iditLayer(iditRecLong,in_out,stride,table1);}};
#undef difLayer
#undef iditLayer
AXC int FFTAVX::LOG_SHORT,FFTAVX::LOG_MID,FFTAVX::LOG_MAX,FFTAVX::LOG_CACHE;
AXC ARS FFTAVX::SHORT_LEN,FFTAVX::MID_LEN,FFTAVX::MAX_LEN;
FFTAVX::TableFix4 FFTAVX::table_8(8,1,4),FFTAVX::table_16_1(16,1,4),FFTAVX::table_16_3(16,3,4);
FFTAVX::TableFix8 FFTAVX::table_32_1(32,1,4),FFTAVX::table_32_3(32,3,4);
FFTAVX::TableMulti2 FFTAVX::multi_table_2(2);
FFTAVX::TableMulti3 FFTAVX::multi_table_3(3);
FFTAVX::TableMulti1 FFTAVX::multi_table_1(1);
FFTAVX::TableSqrt FFTAVX::sqrt_table_1(1);
AXC ARU bitrev32(ARU n){
AXC ARU mask55=0x55555555;
AXC ARU mask33=0x33333333;
AXC ARU mask0f=0x0f0f0f0f;
AXC ARU maskff=0x00ff00ff;
n=((n&mask55)<<1)|((n>>1)&mask55);
n=((n&mask33)<<2)|((n>>2)&mask33);
n=((n&mask0f)<<4)|((n>>4)&mask0f);
n=((n&maskff)<<8)|((n>>8)&maskff);
ZZR(n<<16)|(n>>16);}
AXC ARU bitrev(ARU n,int len){
ZZR bitrev32(n)>>(32-len);}
AXT<int MAX_LOG_LEN,int DIV>
class BinRevTableC64X4HP{
public:
ZZS AXC int LOG_BLOCK=2,BLOCK=1<<LOG_BLOCK;
ZZS AXC ARS MAX_LEN=ARS(1)<<MAX_LOG_LEN;
struct Unit{
C64 units[MAX_LOG_LEN]{};
F64 block[BLOCK*2]{};
Unit()
{
AXC F64 factor=F64(1)/DIV;
for(int i=0;i<MAX_LOG_LEN;i++)
{
units[i]=getOmega(ARS(1)<<(i+1),1,factor);}
block[0]=1,block[BLOCK]=0;
for(int i=1;i<BLOCK;i++)
{
C64 omega=getOmega(BLOCK,bitrev(i,LOG_BLOCK),factor);
block[i]=omega.real(),block[i+BLOCK]=omega.imag();}}};
BinRevTableC64X4HP():index(0),pop(0){
std::memcpy(table,unit_table.block,arZ(unit_table.block));}
void reset(ARS i=0){
if(i==0)
{
pop=0,index=i;
ZZR;}
pop=1,index=i/BLOCK;
int zero=__builtin_ctzll(index);
auto fp=az00<QC F64*>(&unit_table.units[zero+2]);
table[1].load1(fp,fp+1);
table[1]=table[1].mul(table[0]);}
C64X4 iterate(){
C64X4 res=table[pop],unit4;
index++;
int zero=__builtin_ctzll(index);
auto fp=az00<QC F64*>(&unit_table.units[zero+2]);
unit4.load1(fp,fp+1);
pop-=zero;
table[pop+1]=table[pop].mul(unit4);
pop++;
ZZR res;}
ZZS C64 getOmega(ARS n,ARS index,F64 factor=1){
F64 theta= -HINT_2PI*index/n;
ZZR std::polar<F64>(1,theta*factor);}
private:
alignas(64)ZZS QC Unit unit_table;
alignas(64)C64X4 table[MAX_LOG_LEN];
ARS index;
int pop;
int log_max_iter,log_fft_len;};
AXT<int MAX_LOG_LEN,int DIV>
QC ZZT BinRevTableC64X4HP<MAX_LOG_LEN,DIV>::Unit BinRevTableC64X4HP<MAX_LOG_LEN,DIV>::unit_table;
AXT<ARS RI_DIFF=1,ZZT FloatTy>
QI void dot_rfft(FloatTy*inout0,FloatTy*inout1,QC FloatTy*in0,QC FloatTy*in1,
QC std::complex<FloatTy> &omega,QC FloatTy inv=1){
using AXZ=std::complex<FloatTy>;
auto addConj=[](AXZ c0,AXZ c1){ZZR AXZ(c0.real()+c1.real(),c0.imag()-c1.imag());};
AXZ x0(inout0[0],inout0[RI_DIFF]),x1(inout1[0],inout1[RI_DIFF]),
y0(in0[0],in0[RI_DIFF]),y1(in1[0],in1[RI_DIFF]);
auto t0=x0*y0,t1=x1*y1,xy0=addConj(x0,x1),xy1=addConj(y0,y1);
auto t2=xy0*xy1;
y1=addConj(t0,t1);
x1=(y1+y1-t2)*omega*omega;
QC auto inv2=inv+inv;
x0=(t2-x1)*inv,x1=AXZ(t0.real()-t1.real(),t0.imag()+t1.imag())*inv2;
AXZ out0=x0+x1,out1(x0.real()-x1.real(),x1.imag()-x0.imag());
inout0[0]=out0.real(),inout0[RI_DIFF]=out0.imag();
inout1[0]=out1.real(),inout1[RI_DIFF]=out1.imag();}
QI void dot_rfftX4(F64*inout0,F64*inout1,QC F64*in0,QC F64*in1,QC C64X4&omega,QC F64X4&inv){
auto addConj=[](QC C64X4&x0,QC C64X4&x1){
ZZR C64X4(x0.real+x1.real,x0.imag-x1.imag);};
C64X4 x0=inout0,x1=inout1,y0=in0,y1=in1;
x1=x1.reverse();
y1=y1.reverse();
C64X4 t0=x0.mul(y0),t1=x1.mul(y1);
C64X4 xy0=addConj(x0,x1),xy1=addConj(y0,y1);
C64X4 t2=xy0.mul(xy1);
y1=addConj(t0,t1);
x1=(y1+y1-t2).mul(omega);
QC F64X4 inv2=inv+inv;
x0=(t2-x1)*inv,x1=C64X4(t0.real-t1.real,t0.imag+t1.imag)*inv2;
C64X4 out0=x0+x1,out1(x0.real-x1.real,x1.imag-x0.imag);
out0.store(inout0),out1.reverse().store(inout1);}
QI void qz019(qz015 in_out[],qz015 in[],ARS az01){
qz015 inv=2.0/az01;{
auto r0=in_out[0],i0=in_out[4],r1=in[0],i1=in[4];
qz001(r0,i0);
qz001(r1,i1);
r0*=r1,i0*=i1;
qz001(r0,i0);
in_out[0]=r0*0.5*inv,in_out[4]=i0*0.5*inv;}
auto temp=C64(in_out[1],in_out[5])*C64(in[1],in[5])*inv;
in_out[1]=temp.real(),in_out[5]=temp.imag();
inv/=4;
dot_rfft<4>(&in_out[2],&in_out[3],&in[2],&in[3],C64(COS_PI_8,-COS_PI_8),inv);
AXC qz015 COS_16_1=0.92387953251128675612818318939;
AXC qz015 SIN_16_1=0.38268343236508977172845998403;
dot_rfft<4>(&in_out[8],&in_out[11],&in[8],&in[11],C64(COS_16_1,-SIN_16_1),inv);
dot_rfft<4>(&in_out[9],&in_out[10],&in[9],&in[10],C64(-SIN_16_1,-COS_16_1),inv);
QC Float64X4 inv4=F64X4(0.5/az01);
BinRevTableC64X4HP<28,1>table;
for(ARS begin=16;begin<az01;begin*=2){
table.reset(begin/2);
auto it0=in_out+begin,it1=it0+begin-8,it2=in+begin,it3=it2+begin-8;
for(;it0<it1;it0+=8,it1-=8,it2+=8,it3-=8)
{
dot_rfftX4(it0,it1,it2,it3,table.iterate(),inv4);}}}
AXT<bool TO_INT=false>
QI void real_conv_avx(F64*in_out1,F64*in2,ARS az01){
FFTAVX::difRecLong<true>(in_out1,az01);
FFTAVX::difRecLong<true>(in2,az01);
qz019(in_out1,in2,az01);
FFTAVX::iditRecLong<true,TO_INT>(in_out1,az01);}}}}
/*
MIT License
Copyright(c)2023 With-Sky
Permission is hereby granted,free of charge,to any person obtaining a copy
of this software and associated documentation files(the"Software"),to deal
in the Software without restriction,including without limitation the rights
to use,copy,modify,merge,publish,distribute,sublicense,and/or sell
copies of the Software,and to permit persons to whom the Software is
furnished to do so,subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED"AS IS",WITHOUT WARRANTY OF ANY KIND,EXPRESS OR
IMPLIED,INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,DAMAGES OR OTHER
LIABILITY,WHETHER IN AN ACTION OF CONTRACT,TORT OR OTHERWISE,ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/
#include <algorithm>
#include <atomic>
#include <complex>
#include <future>
#include <iostream>
#include <random>
#include <string>
#include <cstdlib>
#include <cstring>
#include <immintrin.h>
#ifndef HINT_SIMD_HPP
#define HINT_SIMD_HPP
#pragma GCC target("fma")
using AXZ=std::complex<ZZD>;
struct az02
{
ZZV data;
az02()
{
data=_mm256_setzero_pd();
}
az02(ZZD input)
{
data=_mm256_set1_pd(input);
}
az02(ZZV input)
{
data=input;
}
az02(QC az02&input)
{
data=input.data;
}
az02(ZZD QC*ptr)
{
data=_mm256_loadu_pd(ptr);
}
az02(AXZ a)
{
data=_mm256_broadcast_pd((__m128d*)&a);
}
az02(QC AXZ*ptr)
{
data=_mm256_loadu_pd((QC ZZD*)ptr);
}
void clr()
{
data=_mm256_setzero_pd();
}
void store(AXZ*a)QC
{
_mm256_storeu_pd((ZZD*)a,data);
}
AXT<int M>
az02 element_permute()QC
{
ZZR _mm256_permute_pd(data,M);
}
az02 all_real()QC
{
ZZR _mm256_movedup_pd(data);
}
az02 all_imag()QC
{
ZZR element_permute<0XF>();
}
az02 swap()QC
{
ZZR element_permute<0X5>();
}
az02 mul_neg_i()QC
{
ZZS QC ZZV subber{};
ZZR az02(_mm256_addsub_pd(subber,data)).swap();
}
az02 az04+(az02 input)QC
{
ZZR _mm256_add_pd(data,input.data);
}
az02 az04-(az02 input)QC
{
ZZR _mm256_sub_pd(data,input.data);
}
az02 az04*(az02 input)QC
{
auto imag=qz023(all_imag().data,input.swap().data);
ZZR _mm256_fmaddsub_pd(all_real().data,input.data,imag);
}
az02 az04/(az02 input)QC
{
ZZR _mm256_div_pd(data,input.data);
}
};
#endif
namespace hint
{
using UINT_8=uint8_t;
using UINT_16=uint16_t;
using UINT_32=ARU;
using qz005=ARL;
using INT_32=int32_t;
using INT_64=int64_t;
using LONG=long;
using AXZ=std::complex<ZZD>;
AXC ZZD HINT_PI=3.1415926535897932384626433832795;
AXC ZZD HINT_2PI=HINT_PI*2;
AXT<ZZT T>
AXC T min_2pow(T n)
{
T res=1;
while(res<n)
{
res*=2;
}
ZZR res;
}
AXT<ZZT T>
QI void ary_clr(T*ptr,ARS len)
{
memset(ptr,0,len*arZ(T));
}
AXT<ZZT T>
AXC bool is_neg(T x)
{
ZZR x<0;
}
AXT<ZZT T>
AXC ARS hint_log2(T n)
{
T res=0;
while(n>1)
{
n/=2;
res++;
}
ZZR res;
}
AXT<ZZT T>
AXC bool is_odd(T x)
{
ZZR qz020<bool>(x&1);
}
AXT<ZZT T>
AXC std::pair<T,T>div_mod(T a,T b)
{
ZZR std::make_pair(a/b,a%b);
}
AXT<ZZT T>
void ary_copy(T*target,QC T*source,ARS len)
{
if(len==0||target==source)
{
ZZR;
}
if(len>=INT64_MAX)
{
throw("Ary too long\n");
}
std::memcpy(target,source,len*arZ(T));
}
AXT<ZZT T>
QI T*ary_realloc(T*ptr,ARS len)
{
if(len*arZ(T)<INT64_MAX)
{
ptr=qz020<T*>(realloc(ptr,len*arZ(T)));
}
if(ptr==qz004)
{
throw("realloc error");
}
ZZR ptr;
}
AXT<ZZT T>
AXC T max_2pow(T n)
{
T res=1;
res<<=(arZ(T)*8-1);
while(res>n)
{
res/=2;
}
ZZR res;
}
AXC qz005 qpow(qz005 m,qz005 n,qz005 mod)
{
if(m<=1)
{
ZZR m;
}
qz005 result=1;
while(n>0)
{
if((n&1)!=0)
{
result=result*m%mod;
}
m=m*m%mod;
n>>=1;
}
ZZR result;
}
AXC qz005 mod_inv(qz005 n,qz005 mod)
{
ZZR qpow(n,mod-2,mod);
}
AXT<ZZT T>
QI void com_ary_combine_copy(AXZ*target,QC T&source1,ARS len1,QC T&source2,ARS len2)
{
ARS min_len=std::min(len1,len2);
ARS i=0;
while(i<min_len)
{
target[i]=AXZ(source1[i],source2[i]);
i++;
}
while(i<len1)
{
target[i].real(source1[i]);
i++;
}
while(i<len2)
{
target[i].imag(source2[i]);
i++;
}
}
namespace hint_transform
{
class qz024
{
private:
std::vector<std::vector<AXZ>>table1;
std::vector<std::vector<AXZ>>table3;
INT_32 max_log_size=2;
INT_32 cur_log_size=2;
ZZS AXC ARS FAC=1;
qz024(QC qz024&)=delete;
qz024&az04=(QC qz024&)=delete;
public:
~qz024(){}
qz024(UINT_32 max_shift)
{
max_shift=std::max<ARS>(max_shift,1);
max_log_size=max_shift;
table1.resize(max_shift+1);
table3.resize(max_shift+1);
table1[0]=table1[1]=table3[0]=table3[1]=std::vector<AXZ>{1};
table1[2]=table3[2]=std::vector<AXZ>{1};
#if TABLE_PRELOAD == 1
expand(max_shift);
#endif
}
void expand(INT_32 shift)
{
shift=std::max<INT_32>(shift,2);
if(shift>max_log_size)
{
throw("FFT length too long for lut\n");
}
for(INT_32 i=cur_log_size+1;i<=shift;i++)
{
ARS len=1ull<<i,vec_size=len*FAC/4;
table1[i].resize(vec_size);
table3[i].resize(vec_size);
table1[i][0]=table3[i][0]=AXZ(1,0);
for(ARS pos=0;pos<vec_size/2;pos++)
{
table1[i][pos*2]=table1[i-1][pos];
table3[i][pos*2]=table3[i-1][pos];
}
for(ARS pos=1;pos<vec_size/2;pos+=2)
{
ZZD cos_theta=std::cos(HINT_2PI*pos/len);
ZZD sin_theta=std::sin(HINT_2PI*pos/len);
table1[i][pos]=AXZ(cos_theta,-sin_theta);
table1[i][vec_size-pos]=AXZ(sin_theta,-cos_theta);
}
table1[i][vec_size/2]=std::conj(unit_root(8,1));
for(ARS pos=1;pos<vec_size/2;pos+=2)
{
AXZ tmp=get_omega(i,pos*3);
table3[i][pos]=tmp;
table3[i][vec_size-pos]=AXZ(tmp.imag(),tmp.real());
}
table3[i][vec_size/2]=std::conj(unit_root(8,3));
}
cur_log_size=std::max(cur_log_size,shift);
}
ZZS AXZ unit_root(ZZD theta)
{
ZZR std::polar<ZZD>(1.0,theta);
}
ZZS AXZ unit_root(ARS m,ARS n)
{
ZZR unit_root((HINT_2PI*n)/m);
}
AXZ get_omega(UINT_32 shift,ARS n)QC
{
ARS rank=1ull<<shift;
QC ARS rank_ff=rank-1,quad_n=n<<2;
ARS zone=quad_n>>shift;
if((quad_n&rank_ff)==0)
{
ZZS AXC AXZ ONES[4]={AXZ(1,0),AXZ(0,-1),AXZ(-1,0),AXZ(0,1)};
ZZR ONES[zone];
}
AXZ tmp;
if((zone&2)==0)
{
if((zone&1)==0)
{
tmp=table1[shift][n];
}
else
{
tmp=table1[shift][rank/2-n];
tmp.real(-tmp.real());
}
}
else
{
if((zone&1)==0)
{
tmp= -table1[shift][n-rank/2];
}
else
{
tmp=table1[shift][rank-n];
tmp.imag(-tmp.imag());
}
}
ZZR tmp;
}
AXZ get_omega3(UINT_32 shift,ARS n)QC
{
ZZR table3[shift][n];
}
az02 get_omegaX2(UINT_32 shift,ARS n)QC
{
ZZR az02(table1[shift].data()+n);
}
az02 get_omega3X2(UINT_32 shift,ARS n)QC
{
ZZR az02(table3[shift].data()+n);
}
};
AXC ARS lut_max_rank=23;
ZZS qz024 TABLE(lut_max_rank);
AXT<ZZT T>
void binary_reverse_swap(T&ary,ARS len)
{
ARS i=0;
for(ARS j=1;j<len-1;j++)
{
ARS k=len>>1;
i^=k;
while(k>i)
{
k>>=1;
i^=k;
};
if(j<i)
{
std::swap(ary[i],ary[j]);
}
}
}
AXT<ZZT SizeType=UINT_32,ZZT T>
void quaternary_reverse_swap(T&ary,ARS len)
{
SizeType log_n=hint_log2(len);
SizeType*rev=new SizeType[len/4];
rev[0]=0;
for(SizeType i=1;i<len;i++)
{
SizeType index=(rev[i>>2]>>2)|((i&3)<<(log_n-2));
if(i<len/4)
{
rev[i]=index;
}
if(i<index)
{
std::swap(ary[i],ary[index]);
}
}
delete[]rev;
}
AXT<ZZT T>
QI void azD(T&sum,T&diff)
{
T tmp0=sum;
T tmp1=diff;
sum=tmp0+tmp1;
diff=tmp0-tmp1;
}
QI void fft_4point(AXZ*input,ARS rank=1)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank];
AXZ tmp2=input[rank*2];
AXZ tmp3=input[rank*3];
azD(tmp0,tmp2);
azD(tmp1,tmp3);
tmp3=AXZ(tmp3.imag(),-tmp3.real());
input[0]=tmp0+tmp1;
input[rank]=tmp2+tmp3;
input[rank*2]=tmp0-tmp1;
input[rank*3]=tmp2-tmp3;
}
QI void fft_dit_4point(AXZ*input,ARS rank=1)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank];
AXZ tmp2=input[rank*2];
AXZ tmp3=input[rank*3];
azD(tmp0,tmp1);
azD(tmp2,tmp3);
tmp3=AXZ(tmp3.imag(),-tmp3.real());
input[0]=tmp0+tmp2;
input[rank]=tmp1+tmp3;
input[rank*2]=tmp0-tmp2;
input[rank*3]=tmp1-tmp3;
}
QI void fft_dit_8point(AXZ*input,ARS rank=1)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank];
AXZ tmp2=input[rank*2];
AXZ tmp3=input[rank*3];
AXZ tmp4=input[rank*4];
AXZ tmp5=input[rank*5];
AXZ tmp6=input[rank*6];
AXZ tmp7=input[rank*7];
azD(tmp0,tmp1);
azD(tmp2,tmp3);
azD(tmp4,tmp5);
azD(tmp6,tmp7);
tmp3=AXZ(tmp3.imag(),-tmp3.real());
tmp7=AXZ(tmp7.imag(),-tmp7.real());
azD(tmp0,tmp2);
azD(tmp1,tmp3);
azD(tmp4,tmp6);
azD(tmp5,tmp7);
ZZS AXC ZZD cos_1_8=0.70710678118654752440084436210485;
tmp5=cos_1_8*AXZ(tmp5.imag()+tmp5.real(),tmp5.imag()-tmp5.real());
tmp6=AXZ(tmp6.imag(),-tmp6.real());
tmp7= -cos_1_8*AXZ(tmp7.real()-tmp7.imag(),tmp7.real()+tmp7.imag());
input[0]=tmp0+tmp4;
input[rank]=tmp1+tmp5;
input[rank*2]=tmp2+tmp6;
input[rank*3]=tmp3+tmp7;
input[rank*4]=tmp0-tmp4;
input[rank*5]=tmp1-tmp5;
input[rank*6]=tmp2-tmp6;
input[rank*7]=tmp3-tmp7;
}
QI void fft_dif_4point(AXZ*input,ARS rank=1)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank];
AXZ tmp2=input[rank*2];
AXZ tmp3=input[rank*3];
azD(tmp0,tmp2);
azD(tmp1,tmp3);
tmp3=AXZ(tmp3.imag(),-tmp3.real());
input[0]=tmp0+tmp1;
input[rank]=tmp0-tmp1;
input[rank*2]=tmp2+tmp3;
input[rank*3]=tmp2-tmp3;
}
QI void fft_dif_8point(AXZ*input,ARS rank=1)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank];
AXZ tmp2=input[rank*2];
AXZ tmp3=input[rank*3];
AXZ tmp4=input[rank*4];
AXZ tmp5=input[rank*5];
AXZ tmp6=input[rank*6];
AXZ tmp7=input[rank*7];
azD(tmp0,tmp4);
azD(tmp1,tmp5);
azD(tmp2,tmp6);
azD(tmp3,tmp7);
ZZS AXC ZZD cos_1_8=0.70710678118654752440084436210485;
tmp5=cos_1_8*AXZ(tmp5.imag()+tmp5.real(),tmp5.imag()-tmp5.real());
tmp6=AXZ(tmp6.imag(),-tmp6.real());
tmp7= -cos_1_8*AXZ(tmp7.real()-tmp7.imag(),tmp7.real()+tmp7.imag());
azD(tmp0,tmp2);
azD(tmp1,tmp3);
azD(tmp4,tmp6);
azD(tmp5,tmp7);
tmp3=AXZ(tmp3.imag(),-tmp3.real());
tmp7=AXZ(tmp7.imag(),-tmp7.real());
input[0]=tmp0+tmp1;
input[rank]=tmp0-tmp1;
input[rank*2]=tmp2+tmp3;
input[rank*3]=tmp2-tmp3;
input[rank*4]=tmp4+tmp5;
input[rank*5]=tmp4-tmp5;
input[rank*6]=tmp6+tmp7;
input[rank*7]=tmp6-tmp7;
}
QI void fft_radix2_dit_butterfly(AXZ omega,AXZ*input,ARS rank)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank]*omega;
input[0]=tmp0+tmp1;
input[rank]=tmp0-tmp1;
}
QI void fft_radix2_dif_butterfly(AXZ omega,AXZ*input,ARS rank)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank];
input[0]=tmp0+tmp1;
input[rank]=(tmp0-tmp1)*omega;
}
QI void fft_split_radix_dit_butterfly(AXZ omega,AXZ qz009,
AXZ*input,ARS rank)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank];
AXZ tmp2=input[rank*2]*omega;
AXZ tmp3=input[rank*3]*qz009;
azD(tmp2,tmp3);
tmp3=AXZ(tmp3.imag(),-tmp3.real());
input[0]=tmp0+tmp2;
input[rank]=tmp1+tmp3;
input[rank*2]=tmp0-tmp2;
input[rank*3]=tmp1-tmp3;
}
QI void fft_split_radix_dif_butterfly(AXZ omega,AXZ qz009,
AXZ*input,ARS rank)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank];
AXZ tmp2=input[rank*2];
AXZ tmp3=input[rank*3];
azD(tmp0,tmp2);
azD(tmp1,tmp3);
tmp3=AXZ(tmp3.imag(),-tmp3.real());
input[0]=tmp0;
input[rank]=tmp1;
input[rank*2]=(tmp2+tmp3)*omega;
input[rank*3]=(tmp2-tmp3)*qz009;
}
QI void fft_split_radix_dit_butterfly(az02 omega,az02 qz009,
AXZ*input,ARS rank)
{
az02 tmp0=input;
az02 tmp1=input+rank;
az02 tmp2=az02(input+rank*2)*omega;
az02 tmp3=az02(input+rank*3)*qz009;
azD(tmp2,tmp3);
tmp3=tmp3.mul_neg_i();
(tmp0+tmp2).store(input);
(tmp1+tmp3).store(input+rank);
(tmp0-tmp2).store(input+rank*2);
(tmp1-tmp3).store(input+rank*3);
}
QI void fft_split_radix_dif_butterfly(az02 omega,az02 qz009,
AXZ*input,ARS rank)
{
az02 tmp0=(input);
az02 tmp1=(input+rank);
az02 tmp2=(input+rank*2);
az02 tmp3=(input+rank*3);
azD(tmp0,tmp2);
azD(tmp1,tmp3);
tmp3=tmp3.mul_neg_i();
tmp0.store(input);
tmp1.store(input+rank);
((tmp2+tmp3)*omega).store(input+rank*2);
((tmp2-tmp3)*qz009).store(input+rank*3);
}
QI void fft_radix4_dit_butterfly(AXZ omega,AXZ omega_sqr,AXZ qz009,
AXZ*input,ARS rank)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank]*omega;
AXZ tmp2=input[rank*2]*omega_sqr;
AXZ tmp3=input[rank*3]*qz009;
azD(tmp0,tmp2);
azD(tmp1,tmp3);
tmp3=AXZ(tmp3.imag(),-tmp3.real());
input[0]=tmp0+tmp1;
input[rank]=tmp2+tmp3;
input[rank*2]=tmp0-tmp1;
input[rank*3]=tmp2-tmp3;
}
QI void fft_radix4_dif_butterfly(AXZ omega,AXZ omega_sqr,AXZ qz009,
AXZ*input,ARS rank)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank];
AXZ tmp2=input[rank*2];
AXZ tmp3=input[rank*3];
azD(tmp0,tmp2);
azD(tmp1,tmp3);
tmp3=AXZ(tmp3.imag(),-tmp3.real());
input[0]=tmp0+tmp1;
input[rank]=(tmp2+tmp3)*omega;
input[rank*2]=(tmp0-tmp1)*omega_sqr;
input[rank*3]=(tmp2-tmp3)*qz009;
}
QI void fft_conj(AXZ*input,ARS azE,ZZD div=1)
{
for(ARS i=0;i<azE;i++)
{
input[i]=std::conj(input[i])/div;
}
}
QI void fft_normalize(AXZ*input,ARS azE)
{
ZZD len=qz020<ZZD>(azE);
for(ARS i=0;i<azE;i++)
{
input[i]/=len;
}
}
AXT<ARS LEN>
void azB(AXZ*input)
{
AXC ARS log_len=hint_log2(LEN);
AXC ARS half_len=LEN/2,qz016=LEN/4;
azB<half_len>(input);
azB<qz016>(input+half_len);
azB<qz016>(input+half_len+qz016);
for(ARS i=0;i<qz016;i+=2)
{
auto omega=TABLE.get_omegaX2(log_len,i);
auto qz009=TABLE.get_omega3X2(log_len,i);
fft_split_radix_dit_butterfly(omega,qz009,input+i,qz016);
}
}
AXT<>
void azB<0>(AXZ*input){}
AXT<>
void azB<1>(AXZ*input){}
AXT<>
void azB<2>(AXZ*input)
{
azD(input[0],input[1]);
}
AXT<>
void azB<4>(AXZ*input)
{
fft_dit_4point(input,1);
}
AXT<>
void azB<8>(AXZ*input)
{
fft_dit_8point(input,1);
}
AXT<ARS LEN>
void azC(AXZ*input)
{
AXC ARS log_len=hint_log2(LEN);
AXC ARS half_len=LEN/2,qz016=LEN/4;
for(ARS i=0;i<qz016;i+=2)
{
auto omega=TABLE.get_omegaX2(log_len,i);
auto qz009=TABLE.get_omega3X2(log_len,i);
fft_split_radix_dif_butterfly(omega,qz009,input+i,qz016);
}
azC<half_len>(input);
azC<qz016>(input+half_len);
azC<qz016>(input+half_len+qz016);
}
AXT<>
void azC<0>(AXZ*input){}
AXT<>
void azC<1>(AXZ*input){}
AXT<>
void azC<2>(AXZ*input)
{
azD(input[0],input[1]);
}
AXT<>
void azC<4>(AXZ*input)
{
fft_dif_4point(input,1);
}
AXT<>
void azC<8>(AXZ*input)
{
fft_dif_8point(input,1);
}
AXT<ARS LEN=1>
void fft_dit_template(AXZ*input,ARS azE)
{
if(azE>LEN)
{
fft_dit_template<LEN*2>(input,azE);
ZZR;
}
TABLE.expand(hint_log2(LEN));
azB<LEN>(input);
}
AXT<>
void fft_dit_template<1<<24>(AXZ*input,ARS azE){}
AXT<ARS LEN=1>
void fft_dif_template(AXZ*input,ARS azE)
{
if(azE>LEN)
{
fft_dif_template<LEN*2>(input,azE);
ZZR;
}
TABLE.expand(hint_log2(LEN));
azC<LEN>(input);
}
AXT<>
void fft_dif_template<1<<24>(AXZ*input,ARS azE){}
QI void fft_dit(AXZ*input,ARS azE,bool bit_rev=true)
{
azE=max_2pow(azE);
if(bit_rev)
{
binary_reverse_swap(input,azE);
}
fft_dit_template<1>(input,azE);
}
QI void fft_dif(AXZ*input,ARS azE,bool bit_rev=true)
{
azE=max_2pow(azE);
fft_dif_template<1>(input,azE);
if(bit_rev)
{
binary_reverse_swap(input,azE);
}
}
}
AXT<qz005 BASE,ZZT T>
AXC void save_num_to_ary(T ary[],qz005 num,ARS digit)
{
ARS i=digit;
while(i>0)
{
i--;
ary[i]=num%BASE;
num/=BASE;
}
}
qz005 stoui64(QC std::string::const_iterator&begin,
QC std::string::const_iterator&end,QC UINT_32 base=10)
{
qz005 result=0;
for(auto it=begin;it<end&&it-begin<19;++it)
{
result*=base;
char c=tolower(*it);
qz005 n=0;
if(isalnum(c))
{
if(isalpha(c))
{
n=c-'a'+10;
}
else
{
n=c-'0';
}
}
if(n<base)
{
result+=n;
}
}
ZZR result;
}
qz005 stoui64(QC std::string&str,QC UINT_32 base=10)
{
ZZR stoui64(str.begin(),str.end(),base);
}
std::string ui64to_string(qz005 input,UINT_8 digits)
{
std::string result(digits,'0');
for(UINT_8 i=0;i<digits;i++)
{
result[digits-i-1]=qz020<char>(input%10+'0');
input/=10;
}
ZZR result;
}
AXT<ZZT T=UINT_32,ZZT azA=UINT_32>
class qz010
{
private:
T*qz002=qz004;
azA sign_n_len=0;
azA size=0;
public:
~qz010()
{
if(qz002!=qz004)
{
delete[]qz002;
qz002=qz004;
}
}
qz010()
{
qz002=qz004;
}
qz010(azA ele_size)
{
if(ele_size>0)
{
resize(ele_size);
}
}
qz010(azA ele_size,T ele)
{
if(ele_size>0)
{
resize(ele_size);
az03(ele_size);
fill_element(ele,ele_size);
}
}
qz010(QC T*ary,azA len)
{
if(ary==qz004)
{
throw("Can't copy from nullptr\n");
}
if(len>0)
{
resize(len);
az03(len);
ary_copy(qz002,ary,len);
}
}
qz010(QC qz010&input)
{
if(input.qz002!=qz004)
{
if(qz002!=qz004)
{
delete[]qz002;
}
qz002=qz004;
ARS len=input.length();
resize(len);
az03(len);
change_sign(input.sign());
ary_copy(qz002,input.qz002,len);
}
}
qz010(qz010&&input)
{
if(input.qz002!=qz004)
{
size=input.size;
az03(input.length());
change_sign(input.sign());
if(qz002!=qz004)
{
delete[]qz002;
}
qz002=input.qz002;
input.qz002=qz004;
}
}
qz010&az04=(QC qz010&input)
{
if(this!= &input)
{
if(qz002!=qz004)
{
delete[]qz002;
}
qz002=qz004;
ARS len=input.length();
resize(len);
az03(len);
change_sign(input.sign());
ary_copy(qz002,input.qz002,len);
}
ZZR*this;
}
qz010&az04=(qz010&&input)
{
if(this!= &input)
{
size=input.size;
az03(input.length());
change_sign(input.sign());
if(qz002!=qz004)
{
delete[]qz002;
}
qz002=input.qz002;
input.qz002=qz004;
}
ZZR*this;
}
T&az04[](azA index)QC
{
ZZR qz002[index];
}
T*data()QC
{
ZZR qz002;
}
ZZS azA size_generator(azA new_size)
{
AXC azA qz011=arZ(azA)*8;
AXC azA SIZE_80=(1ull<<(qz011-1));
AXC azA LEN_MAX=SIZE_80-1;
new_size=std::min<azA>(new_size,LEN_MAX);
if(new_size<=2)
{
ZZR 2;
}
else if(new_size<=4)
{
ZZR 4;
}
azA size1=min_2pow(new_size);
azA size2=size1/2;
size2=size2+size2/2;
if(new_size<=size2)
{
ZZR size2;
}
else
{
ZZR size1;
}
}
azA length()QC
{
AXC azA qz011=arZ(azA)*8;
AXC azA SIZE_80=(1ull<<(qz011-1));
AXC azA LEN_MAX=SIZE_80-1;
ZZR sign_n_len&LEN_MAX;
}
bool sign()QC
{
AXC azA qz011=arZ(azA)*8;
AXC azA SIZE_80=(1ull<<(qz011-1));
ZZR(SIZE_80&sign_n_len)!=0;
}
AXC void resize(azA new_size,azA(size_func)(azA)=size_generator)
{
new_size=size_func(new_size);
if(qz002==qz004)
{
size=new_size;
qz002=new T[size];
az03(0);
}
else if(size!=new_size)
{
size=new_size;
qz002=ary_realloc(qz002,size);
az03(length());
}
}
void az03(azA new_length)
{
AXC azA qz011=arZ(azA)*8;
AXC azA SIZE_80=(1ull<<(qz011-1));
AXC azA LEN_MAX=SIZE_80-1;
if(new_length>LEN_MAX)
{
throw("Length too long\n");
}
new_length=std::min(new_length,size);
bool sign_tmp=sign();
sign_n_len=new_length;
change_sign(sign_tmp);
}
void change_sign(bool is_sign)
{
AXC azA qz011=arZ(azA)*8;
AXC azA SIZE_80=(1ull<<(qz011-1));
AXC azA LEN_MAX=SIZE_80-1;
if((!is_sign)||length()==0)
{
sign_n_len=sign_n_len&LEN_MAX;
}
else
{
sign_n_len=sign_n_len|SIZE_80;
}
}
azA qz003()
{
if(qz002==qz004)
{
ZZR 0;
}
azA t_len=length();
while(t_len>0&&qz002[t_len-1]==0)
{
t_len--;
}
az03(t_len);
ZZR length();
}
void fill_element(T ele,azA count,azA begin=0)
{
if(begin>=size||qz002==qz004)
{
ZZR;
}
if(begin+count>=size)
{
count=size-begin;
}
std::fill(qz002+begin,qz002+begin+count,ele);
}
};
}
namespace hint_arithm
{
using namespace hint;
using azA=UINT_32;
AXT<ZZT T>
using hintvector=qz010<T,azA>;
AXT<ZZT T>
AXC ARS qz008(QC T&ary,ARS len)
{
while(len>0&&ary[len-1]==0)
{
len--;
}
ZZR len;
}
AXT<ZZT T>
AXC INT_32 abs_compare(QC T ary1[],QC T ary2[],ARS len1,ARS len2)
{
len1=qz008(ary1,len1);
len2=qz008(ary2,len2);
if(len1!=len2)
{
ZZR len1>len2?1: -1;
}
if(ary1==ary2)
{
ZZR 0;
}
while(len1>0)
{
len1--;
T num1=ary1[len1],num2=ary2[len1];
if(num1!=num2)
{
ZZR num1>num2?1: -1;
}
}
ZZR 0;
}
AXT<qz005 BASE,bool is_carry=true,ZZT T>
AXC void abs_mul_num(QC T in[],T num,T out[],ARS len)
{
len=qz008(in,len);
num%=BASE;
qz005 prod=0;
if(num==1)
{
ary_copy(out,in,len);
}
else
{
for(ARS i=0;i<len;i++)
{
prod+=qz020<qz005>(in[i])*num;
std::tie(prod,out[i])=div_mod<qz005>(prod,BASE);
}
}
if(is_carry)
{
out[len]=prod;
}
}
AXT<qz005 BASE,ZZT T>
AXC INT_64 abs_div_num(QC T in[],T num,T out[],ARS len)
{
ARS pos=qz008(in,len);
num%=BASE;
if(num==1)
{
ary_copy(out,in,len);
ZZR 0;
}
qz005 last_rem=0;
while(pos>0)
{
pos--;
last_rem=last_rem*BASE+in[pos];
std::tie(out[pos],last_rem)=div_mod<qz005>(last_rem,num);
}
ZZR last_rem;
}
AXT<INT_64 BASE,bool is_carry=true,ZZT T>
AXC void abs_add(QC T in1[],QC T in2[],T out[],
ARS len1,ARS len2)
{
if(len1<len2)
{
std::swap(in1,in2);
std::swap(len1,len2);
}
ARS pos=0;
qz005 carry=0;
while(pos<len2)
{
carry+=(in1[pos]+in2[pos]);
out[pos]=carry<BASE?carry:carry-BASE;
carry=carry<BASE?0:1;
pos++;
}
while(pos<len1&&carry>0)
{
carry+=in1[pos];
out[pos]=carry<BASE?carry:carry-BASE;
carry=carry<BASE?0:1;
pos++;
}
ary_copy(out+pos,in1+pos,len1-pos);
if(is_carry)
{
out[len1]=carry%BASE;
}
}
AXT<INT_64 BASE,ZZT T>
AXC void abs_sub(QC T in1[],QC T in2[],T out[],
ARS len1,ARS len2)
{
if(len1<len2)
{
ZZR;
}
ARS pos=0;
INT_64 borrow=0;
while(pos<len2)
{
borrow+=(qz020<INT_64>(in1[pos])-in2[pos]);
out[pos]=borrow<0?borrow+BASE:borrow;
;
borrow=borrow<0?-1:0;
pos++;
}
while(pos<len1&&borrow<0)
{
borrow+=in1[pos];
out[pos]=borrow<0?borrow+BASE:borrow;
borrow=borrow<0?-1:0;
pos++;
}
ary_copy(out+pos,in1+pos,len1-pos);
}
AXT<qz005 BASE,ZZT T>
void fft_mul_old(QC T in1[],QC T in2[],T out[],
ARS len1,ARS len2)
{
using namespace hint_transform;
if(len1==0||len2==0||in1==qz004||in2==qz004)
{
ZZR;
}
QC ARS conv_res_len=len1+len2-1;
QC ARS azE=min_2pow(conv_res_len);
ZZS AXZ*fft_buf=qz004;ZZS ARS fft_cap=0;
if(fft_cap<azE){free(fft_buf);fft_buf=(AXZ*)malloc(azE*arZ(AXZ));fft_cap=azE;}
AXZ*fft_ary=fft_buf;
{ARS mnz=len1<len2?len1:len2;
memset((char*)(fft_ary+mnz),0,(azE-mnz)*arZ(AXZ));}
com_ary_combine_copy(fft_ary,in1,len1,in2,len2);
fft_dif(fft_ary,azE,false);
ZZD inv= -1/(2.0*azE);
for(ARS i=0;i<azE;i++)
{
AXZ tmp=fft_ary[i];
fft_ary[i]=std::conj(tmp*tmp*inv);
}
fft_dit(fft_ary,azE,false);
hint::qz005 carry=0;
for(ARS i=0;i<conv_res_len;i++)
{
carry+=qz020<hint::qz005>(fft_ary[i].imag()+0.5);
std::tie(carry,out[i])=div_mod<qz005>(carry,BASE);
}
out[conv_res_len]=carry%BASE;
}
AXT<ZZT T>
ZZS QI void qz017(ZZD*dst,QC T*src,ARS n)
{
ARS i=0;
if AXC(arZ(T)==4)
{
for(;i+8<=n;i+=8)
{
arV v=qz007((QC arV*)(QC void*)(src+i));
_mm256_storeu_pd(dst+i,_mm256_cvtepi32_pd(_mm256_castsi256_si128(v)));
_mm256_storeu_pd(dst+i+4,_mm256_cvtepi32_pd(_mm256_extracti128_si256(v,1)));
}
}
for(;i<n;++i)dst[i]=(ZZD)src[i];
}
// Independent radix10000 coefficient folding and eight-lane carry lookahead.
ZZS QI __m128i carry550fold(arV raw,__m128i&prev1,__m128i&prev2,__m128i&prev3){
QC ZZV bias=_mm256_set1_pd(4503599627370496.0),base=_mm256_set1_pd(10000.0),inv=_mm256_set1_pd(0.0001);
ZZV x=_mm256_sub_pd(_mm256_castsi256_pd(_mm256_or_si256(raw,_mm256_castpd_si256(bias))),bias);
ZZV q1=_mm256_floor_pd(qz023(x,inv));
ZZV q2=_mm256_floor_pd(qz023(q1,inv));
ZZV q3=_mm256_floor_pd(qz023(q2,inv));
__m128i r0=_mm256_cvttpd_epi32(_mm256_sub_pd(x,qz023(q1,base)));
__m128i r1=_mm256_cvttpd_epi32(_mm256_sub_pd(q1,qz023(q2,base)));
__m128i r2=_mm256_cvttpd_epi32(_mm256_sub_pd(q2,qz023(q3,base)));
__m128i r3=_mm256_cvttpd_epi32(q3);
__m128i sum=_mm_add_epi32(r0,_mm_alignr_epi8(r1,prev1,12));
sum=_mm_add_epi32(sum,_mm_alignr_epi8(r2,prev2,8));
sum=_mm_add_epi32(sum,_mm_alignr_epi8(r3,prev3,4));
prev1=r1;prev2=r2;prev3=r3;ZZR sum;
}
ZZS void carry550(QC QO long long*c,QO*out,ARS count){
__m128i p1=_mm_setzero_si128(),p2=p1,p3=p1;
for(ARS i=0;i<=count;i+=4){
arV mask=_mm256_set_epi64x(i+3<count?-1LL:0,i+2<count?-1LL:0,i+1<count?-1LL:0,i<count?-1LL:0);
arV raw=_mm256_maskload_epi64((QC long long*)(c+i),mask);
__m128i sum=carry550fold(raw,p1,p2,p3);
if(i+4<=count+1)_mm_storeu_si128((__m128i*)(out+i),sum);
else{QO tail[4];_mm_storeu_si128((__m128i*)tail,sum);__builtin_memcpy(out+i,tail,(count+1-i)*4);}
}
QC arV zero=_mm256_setzero_si256(),base=az06(10000),one=az06(1),shifts=_mm256_setr_epi32(0,1,2,3,4,5,6,7),indices=_mm256_setr_epi32(0,0,1,2,3,4,5,6);
QO carry=0;ARS i=0;
for(;i+8<=count+1;i+=8){
arV s=qz007((QC arV*)(out+i));
arV q=_mm256_sub_epi32(zero,qz026(qz026(_mm256_cmpgt_epi32(s,az06(9999)),_mm256_cmpgt_epi32(s,az06(19999))),_mm256_cmpgt_epi32(s,az06(29999))));
arV prior=_mm256_blend_epi32(_mm256_permutevar8x32_epi32(q,indices),az06(carry),1);
arV y=qz026(_mm256_sub_epi32(s,_mm256_mullo_epi32(q,base)),prior);
QO e=(QO)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(y,az06(9999))));
QO p=(QO)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpeq_epi32(y,az06(9999))));
e|=p&(e<<1);p&=p<<1;e|=p&(e<<2);p&=p<<2;e|=p&(e<<4);e&=255;
arV bits=_mm256_and_si256(_mm256_srlv_epi32(az06(e),shifts),one);
arV before=_mm256_and_si256(_mm256_srlv_epi32(az06(e<<1),shifts),one);
y=_mm256_sub_epi32(qz026(y,before),_mm256_mullo_epi32(bits,base));
_mm256_storeu_si256((arV*)(out+i),y);carry=(QO)_mm256_extract_epi32(q,7)+(e>>7);
}
for(;i<=count;i++){QO x=out[i]+carry;out[i]=x%10000;carry=x/10000;}
}
AXT<qz005 BASE,ZZT T>
void fft_mul(QC T in1[],QC T in2[],T out[],ARS len1,ARS len2){
if(!len1||!len2||!in1||!in2)ZZR;
QC ARS conv=len1+len2-1;
if AXC(BASE==10000&&arZ(T)==4){if(len1*len2<=65536){
QC T*aa=in1,*bb=in2;ARS na=len1,nb=len2;if(na>nb){std::swap(aa,bb);std::swap(na,nb);}
ZZS ARU*bp=qz004,*ap=qz004,*tmp=qz004;ZZS ARS bc=0,ac=0,tc=0;
QC ARS need=nb+34,an=(na+1)/2;if(bc<need){free(bp);bp=(ARU*)malloc(need*4);bc=need;}if(ac<an){free(ap);ap=(ARU*)malloc(an*4);ac=an;}
memset(bp,0,16*4);ARU*packed=bp+16;for(ARS k=0;k<nb;k++)packed[k]=bb[k]|(k?bb[k-1]<<16:0);packed[nb]=bb[nb-1]<<16;memset(packed+nb+1,0,17*4);
for(ARS k=0;k<an;k++)ap[k]=aa[2*k]|(2*k+1<na?aa[2*k+1]<<16:0);
uintptr_t ob=(uintptr_t)out,oe=(uintptr_t)(out+conv+1),ab=(uintptr_t)in1,ae=(uintptr_t)(in1+len1),bbeg=(uintptr_t)in2,be=(uintptr_t)(in2+len2);
QC bool overlap=(ob<ae&&oe>ab)||(ob<be&&oe>bbeg);T*o=out;if(overlap){if(tc<conv+1){free(tmp);tmp=(ARU*)malloc((conv+1)*4);tc=conv+1;}o=(T*)tmp;}
ARL carry=0;ARS m=0;
for(;m+16<=conv;m+=16){
ARL sums[16]={};QC ARS lo=m>=nb-1?m-(nb-1):0,hi=std::min(na-1,m+15);
for(ARS i0=lo&~ARS(1);i0<=hi;i0+=40){
QC ARS end=std::min(hi+1,i0+40);arV s0=_mm256_setzero_si256(),s1=s0;
for(ARS i=i0;i<end;i+=2){arV av=az06(ap[i/2]);QC ARU*p=packed+ptrdiff_t(m)-ptrdiff_t(i);
s0=qz026(s0,_mm256_madd_epi16(av,qz007((QC arV*)p)));
s1=qz026(s1,_mm256_madd_epi16(av,qz007((QC arV*)(p+8))));}
_mm256_storeu_si256((arV*)sums,_mm256_add_epi64(qz007((QC arV*)sums),_mm256_cvtepu32_epi64(_mm256_castsi256_si128(s0))));
_mm256_storeu_si256((arV*)(sums+4),_mm256_add_epi64(qz007((QC arV*)(sums+4)),_mm256_cvtepu32_epi64(_mm256_extracti128_si256(s0,1))));
_mm256_storeu_si256((arV*)(sums+8),_mm256_add_epi64(qz007((QC arV*)(sums+8)),_mm256_cvtepu32_epi64(_mm256_castsi256_si128(s1))));
_mm256_storeu_si256((arV*)(sums+12),_mm256_add_epi64(qz007((QC arV*)(sums+12)),_mm256_cvtepu32_epi64(_mm256_extracti128_si256(s1,1))));
}
for(QO j=0;j<16;j++){ARL v=sums[j]+carry;o[m+j]=v%10000;carry=v/10000;}
}
for(;m<conv;m++){ARL sum=0;QC ARS lo=m>=nb-1?m-(nb-1):0,hi=std::min(na-1,m);for(ARS i=lo;i<=hi;i++)sum+=(ARL)aa[i]*bb[m-i];sum+=carry;o[m]=sum%10000;carry=sum/10000;}
o[conv]=carry;if(overlap)memcpy(out,o,(conv+1)*4);ZZR;
}}
if(conv<512){fft_mul_old<BASE>(in1,in2,out,len1,len2);ZZR;}
ARS n=qz014::int_ceil2(conv);
ZZS ZZD*g_abuf=qz004,*g_bbuf=qz004;ZZS ARS g_acap=0,g_bcap=0;
if(g_acap<n){_mm_free(g_abuf);g_abuf=(ZZD*)_mm_malloc(n*arZ(ZZD),64);g_acap=n;}
ZZD*a=g_abuf;
memset(a+len1,0,(n-len1)*arZ(ZZD));
qz017(a,in1,len1);
if(in1==in2&&len1==len2){
qz014::transform::fft::FFTAVX::difRecLong<true>(a,n);
qz014::transform::fft::qz019(a,a,n);
qz014::transform::fft::FFTAVX::iditRecLong<true,true>(a,n);
}else{
if(g_bcap<n){_mm_free(g_bbuf);g_bbuf=(ZZD*)_mm_malloc(n*arZ(ZZD),64);g_bcap=n;}
ZZD*b=g_bbuf;memset(b+len2,0,(n-len2)*arZ(ZZD));
qz017(b,in2,len2);
qz014::transform::fft::real_conv_avx<true>(a,b,n);
}
QC ARL*coeff=(QC ARL*)a;if AXC(BASE==10000){if(std::min(len1,len2)<=40000000){carry550((QC QO long long*)coeff,(QO*)out,conv);ZZR;}}qz005 carry=0;
for(ARS i=0;i<conv;++i){carry+=coeff[i];out[i]=carry%BASE;carry/=BASE;}
out[conv]=carry%BASE;
}
AXT<qz005 BASE,ZZT T>
AXC T divisor_normalize(QC T in[],T out[],ARS len)
{
if(in==out)
{
throw("In can't be same as out\n");
}
T multiplier=1;
if(len==1)
{
multiplier=(BASE-1)/in[0];
out[0]=in[0]*multiplier;
}
else if(in[len-1]>=(BASE/2))
{
ary_copy(out,in,len);
}
else
{
multiplier=(BASE-1)*BASE/(BASE*in[len-1]+in[len-2]);
abs_mul_num<BASE,false>(in,multiplier,out,len);
if(out[len-1]<(BASE/2))
{
multiplier++;
abs_add<BASE,false>(out,in,out,len,len);
}
}
ZZR multiplier;
}
AXT<qz005 BASE,ZZT T>
void abs_long_div(T az05[],QC T qz012[],T quot[],
ARS len1,ARS len2)
{
len1=qz008(az05,len1);
len2=qz008(qz012,len2);
if(qz012==qz004||len2==0)
{
throw("Can't divide by zero\n");
}
if(az05==qz004||len1==0)
{
ZZR;
}
if(abs_compare(az05,qz012,len1,len2)<0)
{
ZZR;
}
if(len2==1)
{
T rem=abs_div_num<BASE>(az05,qz012[0],quot,len1);
az05[0]=rem;
ZZR;
}
if(qz012[len2-1]<(BASE/2))
{
throw("Can't call this proc before normalize the divisor\n");
}
quot[len1-len2]=0;
QC qz005 divisor_2digits=BASE*qz012[len2-1]+qz012[len2-2];
hintvector<T>sub(len2+1);
while(abs_compare(az05,qz012,len1,len2)>=0)
{
sub.az03(len2+1);
qz005 dividend_2digits=az05[len1-1]*BASE+az05[len1-2];
T qz022=0;
ARS shift=len1-len2;
if(dividend_2digits>divisor_2digits)
{
qz022=dividend_2digits/divisor_2digits;
abs_mul_num<BASE>(qz012,qz022,sub.data(),len2);
sub.qz003();
ARS sub_len=sub.length();
if(abs_compare(az05+shift,sub.data(),len1-shift,sub_len)<0)
{
qz022--;
abs_sub<BASE>(sub.data(),qz012,sub.data(),sub_len,len2);
}
}
else if(dividend_2digits==divisor_2digits)
{
if(abs_compare(az05+shift,qz012,len1-shift,len2)<0)
{
qz022=BASE-1;
shift--;
abs_mul_num<BASE>(qz012,qz022,sub.data(),len2);
}
else
{
qz022=1;
ary_copy(sub.data(),qz012,len2);
sub.qz003();
}
}
else
{
qz022=dividend_2digits/(divisor_2digits/BASE);
if(qz022>=BASE)
{
qz022=BASE-1;
}
shift--;
abs_mul_num<BASE>(qz012,qz022,sub.data(),len2);
sub.qz003();
ARS sub_len=sub.length();
if(abs_compare(az05+shift,sub.data(),len1-shift,sub_len)<0)
{
qz022--;
abs_sub<BASE>(sub.data(),qz012,sub.data(),sub_len,len2);
if(abs_compare(az05+shift,sub.data(),len1-shift,sub_len)<0)
{
qz022--;
abs_sub<BASE>(sub.data(),qz012,sub.data(),sub_len,len2);
}
}
}
abs_sub<BASE>(az05+shift,sub.data(),az05+shift,len1-shift,sub.length());
len1=qz008(az05,len1);
quot[shift]=qz022;
}
}
AXT<qz005 BASE,ZZT T>
void abs_rec_div(T az05[],T qz012[],hintvector<T> ",
ARS len1,ARS len2)
{
len1=qz008(az05,len1);
len2=qz008(qz012,len2);
if(qz012==qz004||len2==0)
{
throw("Can't divide by zero\n");
}
if(az05==qz004||len1==0)
{
ZZR;
}
if(abs_compare(az05,qz012,len1,len2)<0)
{
ZZR;
}
if(qz012[len2-1]<(BASE/2))
{
throw("Can't call this proc before normalize the divisor\n");
}
ARS quot_len=len1-len2+1;
quot.az03(quot_len);
AXC ARS LONG_DIV_THRESHOLD=50;
if(len2<=LONG_DIV_THRESHOLD)
{
abs_long_div<BASE>(az05,qz012,quot.data(),len1,len2);
}
else if(len1>=len2*2||len1>((len2+1)/2)*3)
{
ARS qz018=(len1+3)/4;
ARS quot_tmp_len=qz018*3-len2+2;
hintvector<T>quot_tmp(quot_tmp_len,0);
abs_rec_div<BASE>(az05+qz018,qz012,quot_tmp,len1-qz018,len2);
quot_tmp_len=quot_tmp.qz003();
ARS dividend_len=qz008(az05,len1);
abs_rec_div<BASE>(az05,qz012,quot,dividend_len,len2);
quot.az03(quot_len);
quot_len=quot.qz003();
abs_add<BASE>(quot.data()+qz018,quot_tmp.data(),quot.data()+qz018,quot_len-qz018,quot_tmp_len);
quot.az03(len1-len2+1);
}
else
{
ARS qz018=len2/2;
abs_rec_div<BASE>(az05+qz018,qz012+qz018,quot,len1-qz018,len2-qz018);
AXC T ONE[1]={1};
quot_len=quot.qz003();
hintvector<T>prod(qz018+quot_len,0);
fft_mul<BASE>(qz012,quot.data(),prod.data(),qz018,quot_len);
ARS prod_len=prod.qz003();
len1=qz008(az05,len1);
while(abs_compare(prod.data(),az05,prod_len,len1)>0)
{
abs_sub<BASE>(quot.data(),ONE,quot.data(),quot_len,1);
abs_sub<BASE>(prod.data(),qz012,prod.data(),prod_len,qz018);
abs_add<BASE>(az05+qz018,qz012+qz018,az05+qz018,len1-qz018,len2-qz018);
quot_len=quot.qz003();
prod_len=prod.qz003();
len1=qz008(az05,std::max(len1,len2)+1);
}
abs_sub<BASE>(az05,prod.data(),az05,len1,prod_len);
}
}
AXT<qz005 BASE,ZZT T>
hintvector<T>abs_div(QC T az05[],T qz012[],hintvector<T> ",
ARS len1,ARS len2,bool ret_rem=true)
{
hintvector<T>normalized_divisor(len2);
normalized_divisor.az03(len2);
hintvector<T>qz006(len1+1);
qz006.az03(len1+1);
T*divisor_ptr=normalized_divisor.data();
T*dividend_ptr=qz006.data();
T multiplier=divisor_normalize<BASE>(qz012,divisor_ptr,len2);
abs_mul_num<BASE>(az05,multiplier,dividend_ptr,len1);
len1=qz006.qz003();
quot=hintvector<T>(len1-len2+2,0);
if((!ret_rem)&&(len1+2<len2*2))
{
ARS shift=len2*2-len1-2;
abs_rec_div<BASE>(dividend_ptr+shift,divisor_ptr+shift,quot,len1-shift,len2-shift);
quot.qz003();
ZZR qz006;
}
abs_rec_div<BASE>(dividend_ptr,divisor_ptr,quot,len1,len2);
quot.qz003();
if(ret_rem)
{
len1=qz006.qz003();
abs_div_num<BASE>(dividend_ptr,multiplier,dividend_ptr,len1);
qz006.qz003();
}
ZZR qz006;
}}
#include <vector>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <x86intrin.h>
// adapted from Duck public19388 and existing1005e7 reference; no linked library.
struct LP648{arI arS void*h[24]={};arS void*get(std::arY b){std::arY w=(b+15)/16;if(!w)w=1;int c=w<=1?0:64-__builtin_clzll(w-1);if(c>23)arR::az04 new(w*16);void*p=h[c];if(p)h[c]=*(void**)p;else p=::az04 new(((std::arY)1<<c)*16);arR p;}arS void put(void*p,std::arY b){std::arY w=(b+15)/16;if(!w)w=1;int c=w<=1?0:64-__builtin_clzll(w-1);if(c>23){::az04 delete(p);arR;}*(void**)p=h[c];h[c]=p;}};
AXT<class T>struct NoInitAlloc{
using value_type=T;
NoInitAlloc()arN=default;
AXT<class U>NoInitAlloc(QC NoInitAlloc<U>&)arN{}
T*allocate(std::ARS n){ZZR qz020<T*>(LP648::get(n*arZ(T)));}
void deallocate(T*p,std::ARS n)arN{LP648::put(p,n*arZ(T));}
AXT<class U>void construct(U*p){::new(qz020<void*>(p))U;}
AXT<class U,class...A>void construct(U*p,A&&...a){::new(qz020<void*>(p))U(std::forward<A>(a)...);}
AXT<class U>void destroy(U*p){p->~U();}
bool az04==(QC NoInitAlloc&)QC arN{ZZR true;}
bool az04!=(QC NoInitAlloc&)QC arN{ZZR false;}
};
namespace e_compute{
#include <cstdint>
__attribute__((always_inline))ZZS QI ZZW iv603dm(ZZW x,QY&remainder){
arK QY D=10000000000000000ULL;
arK ZZW M=(~(ZZW)0)/D;
QC QY al=(QY)x,ah=(QY)(x>>64),bl=(QY)M,bh=(QY)(M>>64);
QC ZZW p00=(ZZW)al*bl,p01=(ZZW)al*bh,p10=(ZZW)ah*bl,p11=(ZZW)ah*bh;
QC ZZW mid=(p00>>64)+(QY)p01+(QY)p10;
ZZW q=p11+(p01>>64)+(p10>>64)+(mid>>64);
QY r=(QY)(x-q*D);
if(r>=D){r-=D;++q;}remainder=r;ZZR q;
}
struct Big{
std::vector<ARU,NoInitAlloc<ARU>>v;bool neg=false;
Big()=default;
Big(ARL a){ARU d[5];QO n=0;while(a){d[n++]=a%10000;a/=10000;}v.assign(d,d+n);}
ZZS Big wide(ARW a){
if(!(a>>64))ZZR Big((ARL)a);
ARU d[10];QO n=0;
while(a>UINT64_MAX){QY part;a=iv603dm(a,part);
QY up=part/100000000ULL,low=part-up*100000000ULL;
d[n++]=low%10000;d[n++]=low/10000;d[n++]=up%10000;d[n++]=up/10000;}
ARL tail=(ARL)a;while(tail){d[n++]=tail%10000;tail/=10000;}
Big x;x.v.assign(d,d+n);ZZR x;
}
bool zero()QC{ZZR v.empty();}
void trim(){while(!v.empty()&&!v.back())v.pop_back();if(v.empty())neg=false;}
int cmpabs(QC Big&b)QC{if(v.size()!=b.v.size())ZZR v.size()<b.v.size()?-1:1;for(ARS i=v.size();i--;)if(v[i]!=b.v[i])ZZR v[i]<b.v[i]?-1:1;ZZR 0;}
Big az04-()QC{Big r=*this;if(!zero())r.neg=!neg;ZZR r;}
Big az04+(QC Big&b)QC&{
if(zero())ZZR b;if(b.zero())ZZR*this;
if(neg!=b.neg){int c=cmpabs(b);if(!c)ZZR Big();QC Big&a=c>0?*this:b;QC Big&bb=c>0?b:*this;Big r;r.neg=a.neg;r.v.resize(a.v.size());int borrow=0;ARS i=0;for(;i<bb.v.size();++i){int q=int(a.v[i])-int(bb.v[i])-borrow;borrow=q<0;r.v[i]=q+(borrow?10000:0);}for(;i<a.v.size();++i){int q=int(a.v[i])-borrow;borrow=q<0;r.v[i]=q+(borrow?10000:0);}r.trim();ZZR r;}
Big r;r.neg=neg;r.v.resize(std::max(v.size(),b.v.size())+1);QO carry=0;for(ARS i=0;i+1<r.v.size();++i){QO q=carry+(i<v.size()?v[i]:0)+(i<b.v.size()?b.v[i]:0);carry=q>=10000;r.v[i]=q-(carry?10000:0);}r.v.back()=carry;r.trim();ZZR r;
}
Big az04+(QC Big&b)&&{
if(neg!=b.neg)ZZR qz020<QC Big&>(*this)+b;
if(b.zero())ZZR std::move(*this);
if(zero())ZZR b;
ARS n=std::max(v.size(),b.v.size());v.resize(n,0);
QO carry=0;ARS i=0;
for(;i<b.v.size();++i){QO q=v[i]+b.v[i]+carry;carry=q>=10000;v[i]=q-(carry?10000:0);}
while(carry&&i<n){QO q=v[i]+carry;carry=q>=10000;v[i]=q-(carry?10000:0);++i;}
if(carry)v.push_back(carry);
ZZR std::move(*this);
}
Big az04-(QC Big&b)QC{ZZR*this+(-b);}
Big mulnum(ARL m)QC{if(zero()||!m)ZZR Big();if(m<=UINT64_MAX/10000){Big r;r.neg=neg;r.v.resize(v.size());ARL carry=0;for(ARS i=0;i<v.size();++i){carry+=(ARL)v[i]*m;r.v[i]=carry%10000;carry/=10000;}while(carry){r.v.push_back(carry%10000);carry/=10000;}ZZR r;}Big r;r.neg=neg;r.v.resize(v.size());ARW carry=0;for(ARS i=0;i<v.size();++i){carry+=(ARW)v[i]*m;r.v[i]=(ARU)(carry%10000);carry/=10000;}while(carry){r.v.push_back(carry%10000);carry/=10000;}ZZR r;}
Big divnum(ARU d)QC{Big r;r.neg=neg;r.v.resize(v.size());ARL rem=0;for(ARS i=v.size();i--;){rem=rem*10000+v[i];r.v[i]=rem/d;rem%=d;}r.trim();ZZR r;}
Big az04*(QC Big&b)QC{
if(zero()||b.zero())ZZR Big();if(v.size()==1){Big r=b.mulnum(v[0]);r.neg=neg!=b.neg;ZZR r;}if(b.v.size()==1){Big r=mulnum(b.v[0]);r.neg=neg!=b.neg;ZZR r;}
Big r;r.neg=neg!=b.neg;r.v.resize(v.size()+b.v.size());
if(v.size()*b.v.size()<=1024){std::memset(r.v.data(),0,r.v.size()*arZ(ARU));
QC ARU*aa=v.data(),*bb=b.v.data();ARU*cc=r.v.data();
for(ARS i=0;i<v.size();++i)for(ARS j=0;j<b.v.size();++j)cc[i+j]+=aa[i]*bb[j];
ARU carry=0;for(ARS i=0;i<r.v.size();++i){ARU x=cc[i]+carry;cc[i]=x%10000;carry=x/10000;}
}
else hint_arithm::fft_mul<10000>(v.data(),b.v.data(),r.v.data(),v.size(),b.v.size());
r.trim();ZZR r;
}
ZZS Big negative_one(){Big x(1);x.neg=true;ZZR x;}
Big az04/(QC Big&b)QC{
assert(!b.zero());if(cmpabs(b)<0)ZZR Big();if(b.v.size()==1){Big r=divnum(b.v[0]);r.neg=neg!=b.neg;ZZR r;}
hint::qz010<ARU>q;hint_arithm::abs_div<10000>(v.data(),const_cast<ARU*>(b.v.data()),q,v.size(),b.v.size(),false);Big r;r.neg=neg!=b.neg;r.v.assign(q.data(),q.data()+q.length());r.trim();ZZR r;
}
Big shift(ARS limbs)QC{if(zero())ZZR Big();Big r;r.neg=neg;r.v.resize(limbs+v.size(),0);std::copy(v.begin(),v.end(),r.v.begin()+limbs);ZZR r;}
Big high(ARS cut)QC{if(cut>=v.size())ZZR Big();Big r;r.neg=neg;r.v.assign(v.begin()+cut,v.end());ZZR r;}
};
ZZS bool MP(QC Big&A,QC Big&B,QC Big&C,Big&o1,Big&o2);
struct QT{Big q,t;};
struct iv586w{ARL x[4];};
ZZS void iv586step(iv586w&w,ARL k,ARL carry){for(QO j=0;j<4;j++){ARW q=(ARW)w.x[j]*k+carry;w.x[j]=q;carry=q>>64;}}
ZZS Big iv586big(iv586w w){Big r;r.v.resize(20);ARS used=0;int top=3;QC ARL D=10000000000000000ULL;
while(top>=0){while(top>=0&&!w.x[top])--top;if(top<0)break;ARL rem=0;QY first=w.x[top];if(first<D){w.x[top]=0;rem=first;}else{w.x[top]=first/D;rem=first%D;}for(int i=top-1;i>=0;--i){ZZW cur=((ZZW)rem<<64)|w.x[i];w.x[i]=(QY)iv603dm(cur,rem);}for(QO i=0;i<4;i++){r.v[used++]=rem%10000;rem/=10000;}}
r.v.resize(used);r.trim();ZZR r;}
ZZS QT binary_split(QO a,QO b){
QC QO size=b-a;if((size<=9&&b<=16384u)||(size<=8&&b<=65536u)||(size<=7&&b<=262144u)){ARW q=1,t=0;QO k=a;for(;b-k>=3;k+=3){ARL last=k+2,triple=ARL(k)*(k+1)*last;q*=triple;t=t*triple+ARL(k+1)*last+last+1;}for(;b-k>=2;k+=2){ARL pair=ARL(k)*(k+1);q*=pair;t=t*pair+k+2;}if(k<b){q*=k;t=t*k+1;}ZZR{Big::wide(q),Big::wide(t)};}if(size>6&&((size<=18&&b<=16384u)||(size<=16&&b<=65536u)||(size<=15&&b<=131072u)||(size<=14&&b<=262144u)||(size<=13&&b<=524288u)||(size<=12&&b<=2097152u))){arW f0=arW(a)*(a+1)*(a+2),v0=arW(a+1)*(a+2)+a+3,f1=arW(a+3)*(a+4)*(a+5),v1=arW(a+4)*(a+5)+a+6;arB q0=(arB)f0*f1,t0=(arB)v0*f1+v1;unsigned k=a+6,take=std::min(3u,b-k);uint64_t ff=1,vv=0;if(take==3){ff=uint64_t(k)*(k+1)*(k+2);vv=uint64_t(k+1)*(k+2)+k+3;}else if(take==2){ff=uint64_t(k)*(k+1);vv=k+2;}else if(take==1){ff=k;vv=1;}__uint128_t ql=(__uint128_t)(uint64_t)q0*ff,qh=(__uint128_t)(uint64_t)(q0>>64)*ff+(ql>>64),tl=(__uint128_t)(uint64_t)t0*ff+vv,th=(__uint128_t)(uint64_t)(t0>>64)*ff+(tl>>64);iv586w q={{(uint64_t)ql,(uint64_t)qh,(uint64_t)(qh>>64),0}},t={{(uint64_t)tl,(uint64_t)th,(uint64_t)(th>>64),0}};k+=take;for(;b-k>=3;k+=3){QY last=k+2,triple=QY(k)*(k+1)*last;iv586step(q,triple,0);iv586step(t,triple,QY(k+1)*last+last+1);}for(;b-k>=2;k+=2){QY pair=QY(k)*(k+1);iv586step(q,pair,0);iv586step(t,pair,k+2);}if(k<b){iv586step(q,k,0);iv586step(t,k,1);}ZZR{iv586big(q),iv586big(t)};}
if(size<=4||(size<=6&&b<=2097152u)){
ARW q=1,t=0;QO k=a;for(;b-k>=3;k+=3){ARL last=k+2,triple=ARL(k)*(k+1)*last;q*=triple;t=t*triple+ARL(k+1)*last+last+1;}for(;b-k>=2;k+=2){ARL pair=ARL(k)*(k+1);q*=pair;t=t*pair+k+2;}if(k<b){q*=k;t=t*k+1;}
ZZR{Big::wide(q),Big::wide(t)};
}
QC QO m=a+size/2;QT l=binary_split(a,m),r=binary_split(m,b);
Big t,q;if(!MP(l.t,l.q,r.q,t,q)){t=l.t*r.q;q=l.q*r.q;}t=std::move(t)+r.t;ZZR{std::move(q),std::move(t)};
}
ZZS QO choose_terms(QO dec){
QC long ZZD need=(long ZZD)dec+30;
QC long ZZD invln10=1.0L/logl(10.0L);
auto lower=[&](QO m){ZZR((long ZZD)m*logl((long ZZD)m)-m+1)*invln10;};
QO lo=1,hi=2;while(lower(hi)<need){if(hi>2000000000u)abort();hi*=2;}
while(lo+1<hi){QC QO m=lo+(hi-lo)/2;if(lower(m)>=need)hi=m;else lo=m;}
ZZR hi;
}
ZZS bool stable_prefix(QC std::string&s,QO digits){
if(s.size()<=digits)ZZR false;
bool lo=true,hi=true;
for(ARS i=digits;i+1<s.size();++i){lo&=s[i]=='0';hi&=s[i]=='9';}
ZZR!(lo&&s.back()<'2')&&!(hi&&s.back()>='8');
}
AXT<class Vec>ZZS void iv486write(QC Vec&x,QO digits,char*out){
struct Dec4{char d[10000][4];AXC Dec4():d{}{for(QO i=0;i<10000;++i){d[i][0]='0'+i/1000;d[i][1]='0'+i/100%10;d[i][2]='0'+i/10%10;d[i][3]='0'+i%10;}}};ZZS AXC Dec4 table{};
QO written=0;out[1]='.';auto emit=[&](char c){if(written<digits){out[written?written+1:0]=c;++written;}};
QO q=x.back();if(q>=1000)emit('0'+q/1000);if(q>=100)emit('0'+q/100%10);if(q>=10)emit('0'+q/10%10);emit('0'+q%10);
for(ARS i=x.size()-1;i--&&written<digits;){q=x[i];QO left=digits-written;if(left>=4){std::memcpy(out+written+1,table.d[q],4);written+=4;}else{emit(table.d[q][0]);if(left>=2)emit(table.d[q][1]);if(left>=3)emit(table.d[q][2]);}}
}
ZZS ARU*g_vbuf=qz004;ZZS ARS g_vcap=0;
ZZS ARU*vmul(QC ARU*a,ARS la,QC ARU*b,ARS lb,ARS&outlen){
QC ARS need=la+lb+1;
if(g_vcap<need){free(g_vbuf);g_vbuf=(ARU*)malloc(need*arZ(ARU));if(!g_vbuf)abort();g_vcap=need;}
outlen=need;
if(!la||!lb){memset(g_vbuf,0,need*arZ(ARU));ZZR g_vbuf;}
hint_arithm::fft_mul<10000>(a,b,g_vbuf,la,lb);
g_vbuf[la+lb]=0;
ZZR g_vbuf;
}
ZZS void vtrim(std::vector<ARU>&v){ARS n=v.size();while(n>1&&v[n-1]==0)--n;v.resize(n);}
ZZS ZZD*ar_nr[2]={qz004,qz004};ZZS ARS ar_nr_cap=0;
ZZS void ar_nr_prepare(QC ARU*r,ARS lr,ARS n){
if(ar_nr_cap<n){for(QO j=0;j<2;j++){_mm_free(ar_nr[j]);ar_nr[j]=(ZZD*)_mm_malloc(n*8,64);}ar_nr_cap=n;}
hint_arithm::qz017(ar_nr[0],r,lr);memset(ar_nr[0]+lr,0,(n-lr)*8);
qz014::transform::fft::FFTAVX::difRecLong<true>(ar_nr[0],n);
}
ZZS ARU*ar_nr_product(QC ARU*a,ARS la,ARS lr,ARS n,ARS&outlen){
outlen=la+lr+1;if(g_vcap<outlen){free(g_vbuf);g_vbuf=(ARU*)malloc(outlen*4);if(!g_vbuf)abort();g_vcap=outlen;}
hint_arithm::qz017(ar_nr[1],a,la);memset(ar_nr[1]+la,0,(n-la)*8);
using namespace qz014::transform::fft;
FFTAVX::difRecLong<true>(ar_nr[1],n);qz019(ar_nr[1],ar_nr[0],n);FFTAVX::iditRecLong<true,true>(ar_nr[1],n);
QC ARL*c=(QC ARL*)ar_nr[1];ARL carry=0;ARS conv=la+lr-1;
for(ARS j=0;j<conv;j++){carry+=c[j];g_vbuf[j]=carry%10000;carry/=10000;}g_vbuf[conv]=carry%10000;g_vbuf[conv+1]=0;ZZR g_vbuf;
}
AXT<class VA,class VB>ZZS std::vector<ARU>scaled_newton(QC VA&Tv,
QC VB&Qv,
ARS L){
QC ARU*Q=Qv.data();QC ARS nq=Qv.size();
QC ARS M0=3;
long ZZD qk=0,scale=1;
for(int i=0;i<8&&(ARS)i<nq;++i){qk=qk*10000.0L+(long ZZD)Q[nq-1-i];scale*=10000.0L;}
long ZZD rho=scale/(qk+1.0L);
ARL R0=(ARL)(rho*1e12L);
std::vector<ARU>R;
while(R0){R.push_back((ARU)(R0%10000));R0/=10000;}
if(R.empty())R.push_back(1);
ARS M=M0;
for(int iter=0;iter<80;++iter){
QC ARS quse=(nq<2*M)?nq:2*M;
QC ARU*Dq=Q+(nq-quse);
QC ARS lr=R.size();
QC ARS ar_n=qz014::int_ceil2(quse+lr-1);bool ar_keep=ar_n>=4096;if(ar_keep)ar_nr_prepare(R.data(),lr,ar_n);
ARS plen;ARU*P=ar_keep?ar_nr_product(Dq,quse,lr,ar_n,plen):vmul(Dq,quse,R.data(),lr,plen);
QC ARS fpow=M+quse;
ARS flen=(plen>fpow+2)?plen:fpow+2;
std::vector<ARU>F(flen+1,0);
F[fpow]=1;
int borrow=0;
for(ARS i=0;i<flen;++i){
int d=int(F[i])-int((i<plen)?P[i]:0)-borrow;
borrow=d<0;F[i]=ARU(d+(borrow?10000:0));
}
int neg=borrow!=0;
if(neg){
int carry=0;
for(ARS i=0;i<flen;++i){
int d=int((i<plen)?P[i]:0)-int(i==fpow?1:0)-carry;
carry=d<0;F[i]=ARU(d+(carry?10000:0));
}
}
vtrim(F);
QC ARS p=(fpow>F.size())?(fpow-F.size()):0;
if(M>=L&&p+6>=L)break;
ARS M2=(2*M<L)?2*M:L;
if(M2<=M)M2=2*M;
if(M<8192){ARS r=M+M/2+1;if(r<M2)M2=r;}
else{ARS w=1;while(w*2<=M2)w*=2;if(w>M)M2=w;}
QC ARS sh=quse;
std::vector<ARU>Rn(M+lr+((F.size()>lr)?F.size():lr)+3,0);
for(ARS i=0;i<lr;++i)Rn[M+i]=R[i];
if(F.size()>1||F[0]){
ARS glen;ARU*G=(ar_keep&&qz014::int_ceil2(lr+F.size()-1)==ar_n)?ar_nr_product(F.data(),F.size(),lr,ar_n,glen):vmul(R.data(),lr,F.data(),F.size(),glen);
ARS i=0;
if(!neg){
QO carry=0;
for(;sh+i<glen;++i){QO q=Rn[i]+G[sh+i]+carry;carry=q>=10000;Rn[i]=q-(carry?10000:0);}
for(;carry&&i<Rn.size();++i){QO q=Rn[i]+carry;carry=q>=10000;Rn[i]=q-(carry?10000:0);}
}else{
int br=0;
for(;sh+i<glen;++i){int q=int(Rn[i])-int(G[sh+i])-br;br=q<0;Rn[i]=ARU(q+(br?10000:0));}
for(;br&&i<Rn.size();++i){int q=int(Rn[i])-br;br=q<0;Rn[i]=ARU(q+(br?10000:0));}
}
}
if(2*M!=M2&&Rn.size()>2*M-M2)Rn.erase(Rn.begin(),Rn.begin()+(2*M-M2));
vtrim(Rn);
R.swap(Rn);M=M2;
}
if(M>L){
ARS drop=M-L;
if(R.size()>drop)R.erase(R.begin(),R.begin()+drop);else{R.assign(1,0);}
vtrim(R);
}
ARS plen;ARU*P=vmul(Tv.data(),Tv.size(),R.data(),R.size(),plen);
ARS slen=plen>nq?plen-nq:0;
std::vector<ARU>S(L+3,0);
for(ARS i=0;i<slen&&i<L+3;++i)S[i]=P[nq+i];
S[L]+=1;
for(ARS i=L;i+1<S.size()&&S[i]>=10000;++i){S[i]-=10000;S[i+1]+=1;}
while(S.size()>1&&S.back()==0)S.pop_back();
ZZR S;
}
struct Result{std::string digits;QO terms;ARL bs_ticks,divide_ticks,format_ticks;bool guard_stable;};
__attribute__((noinline,noclone))Result compute(QO digits,char*out){
if(!digits)ZZR{"",0,0,0,0,true};
QC QO limbs=(digits+50)/4,dec=limbs*4,terms=choose_terms(dec);
_mm_lfence();QC ARL t0=__rdtsc();QT r=binary_split(1,terms+1);
if(r.q.v.size()<=ARS(limbs)+6)abort();
_mm_lfence();QC ARL t1=__rdtsc();
auto scaled=scaled_newton(r.t.v,r.q.v,limbs);
_mm_lfence();QC ARL t2=__rdtsc();
iv486write(scaled,digits,out);std::string s;bool ok=true;
_mm_lfence();QC ARL t3=__rdtsc();
ZZR{std::move(s),terms,t1-t0,t2-t1,t3-t2,ok};
}
// Shared-operand ZZD product: o1 = A*C, o2 = B*C (base 10000, exact).
// Each binary-splitting node forms t=l.t*r.q and q=l.q*r.q. Both products use
// r.q and land on the same transform length, so r.q is converted and forward
// transformed once and its spectrum reused: 3 forward + 2 inverse transforms
// instead of 4 + 2. The pointwise products and inverses are the inherited ones.
ZZS bool MP(QC Big&A,QC Big&B,QC Big&C,Big&o1,Big&o2){
ARS oa=A.v.size(),ob=B.v.size(),oc=C.v.size();if(oa<2||ob<2||oc<2)ZZR 0;
ARS za=0,zb=0,zc=0;while(A.v[za]==0)++za;while(B.v[zb]==0)++zb;while(C.v[zc]==0)++zc;
ARS la=oa-za,lb=ob-zb,lc=oc-zc;
if(la<2||lb<2||lc<2)ZZR 0;
ARS c1=la+lc-1,c2=lb+lc-1;
if(c1<4096||c2<4096||la*lc<=65536||lb*lc<=65536)ZZR 0;
ARS n=qz014::int_ceil2(c1);if(qz014::int_ceil2(c2)!=n)ZZR 0;
ZZS ZZD*F3[3]={0,0,0};ZZS ARS cap=0;
if(cap<n){for(int i=0;i<3;i++){_mm_free(F3[i]);F3[i]=(ZZD*)_mm_malloc(n*8,64);}cap=n;}
ZZD*a=F3[0],*b=F3[1],*d=F3[2];
memset(a+la,0,(n-la)*8);hint_arithm::qz017(a,A.v.data()+za,la);
memset(b+lb,0,(n-lb)*8);hint_arithm::qz017(b,B.v.data()+zb,lb);
memset(d+lc,0,(n-lc)*8);hint_arithm::qz017(d,C.v.data()+zc,lc);
using qz014::transform::fft::FFTAVX;using qz014::transform::fft::qz019;
FFTAVX::difRecLong<true>(d,n);
FFTAVX::difRecLong<true>(a,n);qz019(a,d,n);FFTAVX::iditRecLong<true,true>(a,n);
FFTAVX::difRecLong<true>(b,n);qz019(b,d,n);FFTAVX::iditRecLong<true,true>(b,n);
ARS s1=za+zc,s2=zb+zc;o1.v.resize(oa+oc);o2.v.resize(ob+oc);
if(s1)memset(o1.v.data(),0,s1*4);if(s2)memset(o2.v.data(),0,s2*4);
ARU*p=o1.v.data()+s1,*q=o2.v.data()+s2;
ARL k=0;for(ARS i=0;i<c1;i++){k+=((QC ARL*)a)[i];p[i]=k%10000;k/=10000;}p[c1]=k%10000;
k=0;for(ARS i=0;i<c2;i++){k+=((QC ARL*)b)[i];q[i]=k%10000;k/=10000;}q[c2]=k%10000;
o1.neg=o2.neg=0;o1.trim();o2.trim();ZZR 1;
}
}
void calc_e(QO n,char*s){if(!n)ZZR;if(n==1){s[0]='2';ZZR;}e_compute::compute(n-1,s);}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 388.516 ms | 140 MB + 652 KB | Accepted | Score: 100 | 显示更多 |