提交记录 166325


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_v41f1017_agg4 1020a. 测测你的自然常数2 Accepted 100 389.493 ms 144012 KB C++17 99.69 KB
提交时间 评测时间
2026-11-17 09:14:36 2026-11-17 09:14:47
/* saffah_v41f1017_agg4: adopted https://duck.ac/submission/166221 verbatim; changed only HintFFT LOG_SHORT 10->7 and the fft_mul scalar-FFT threshold (->conv<512), dropping the 4096 pad. LOG_SHORT=7 makes the AVX real transform exact at every power-of-two size (checked exactly against schoolbook for all sizes 8..400000), so small products use it at their true length. All inherited notices and the full TSKY(With-Sky) HintFFT MIT licence are retained verbatim; licence compliance unchanged. Purpose: delete the scalar short-convolution path and the 4096 pad; official measurement decides. */
/* 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.
*/
#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 E arY
#define AXC arK
#define Z 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 hintpowfft
{
AXT<ZZT T,E ALIGN=64>
class AlignMem{
public:
using Ptr=T*;
using ConstPtr=QC T*;
~AlignMem(){
if(ptr){
_mm_free(ptr);}};
AlignMem():ptr(nullptr),len(0){}
AlignMem(E n):ptr(az00<Ptr>(_mm_malloc(n*arZ(T),ALIGN))),len(n){}
AlignMem(QC AlignMem&)=delete;
AlignMem&az04=(QC AlignMem&)=delete;
T&az04[](E i){
ZZR ptr[i];}
QC T&az04[](E 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;}
E size()QC{
ZZR len;}
private:
T*ptr;
E 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(_mm256_permute2f128_pd(t0,t1,0x20));
row1=YMM(_mm256_permute2f128_pd(t0,t1,0x31));}
AXT<ZZT YMM>
QI void transpose64_4X2(YMM&row0,YMM&row1){
auto t0=_mm256_permute2f128_pd(ZZV(row0),ZZV(row1),0x20);
auto t1=_mm256_permute2f128_pd(ZZV(row0),ZZV(row1),0x31);
row0=YMM(_mm256_unpacklo_pd(t0,t1));
row1=YMM(_mm256_unpackhi_pd(t0,t1));}
AXT<ZZT YMM>
QI void transpose64_4X4(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(_mm256_permute2f128_pd(t0,t2,0x20));
row1=YMM(_mm256_permute2f128_pd(t1,t3,0x20));
row2=YMM(_mm256_permute2f128_pd(t0,t2,0x31));
row3=YMM(_mm256_permute2f128_pd(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 _mm256_mul_pd(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 Float64=ZZD;
AXC Float64 HINT_PI=3.141592653589793238462643;
AXC Float64 HINT_2PI=HINT_PI*2;
AXC Float64 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 transform2(T&sum,T&diff){
T temp0=sum,temp1=diff;
sum=temp0+temp1;
diff=temp0-temp1;}
namespace fft{
using F64=Float64;
using C64=std::complex<F64>;
using F64X4=Float64X4;
using C64X4=Complex64X4;
AXT<ZZT Float,E OMEGA_LEN>
class TableFix{
alignas(64)Float table[OMEGA_LEN*2];
public:
TableFix(E theta_divider,E factor,E stride){
QC Float theta= -HINT_2PI*factor/theta_divider;
for(E begin=0,index=0;begin<OMEGA_LEN*2;begin+=stride*2)
{
for(E 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[](E index)QC{
ZZR table[index];}};
void initOmegaX4(F64*arr,E 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(E begin=1;begin<table_len;begin*=2){
E nth=begin*4;
C64X4 unit;
unit.set1(std::cos(theta*nth),std::sin(theta*nth));
for(E 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 E TABLE_CPX_LEN=(E(1)<<(LOG_END+1))/DIV;
alignas(64)Float table[TABLE_CPX_LEN*2];
public:
TableFixMulti(E factor,E stride=4){
initBottomUp(factor,stride);}
void initBottomUp(E factor,E stride){
static_assert(std::is_same<Float,Float64>::value);
E len=E(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=E(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(E(1)<<log_rank);}
AXC Float*getBeginLog(int log_rank){
ZZR getBegin(E(1)<<log_rank);}
AXC QC Float*getBegin(E rank)QC{
ZZR&table[rank*2/DIV];}
AXC Float*getBegin(E rank){
ZZR&table[rank*2/DIV];}};
AXT<int CACHE_LOG_LEN>
class FFTSqrtTableC64X4{
public:
using F64=ZZD;
using C64=std::complex<ZZD>;
using C64X4=hintpowfft::Complex64X4;
ZZS AXC E CACHE_LEN=E(1)<<CACHE_LOG_LEN;
ZZS AXC E MASK=CACHE_LEN-1;
ZZS AXC E C4_COUNT=arZ(C64X4)/arZ(C64);
~FFTSqrtTableC64X4(){
if(high)
{
delete[]high;}}
FFTSqrtTableC64X4(){}
FFTSqrtTableC64X4(E azE,int len_div,int factor){
init(azE,len_div,factor);}
void init(E azE,int len_div,int factor){
E table_len=azE/len_div;
E low_len=CACHE_LEN*C4_COUNT,high_len=table_len/low_len;
if(high!=nullptr)
{
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(E begin=1;begin<high_len;begin*=2)
{
C64 unit=std::polar<F64>(1.0,theta*begin*low_len);
for(E i=0;i<begin;i++)
{
high[i+begin]=high[i]*unit;}}}
C64X4 az04[](E 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=nullptr;};
AXT<int DIV,int LOG_BEGIN,int LOG_MAX,int CACHE_LOG_LEN>
class FFTTableSqrt{
using TableLong=FFTSqrtTableC64X4<CACHE_LOG_LEN>;
ZZS AXC E SHORT_LEN=E(1)<<LOG_BEGIN;
ZZS AXC E TABLE_LEN=LOG_MAX-LOG_BEGIN+1;
public:
FFTTableSqrt(int factor){
for(int i=0;i<TABLE_LEN;i++)
{
E 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);
transform2(r0,r1);
transform2(i0,i1);}
AXT<ZZT Float>
ZZS void idit4(Float&r0,Float&i0,Float&r1,Float&i1,Float&r2,Float&i2,Float&r3,Float&i3){
transform2(r0,r1);
transform2(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){
transform2(r0,r2);
transform2(i0,i2);
transform2(r1,r3);
transform2(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){
transform2(r2,r3);
transform2(i2,i3);
transform2(r0,r2);
transform2(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 E SHORT_LEN=E(1)<<LOG_SHORT,MID_LEN=E(1)<<LOG_MID,MAX_LEN=E(1)<<LOG_MAX;
using TableFix4=QC TableFix<Float64,4>;
using TableFix8=QC TableFix<Float64,8>;
using TableMulti1=QC TableFixMulti<Float64,LOG_SHORT+1,LOG_MID,4>;
using TableMulti2=QC TableFixMulti<Float64,6,LOG_SHORT+1,4>;
using TableMulti3=QC TableFixMulti<Float64,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 Float64*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){
transpose64_4X4(r0,r1,r2,r3);
transpose64_4X4(i0,i1,i2,i3);
dif4(r0,i0,r1,i1,r2,i2,r3,i3);
transpose64_4X4(r0,r1,r2,r3);
transpose64_4X4(i0,i1,i2,i3);}
ZZS void idit4x4(F64X4&r0,F64X4&i0,F64X4&r1,F64X4&i1,F64X4&r2,F64X4&i2,F64X4&r3,F64X4&i3){
transpose64_4X4(r0,r1,r2,r3);
transpose64_4X4(i0,i1,i2,i3);
idit4(r0,i0,r1,i1,r2,i2,r3,i3);
transpose64_4X4(r0,r1,r2,r3);
transpose64_4X4(i0,i1,i2,i3);}
ZZS void dif8x2(C64X4&c0,C64X4&c1,C64X4&c2,C64X4&c3){
C64X4 omega(it8);
transform2(c0,c1);
transform2(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);
transform2(c0,c1);
transform2(c2,c3);}
ZZS void dif16(Float64 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(Float64 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(Float64 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(Float64 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(Float64 in_out[],E 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(Float64 in_out[],E az01){
E azE=az01/2;
C64X4 c0,c1,c2,c3;
E stride=azE/2;
auto it0=in_out,it1=it0+stride,it2=it1+stride,it3=it2+stride;
for(E 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(Float64 in_out[],E az01){
E azE=az01/2;
E rank=hint_log2(azE)%2==0?64:128;
fftTiny(in_out,az01,idit32,idit16);
for(;rank<=azE;rank*=4)
{
QC E 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; \
E indx = 0; \
for (auto end = it1; FROM_RIRI_PERM && 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; (!FROM_RIRI_PERM) && 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; \
E 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 FROM_RIRI_PERM=false>
ZZS void difRecMid(Float64 in_out[],E az01){
QC E azE=az01/2;
if(azE<=SHORT_LEN)
{
difIter(in_out,az01);
ZZR;}
using FromRIRI=std::integral_constant<bool,FROM_RIRI_PERM>;
auto table1=az00<QC C64X4*>(multi_table_1.getBegin(azE));
QC E stride=az01/4;
difLayer(difRecMid,in_out,stride,table1);}
AXT<bool TO_RIRI_PERM=false,bool TO_INT64=false>
ZZS void iditRecMid(Float64 in_out[],E az01){
QC E azE=az01/2;
if(azE<=SHORT_LEN)
{
iditIter(in_out,az01);
ZZR;}
using ToRIRI=std::integral_constant<bool,TO_RIRI_PERM>;
using ToI64=std::integral_constant<bool,TO_INT64>;
QC E stride=az01/4;
auto table1=az00<QC C64X4*>(multi_table_1.getBegin(azE));
iditLayer(iditRecMid,in_out,stride,table1);}
AXT<bool FROM_RIRI_PERM=false>
ZZS void difRecLong(Float64 in_out[],E az01){
QC E azE=az01/2;
if(azE<=MID_LEN)
{
difRecMid<FROM_RIRI_PERM>(in_out,az01);
ZZR;}
using FromRIRI=std::integral_constant<bool,FROM_RIRI_PERM>;
QC auto&table1=sqrt_table_1[hint_log2(azE)];
QC E stride=az01/4;
difLayer(difRecLong,in_out,stride,table1);}
AXT<bool TO_RIRI_PERM=false,bool TO_INT64=false>
ZZS void iditRecLong(Float64 in_out[],E az01){
QC E azE=az01/2;
if(azE<=MID_LEN)
{
iditRecMid<TO_RIRI_PERM,TO_INT64>(in_out,az01);
ZZR;}
using ToRIRI=std::integral_constant<bool,TO_RIRI_PERM>;
using ToI64=std::integral_constant<bool,TO_INT64>;
QC E 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 E 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 E MAX_LEN=E(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(E(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(E 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(E n,E 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];
E 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<E 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 Z=std::complex<FloatTy>;
auto addConj=[](Z c0,Z c1){ZZR Z(c0.real()+c1.real(),c0.imag()-c1.imag());};
Z 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=Z(t0.real()-t1.real(),t0.imag()+t1.imag())*inv2;
Z 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 real_dot_binrev4(Float64 in_out[],Float64 in[],E az01){
Float64 inv=2.0/az01;{
auto r0=in_out[0],i0=in_out[4],r1=in[0],i1=in[4];
transform2(r0,i0);
transform2(r1,i1);
r0*=r1,i0*=i1;
transform2(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 Float64 COS_16_1=0.92387953251128675612818318939;
AXC Float64 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(E 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,E az01){
FFTAVX::difRecLong<true>(in_out1,az01);
FFTAVX::difRecLong<true>(in2,az01);
real_dot_binrev4(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 Z=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(Z a)
{
data=_mm256_broadcast_pd((__m128d*)&a);
}
az02(QC Z*ptr)
{
data=_mm256_loadu_pd((QC ZZD*)ptr);
}
void clr()
{
data=_mm256_setzero_pd();
}
void store(Z*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=_mm256_mul_pd(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 UINT_64=ARL;
using INT_32=int32_t;
using INT_64=int64_t;
using LONG=long;
using Z=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,E len)
{
memset(ptr,0,len*arZ(T));
}
AXT<ZZT T>
AXC bool is_neg(T x)
{
ZZR x<0;
}
AXT<ZZT T>
AXC E 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 static_cast<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,E 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,E len)
{
if(len*arZ(T)<INT64_MAX)
{
ptr=static_cast<T*>(realloc(ptr,len*arZ(T)));
}
if(ptr==nullptr)
{
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 UINT_64 qpow(UINT_64 m,UINT_64 n,UINT_64 mod)
{
if(m<=1)
{
ZZR m;
}
UINT_64 result=1;
while(n>0)
{
if((n&1)!=0)
{
result=result*m%mod;
}
m=m*m%mod;
n>>=1;
}
ZZR result;
}
AXC UINT_64 mod_inv(UINT_64 n,UINT_64 mod)
{
ZZR qpow(n,mod-2,mod);
}
AXT<ZZT T>
QI void com_ary_combine_copy(Z*target,QC T&source1,E len1,QC T&source2,E len2)
{
E min_len=std::min(len1,len2);
E i=0;
while(i<min_len)
{
target[i]=Z(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 ComplexTableY
{
private:
std::vector<std::vector<Z>>table1;
std::vector<std::vector<Z>>table3;
INT_32 max_log_size=2;
INT_32 cur_log_size=2;
ZZS AXC E FAC=1;
ComplexTableY(QC ComplexTableY&)=delete;
ComplexTableY&az04=(QC ComplexTableY&)=delete;
public:
~ComplexTableY(){}
ComplexTableY(UINT_32 max_shift)
{
max_shift=std::max<E>(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<Z>{1};
table1[2]=table3[2]=std::vector<Z>{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++)
{
E len=1ull<<i,vec_size=len*FAC/4;
table1[i].resize(vec_size);
table3[i].resize(vec_size);
table1[i][0]=table3[i][0]=Z(1,0);
for(E pos=0;pos<vec_size/2;pos++)
{
table1[i][pos*2]=table1[i-1][pos];
table3[i][pos*2]=table3[i-1][pos];
}
for(E 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]=Z(cos_theta,-sin_theta);
table1[i][vec_size-pos]=Z(sin_theta,-cos_theta);
}
table1[i][vec_size/2]=std::conj(unit_root(8,1));
for(E pos=1;pos<vec_size/2;pos+=2)
{
Z tmp=get_omega(i,pos*3);
table3[i][pos]=tmp;
table3[i][vec_size-pos]=Z(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 Z unit_root(ZZD theta)
{
ZZR std::polar<ZZD>(1.0,theta);
}
ZZS Z unit_root(E m,E n)
{
ZZR unit_root((HINT_2PI*n)/m);
}
Z get_omega(UINT_32 shift,E n)QC
{
E rank=1ull<<shift;
QC E rank_ff=rank-1,quad_n=n<<2;
E zone=quad_n>>shift;
if((quad_n&rank_ff)==0)
{
ZZS AXC Z ONES[4]={Z(1,0),Z(0,-1),Z(-1,0),Z(0,1)};
ZZR ONES[zone];
}
Z 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;
}
Z get_omega3(UINT_32 shift,E n)QC
{
ZZR table3[shift][n];
}
az02 get_omegaX2(UINT_32 shift,E n)QC
{
ZZR az02(table1[shift].data()+n);
}
az02 get_omega3X2(UINT_32 shift,E n)QC
{
ZZR az02(table3[shift].data()+n);
}
};
AXC E lut_max_rank=23;
ZZS ComplexTableY TABLE(lut_max_rank);
AXT<ZZT T>
void binary_reverse_swap(T&ary,E len)
{
E i=0;
for(E j=1;j<len-1;j++)
{
E 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,E 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(Z*input,E rank=1)
{
Z tmp0=input[0];
Z tmp1=input[rank];
Z tmp2=input[rank*2];
Z tmp3=input[rank*3];
azD(tmp0,tmp2);
azD(tmp1,tmp3);
tmp3=Z(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(Z*input,E rank=1)
{
Z tmp0=input[0];
Z tmp1=input[rank];
Z tmp2=input[rank*2];
Z tmp3=input[rank*3];
azD(tmp0,tmp1);
azD(tmp2,tmp3);
tmp3=Z(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(Z*input,E rank=1)
{
Z tmp0=input[0];
Z tmp1=input[rank];
Z tmp2=input[rank*2];
Z tmp3=input[rank*3];
Z tmp4=input[rank*4];
Z tmp5=input[rank*5];
Z tmp6=input[rank*6];
Z tmp7=input[rank*7];
azD(tmp0,tmp1);
azD(tmp2,tmp3);
azD(tmp4,tmp5);
azD(tmp6,tmp7);
tmp3=Z(tmp3.imag(),-tmp3.real());
tmp7=Z(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*Z(tmp5.imag()+tmp5.real(),tmp5.imag()-tmp5.real());
tmp6=Z(tmp6.imag(),-tmp6.real());
tmp7= -cos_1_8*Z(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(Z*input,E rank=1)
{
Z tmp0=input[0];
Z tmp1=input[rank];
Z tmp2=input[rank*2];
Z tmp3=input[rank*3];
azD(tmp0,tmp2);
azD(tmp1,tmp3);
tmp3=Z(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(Z*input,E rank=1)
{
Z tmp0=input[0];
Z tmp1=input[rank];
Z tmp2=input[rank*2];
Z tmp3=input[rank*3];
Z tmp4=input[rank*4];
Z tmp5=input[rank*5];
Z tmp6=input[rank*6];
Z 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*Z(tmp5.imag()+tmp5.real(),tmp5.imag()-tmp5.real());
tmp6=Z(tmp6.imag(),-tmp6.real());
tmp7= -cos_1_8*Z(tmp7.real()-tmp7.imag(),tmp7.real()+tmp7.imag());
azD(tmp0,tmp2);
azD(tmp1,tmp3);
azD(tmp4,tmp6);
azD(tmp5,tmp7);
tmp3=Z(tmp3.imag(),-tmp3.real());
tmp7=Z(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(Z omega,Z*input,E rank)
{
Z tmp0=input[0];
Z tmp1=input[rank]*omega;
input[0]=tmp0+tmp1;
input[rank]=tmp0-tmp1;
}
QI void fft_radix2_dif_butterfly(Z omega,Z*input,E rank)
{
Z tmp0=input[0];
Z tmp1=input[rank];
input[0]=tmp0+tmp1;
input[rank]=(tmp0-tmp1)*omega;
}
QI void fft_split_radix_dit_butterfly(Z omega,Z omega_cube,
Z*input,E rank)
{
Z tmp0=input[0];
Z tmp1=input[rank];
Z tmp2=input[rank*2]*omega;
Z tmp3=input[rank*3]*omega_cube;
azD(tmp2,tmp3);
tmp3=Z(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(Z omega,Z omega_cube,
Z*input,E rank)
{
Z tmp0=input[0];
Z tmp1=input[rank];
Z tmp2=input[rank*2];
Z tmp3=input[rank*3];
azD(tmp0,tmp2);
azD(tmp1,tmp3);
tmp3=Z(tmp3.imag(),-tmp3.real());
input[0]=tmp0;
input[rank]=tmp1;
input[rank*2]=(tmp2+tmp3)*omega;
input[rank*3]=(tmp2-tmp3)*omega_cube;
}
QI void fft_split_radix_dit_butterfly(az02 omega,az02 omega_cube,
Z*input,E rank)
{
az02 tmp0=input;
az02 tmp1=input+rank;
az02 tmp2=az02(input+rank*2)*omega;
az02 tmp3=az02(input+rank*3)*omega_cube;
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 omega_cube,
Z*input,E 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)*omega_cube).store(input+rank*3);
}
QI void fft_radix4_dit_butterfly(Z omega,Z omega_sqr,Z omega_cube,
Z*input,E rank)
{
Z tmp0=input[0];
Z tmp1=input[rank]*omega;
Z tmp2=input[rank*2]*omega_sqr;
Z tmp3=input[rank*3]*omega_cube;
azD(tmp0,tmp2);
azD(tmp1,tmp3);
tmp3=Z(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(Z omega,Z omega_sqr,Z omega_cube,
Z*input,E rank)
{
Z tmp0=input[0];
Z tmp1=input[rank];
Z tmp2=input[rank*2];
Z tmp3=input[rank*3];
azD(tmp0,tmp2);
azD(tmp1,tmp3);
tmp3=Z(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)*omega_cube;
}
QI void fft_conj(Z*input,E azE,ZZD div=1)
{
for(E i=0;i<azE;i++)
{
input[i]=std::conj(input[i])/div;
}
}
QI void fft_normalize(Z*input,E azE)
{
ZZD len=static_cast<ZZD>(azE);
for(E i=0;i<azE;i++)
{
input[i]/=len;
}
}
AXT<E LEN>
void azB(Z*input)
{
AXC E log_len=hint_log2(LEN);
AXC E half_len=LEN/2,quarter_len=LEN/4;
azB<half_len>(input);
azB<quarter_len>(input+half_len);
azB<quarter_len>(input+half_len+quarter_len);
for(E i=0;i<quarter_len;i+=2)
{
auto omega=TABLE.get_omegaX2(log_len,i);
auto omega_cube=TABLE.get_omega3X2(log_len,i);
fft_split_radix_dit_butterfly(omega,omega_cube,input+i,quarter_len);
}
}
AXT<>
void azB<0>(Z*input){}
AXT<>
void azB<1>(Z*input){}
AXT<>
void azB<2>(Z*input)
{
azD(input[0],input[1]);
}
AXT<>
void azB<4>(Z*input)
{
fft_dit_4point(input,1);
}
AXT<>
void azB<8>(Z*input)
{
fft_dit_8point(input,1);
}
AXT<E LEN>
void azC(Z*input)
{
AXC E log_len=hint_log2(LEN);
AXC E half_len=LEN/2,quarter_len=LEN/4;
for(E i=0;i<quarter_len;i+=2)
{
auto omega=TABLE.get_omegaX2(log_len,i);
auto omega_cube=TABLE.get_omega3X2(log_len,i);
fft_split_radix_dif_butterfly(omega,omega_cube,input+i,quarter_len);
}
azC<half_len>(input);
azC<quarter_len>(input+half_len);
azC<quarter_len>(input+half_len+quarter_len);
}
AXT<>
void azC<0>(Z*input){}
AXT<>
void azC<1>(Z*input){}
AXT<>
void azC<2>(Z*input)
{
azD(input[0],input[1]);
}
AXT<>
void azC<4>(Z*input)
{
fft_dif_4point(input,1);
}
AXT<>
void azC<8>(Z*input)
{
fft_dif_8point(input,1);
}
AXT<E LEN=1>
void fft_dit_template(Z*input,E 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>(Z*input,E azE){}
AXT<E LEN=1>
void fft_dif_template(Z*input,E 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>(Z*input,E azE){}
QI void fft_dit(Z*input,E 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(Z*input,E azE,bool bit_rev=true)
{
azE=max_2pow(azE);
fft_dif_template<1>(input,azE);
if(bit_rev)
{
binary_reverse_swap(input,azE);
}
}
}
AXT<UINT_64 BASE,ZZT T>
AXC void save_num_to_ary(T ary[],UINT_64 num,E digit)
{
E i=digit;
while(i>0)
{
i--;
ary[i]=num%BASE;
num/=BASE;
}
}
UINT_64 stoui64(QC std::string::const_iterator&begin,
QC std::string::const_iterator&end,QC UINT_32 base=10)
{
UINT_64 result=0;
for(auto it=begin;it<end&&it-begin<19;++it)
{
result*=base;
char c=tolower(*it);
UINT_64 n=0;
if(isalnum(c))
{
if(isalpha(c))
{
n=c-'a'+10;
}
else
{
n=c-'0';
}
}
if(n<base)
{
result+=n;
}
}
ZZR result;
}
UINT_64 stoui64(QC std::string&str,QC UINT_32 base=10)
{
ZZR stoui64(str.begin(),str.end(),base);
}
std::string ui64to_string(UINT_64 input,UINT_8 digits)
{
std::string result(digits,'0');
for(UINT_8 i=0;i<digits;i++)
{
result[digits-i-1]=static_cast<char>(input%10+'0');
input/=10;
}
ZZR result;
}
AXT<ZZT T=UINT_32,ZZT azA=UINT_32>
class HintVector
{
private:
T*ary_ptr=nullptr;
azA sign_n_len=0;
azA size=0;
public:
~HintVector()
{
if(ary_ptr!=nullptr)
{
delete[]ary_ptr;
ary_ptr=nullptr;
}
}
HintVector()
{
ary_ptr=nullptr;
}
HintVector(azA ele_size)
{
if(ele_size>0)
{
resize(ele_size);
}
}
HintVector(azA ele_size,T ele)
{
if(ele_size>0)
{
resize(ele_size);
az03(ele_size);
fill_element(ele,ele_size);
}
}
HintVector(QC T*ary,azA len)
{
if(ary==nullptr)
{
throw("Can't copy from nullptr\n");
}
if(len>0)
{
resize(len);
az03(len);
ary_copy(ary_ptr,ary,len);
}
}
HintVector(QC HintVector&input)
{
if(input.ary_ptr!=nullptr)
{
if(ary_ptr!=nullptr)
{
delete[]ary_ptr;
}
ary_ptr=nullptr;
E len=input.length();
resize(len);
az03(len);
change_sign(input.sign());
ary_copy(ary_ptr,input.ary_ptr,len);
}
}
HintVector(HintVector&&input)
{
if(input.ary_ptr!=nullptr)
{
size=input.size;
az03(input.length());
change_sign(input.sign());
if(ary_ptr!=nullptr)
{
delete[]ary_ptr;
}
ary_ptr=input.ary_ptr;
input.ary_ptr=nullptr;
}
}
HintVector&az04=(QC HintVector&input)
{
if(this!= &input)
{
if(ary_ptr!=nullptr)
{
delete[]ary_ptr;
}
ary_ptr=nullptr;
E len=input.length();
resize(len);
az03(len);
change_sign(input.sign());
ary_copy(ary_ptr,input.ary_ptr,len);
}
ZZR*this;
}
HintVector&az04=(HintVector&&input)
{
if(this!= &input)
{
size=input.size;
az03(input.length());
change_sign(input.sign());
if(ary_ptr!=nullptr)
{
delete[]ary_ptr;
}
ary_ptr=input.ary_ptr;
input.ary_ptr=nullptr;
}
ZZR*this;
}
T&az04[](azA index)QC
{
ZZR ary_ptr[index];
}
T*data()QC
{
ZZR ary_ptr;
}
ZZS azA size_generator(azA new_size)
{
AXC azA SIZE_TYPE_BITS=arZ(azA)*8;
AXC azA SIZE_80=(1ull<<(SIZE_TYPE_BITS-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 SIZE_TYPE_BITS=arZ(azA)*8;
AXC azA SIZE_80=(1ull<<(SIZE_TYPE_BITS-1));
AXC azA LEN_MAX=SIZE_80-1;
ZZR sign_n_len&LEN_MAX;
}
bool sign()QC
{
AXC azA SIZE_TYPE_BITS=arZ(azA)*8;
AXC azA SIZE_80=(1ull<<(SIZE_TYPE_BITS-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(ary_ptr==nullptr)
{
size=new_size;
ary_ptr=new T[size];
az03(0);
}
else if(size!=new_size)
{
size=new_size;
ary_ptr=ary_realloc(ary_ptr,size);
az03(length());
}
}
void az03(azA new_length)
{
AXC azA SIZE_TYPE_BITS=arZ(azA)*8;
AXC azA SIZE_80=(1ull<<(SIZE_TYPE_BITS-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 SIZE_TYPE_BITS=arZ(azA)*8;
AXC azA SIZE_80=(1ull<<(SIZE_TYPE_BITS-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 set_true_len()
{
if(ary_ptr==nullptr)
{
ZZR 0;
}
azA t_len=length();
while(t_len>0&&ary_ptr[t_len-1]==0)
{
t_len--;
}
az03(t_len);
ZZR length();
}
void fill_element(T ele,azA count,azA begin=0)
{
if(begin>=size||ary_ptr==nullptr)
{
ZZR;
}
if(begin+count>=size)
{
count=size-begin;
}
std::fill(ary_ptr+begin,ary_ptr+begin+count,ele);
}
};
}
namespace hint_arithm
{
using namespace hint;
using azA=UINT_32;
AXT<ZZT T>
using hintvector=HintVector<T,azA>;
AXT<ZZT T>
AXC E ary_true_len(QC T&ary,E 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[],E len1,E len2)
{
len1=ary_true_len(ary1,len1);
len2=ary_true_len(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<UINT_64 BASE,bool is_carry=true,ZZT T>
AXC void abs_mul_num(QC T in[],T num,T out[],E len)
{
len=ary_true_len(in,len);
num%=BASE;
UINT_64 prod=0;
if(num==1)
{
ary_copy(out,in,len);
}
else
{
for(E i=0;i<len;i++)
{
prod+=static_cast<UINT_64>(in[i])*num;
std::tie(prod,out[i])=div_mod<UINT_64>(prod,BASE);
}
}
if(is_carry)
{
out[len]=prod;
}
}
AXT<UINT_64 BASE,ZZT T>
AXC INT_64 abs_div_num(QC T in[],T num,T out[],E len)
{
E pos=ary_true_len(in,len);
num%=BASE;
if(num==1)
{
ary_copy(out,in,len);
ZZR 0;
}
UINT_64 last_rem=0;
while(pos>0)
{
pos--;
last_rem=last_rem*BASE+in[pos];
std::tie(out[pos],last_rem)=div_mod<UINT_64>(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[],
E len1,E len2)
{
if(len1<len2)
{
std::swap(in1,in2);
std::swap(len1,len2);
}
E pos=0;
UINT_64 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[],
E len1,E len2)
{
if(len1<len2)
{
ZZR;
}
E pos=0;
INT_64 borrow=0;
while(pos<len2)
{
borrow+=(static_cast<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<UINT_64 BASE,ZZT T>
void fft_mul_old(QC T in1[],QC T in2[],T out[],
E len1,E len2)
{
using namespace hint_transform;
if(len1==0||len2==0||in1==nullptr||in2==nullptr)
{
ZZR;
}
QC E conv_res_len=len1+len2-1;
QC E azE=min_2pow(conv_res_len);
ZZS Z*fft_buf=nullptr;ZZS E fft_cap=0;
if(fft_cap<azE){free(fft_buf);fft_buf=(Z*)malloc(azE*arZ(Z));fft_cap=azE;}
Z*fft_ary=fft_buf;
{E mnz=len1<len2?len1:len2;
memset((char*)(fft_ary+mnz),0,(azE-mnz)*arZ(Z));}
com_ary_combine_copy(fft_ary,in1,len1,in2,len2);
fft_dif(fft_ary,azE,false);
ZZD inv= -1/(2.0*azE);
for(E i=0;i<azE;i++)
{
Z tmp=fft_ary[i];
fft_ary[i]=std::conj(tmp*tmp*inv);
}
fft_dit(fft_ary,azE,false);
hint::UINT_64 carry=0;
for(E i=0;i<conv_res_len;i++)
{
carry+=static_cast<hint::UINT_64>(fft_ary[i].imag()+0.5);
std::tie(carry,out[i])=div_mod<UINT_64>(carry,BASE);
}
out[conv_res_len]=carry%BASE;
}
AXT<ZZT T>
ZZS QI void limbs_to_double(ZZD*dst,QC T*src,E n)
{
E i=0;
if AXC(arZ(T)==4)
{
for(;i+8<=n;i+=8)
{
arV v=_mm256_loadu_si256((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(_mm256_mul_pd(x,inv));
ZZV q2=_mm256_floor_pd(_mm256_mul_pd(q1,inv));
ZZV q3=_mm256_floor_pd(_mm256_mul_pd(q2,inv));
__m128i r0=_mm256_cvttpd_epi32(_mm256_sub_pd(x,_mm256_mul_pd(q1,base)));
__m128i r1=_mm256_cvttpd_epi32(_mm256_sub_pd(q1,_mm256_mul_pd(q2,base)));
__m128i r2=_mm256_cvttpd_epi32(_mm256_sub_pd(q2,_mm256_mul_pd(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,E count){
__m128i p1=_mm_setzero_si128(),p2=p1,p3=p1;
for(E 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;E i=0;
for(;i+8<=count+1;i+=8){
arV s=_mm256_loadu_si256((QC arV*)(out+i));
arV q=_mm256_sub_epi32(zero,_mm256_add_epi32(_mm256_add_epi32(_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=_mm256_add_epi32(_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(_mm256_add_epi32(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<UINT_64 BASE,ZZT T>
void fft_mul(QC T in1[],QC T in2[],T out[],E len1,E len2){
if(!len1||!len2||!in1||!in2)ZZR;
QC E conv=len1+len2-1;
if AXC(BASE==10000&&arZ(T)==4){if(len1*len2<=65536){
QC T*aa=in1,*bb=in2;E na=len1,nb=len2;if(na>nb){std::swap(aa,bb);std::swap(na,nb);}
ZZS ARU*bp=nullptr,*ap=nullptr,*tmp=nullptr;ZZS E bc=0,ac=0,tc=0;
QC E 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(E 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(E 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;E m=0;
for(;m+16<=conv;m+=16){
ARL sums[16]={};QC E lo=m>=nb-1?m-(nb-1):0,hi=std::min(na-1,m+15);
for(E i0=lo&~E(1);i0<=hi;i0+=40){
QC E end=std::min(hi+1,i0+40);arV s0=_mm256_setzero_si256(),s1=s0;
for(E i=i0;i<end;i+=2){arV av=az06(ap[i/2]);QC ARU*p=packed+ptrdiff_t(m)-ptrdiff_t(i);
s0=_mm256_add_epi32(s0,_mm256_madd_epi16(av,_mm256_loadu_si256((QC arV*)p)));
s1=_mm256_add_epi32(s1,_mm256_madd_epi16(av,_mm256_loadu_si256((QC arV*)(p+8))));}
_mm256_storeu_si256((arV*)sums,_mm256_add_epi64(_mm256_loadu_si256((QC arV*)sums),_mm256_cvtepu32_epi64(_mm256_castsi256_si128(s0))));
_mm256_storeu_si256((arV*)(sums+4),_mm256_add_epi64(_mm256_loadu_si256((QC arV*)(sums+4)),_mm256_cvtepu32_epi64(_mm256_extracti128_si256(s0,1))));
_mm256_storeu_si256((arV*)(sums+8),_mm256_add_epi64(_mm256_loadu_si256((QC arV*)(sums+8)),_mm256_cvtepu32_epi64(_mm256_castsi256_si128(s1))));
_mm256_storeu_si256((arV*)(sums+12),_mm256_add_epi64(_mm256_loadu_si256((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 E lo=m>=nb-1?m-(nb-1):0,hi=std::min(na-1,m);for(E 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;}
const E n=hintpowfft::int_ceil2(conv);
ZZS ZZD*g_abuf=nullptr,*g_bbuf=nullptr;ZZS E 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));
limbs_to_double(a,in1,len1);
if(in1==in2&&len1==len2){
hintpowfft::transform::fft::FFTAVX::difRecLong<true>(a,n);
hintpowfft::transform::fft::real_dot_binrev4(a,a,n);
hintpowfft::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));
limbs_to_double(b,in2,len2);
hintpowfft::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;}}UINT_64 carry=0;
for(E i=0;i<conv;++i){carry+=coeff[i];out[i]=carry%BASE;carry/=BASE;}
out[conv]=carry%BASE;
}
AXT<UINT_64 BASE,ZZT T>
AXC T divisor_normalize(QC T in[],T out[],E 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<UINT_64 BASE,ZZT T>
void abs_long_div(T az05[],QC T divisor[],T quot[],
E len1,E len2)
{
len1=ary_true_len(az05,len1);
len2=ary_true_len(divisor,len2);
if(divisor==nullptr||len2==0)
{
throw("Can't divide by zero\n");
}
if(az05==nullptr||len1==0)
{
ZZR;
}
if(abs_compare(az05,divisor,len1,len2)<0)
{
ZZR;
}
if(len2==1)
{
T rem=abs_div_num<BASE>(az05,divisor[0],quot,len1);
az05[0]=rem;
ZZR;
}
if(divisor[len2-1]<(BASE/2))
{
throw("Can't call this proc before normalize the divisor\n");
}
quot[len1-len2]=0;
QC UINT_64 divisor_2digits=BASE*divisor[len2-1]+divisor[len2-2];
hintvector<T>sub(len2+1);
while(abs_compare(az05,divisor,len1,len2)>=0)
{
sub.az03(len2+1);
UINT_64 dividend_2digits=az05[len1-1]*BASE+az05[len1-2];
T quo_digit=0;
E shift=len1-len2;
if(dividend_2digits>divisor_2digits)
{
quo_digit=dividend_2digits/divisor_2digits;
abs_mul_num<BASE>(divisor,quo_digit,sub.data(),len2);
sub.set_true_len();
E sub_len=sub.length();
if(abs_compare(az05+shift,sub.data(),len1-shift,sub_len)<0)
{
quo_digit--;
abs_sub<BASE>(sub.data(),divisor,sub.data(),sub_len,len2);
}
}
else if(dividend_2digits==divisor_2digits)
{
if(abs_compare(az05+shift,divisor,len1-shift,len2)<0)
{
quo_digit=BASE-1;
shift--;
abs_mul_num<BASE>(divisor,quo_digit,sub.data(),len2);
}
else
{
quo_digit=1;
ary_copy(sub.data(),divisor,len2);
sub.set_true_len();
}
}
else
{
quo_digit=dividend_2digits/(divisor_2digits/BASE);
if(quo_digit>=BASE)
{
quo_digit=BASE-1;
}
shift--;
abs_mul_num<BASE>(divisor,quo_digit,sub.data(),len2);
sub.set_true_len();
E sub_len=sub.length();
if(abs_compare(az05+shift,sub.data(),len1-shift,sub_len)<0)
{
quo_digit--;
abs_sub<BASE>(sub.data(),divisor,sub.data(),sub_len,len2);
if(abs_compare(az05+shift,sub.data(),len1-shift,sub_len)<0)
{
quo_digit--;
abs_sub<BASE>(sub.data(),divisor,sub.data(),sub_len,len2);
}
}
}
abs_sub<BASE>(az05+shift,sub.data(),az05+shift,len1-shift,sub.length());
len1=ary_true_len(az05,len1);
quot[shift]=quo_digit;
}
}
AXT<UINT_64 BASE,ZZT T>
void abs_rec_div(T az05[],T divisor[],hintvector<T> &quot,
E len1,E len2)
{
len1=ary_true_len(az05,len1);
len2=ary_true_len(divisor,len2);
if(divisor==nullptr||len2==0)
{
throw("Can't divide by zero\n");
}
if(az05==nullptr||len1==0)
{
ZZR;
}
if(abs_compare(az05,divisor,len1,len2)<0)
{
ZZR;
}
if(divisor[len2-1]<(BASE/2))
{
throw("Can't call this proc before normalize the divisor\n");
}
E quot_len=len1-len2+1;
quot.az03(quot_len);
AXC E LONG_DIV_THRESHOLD=50;
if(len2<=LONG_DIV_THRESHOLD)
{
abs_long_div<BASE>(az05,divisor,quot.data(),len1,len2);
}
else if(len1>=len2*2||len1>((len2+1)/2)*3)
{
E base_len=(len1+3)/4;
E quot_tmp_len=base_len*3-len2+2;
hintvector<T>quot_tmp(quot_tmp_len,0);
abs_rec_div<BASE>(az05+base_len,divisor,quot_tmp,len1-base_len,len2);
quot_tmp_len=quot_tmp.set_true_len();
E dividend_len=ary_true_len(az05,len1);
abs_rec_div<BASE>(az05,divisor,quot,dividend_len,len2);
quot.az03(quot_len);
quot_len=quot.set_true_len();
abs_add<BASE>(quot.data()+base_len,quot_tmp.data(),quot.data()+base_len,quot_len-base_len,quot_tmp_len);
quot.az03(len1-len2+1);
}
else
{
E base_len=len2/2;
abs_rec_div<BASE>(az05+base_len,divisor+base_len,quot,len1-base_len,len2-base_len);
AXC T ONE[1]={1};
quot_len=quot.set_true_len();
hintvector<T>prod(base_len+quot_len,0);
fft_mul<BASE>(divisor,quot.data(),prod.data(),base_len,quot_len);
E prod_len=prod.set_true_len();
len1=ary_true_len(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(),divisor,prod.data(),prod_len,base_len);
abs_add<BASE>(az05+base_len,divisor+base_len,az05+base_len,len1-base_len,len2-base_len);
quot_len=quot.set_true_len();
prod_len=prod.set_true_len();
len1=ary_true_len(az05,std::max(len1,len2)+1);
}
abs_sub<BASE>(az05,prod.data(),az05,len1,prod_len);
}
}
AXT<UINT_64 BASE,ZZT T>
hintvector<T>abs_div(QC T az05[],T divisor[],hintvector<T> &quot,
E len1,E len2,bool ret_rem=true)
{
hintvector<T>normalized_divisor(len2);
normalized_divisor.az03(len2);
hintvector<T>normalized_dividend(len1+1);
normalized_dividend.az03(len1+1);
T*divisor_ptr=normalized_divisor.data();
T*dividend_ptr=normalized_dividend.data();
T multiplier=divisor_normalize<BASE>(divisor,divisor_ptr,len2);
abs_mul_num<BASE>(az05,multiplier,dividend_ptr,len1);
len1=normalized_dividend.set_true_len();
quot=hintvector<T>(len1-len2+2,0);
if((!ret_rem)&&(len1+2<len2*2))
{
E shift=len2*2-len1-2;
abs_rec_div<BASE>(dividend_ptr+shift,divisor_ptr+shift,quot,len1-shift,len2-shift);
quot.set_true_len();
ZZR normalized_dividend;
}
abs_rec_div<BASE>(dividend_ptr,divisor_ptr,quot,len1,len2);
quot.set_true_len();
if(ret_rem)
{
len1=normalized_dividend.set_true_len();
abs_div_num<BASE>(dividend_ptr,multiplier,dividend_ptr,len1);
normalized_dividend.set_true_len();
}
ZZR normalized_dividend;
}}
#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::E n){ZZR static_cast<T*>(LP648::get(n*arZ(T)));}
void deallocate(T*p,std::E n)arN{LP648::put(p,n*arZ(T));}
AXT<class U>void construct(U*p){::new(static_cast<void*>(p))U;}
AXT<class U,class...A>void construct(U*p,A&&...a){::new(static_cast<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(E 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;E 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(E 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 static_cast<QC Big&>(*this)+b;
if(b.zero())ZZR std::move(*this);
if(zero())ZZR b;
E n=std::max(v.size(),b.v.size());v.resize(n,0);
QO carry=0;E 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(E 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(E 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(E 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(E i=0;i<v.size();++i)for(E j=0;j<b.v.size();++j)cc[i+j]+=aa[i]*bb[j];
ARU carry=0;for(E 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::HintVector<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(E 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(E 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);E 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;iv586w q={{(arW)q0,(arW)(q0>>64),0,0}},t={{(arW)t0,(arW)(t0>>64),0,0}};arU k=a+6;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(E 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(E 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=nullptr;ZZS E g_vcap=0;
ZZS ARU*vmul(QC ARU*a,E la,QC ARU*b,E lb,E&outlen){
QC E 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){E n=v.size();while(n>1&&v[n-1]==0)--n;v.resize(n);}
ZZS ZZD*ar_nr[2]={nullptr,nullptr};ZZS E ar_nr_cap=0;
ZZS void ar_nr_prepare(QC ARU*r,E lr,E 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::limbs_to_double(ar_nr[0],r,lr);memset(ar_nr[0]+lr,0,(n-lr)*8);
hintpowfft::transform::fft::FFTAVX::difRecLong<true>(ar_nr[0],n);
}
ZZS ARU*ar_nr_product(QC ARU*a,E la,E lr,E n,E&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::limbs_to_double(ar_nr[1],a,la);memset(ar_nr[1]+la,0,(n-la)*8);
using namespace hintpowfft::transform::fft;
FFTAVX::difRecLong<true>(ar_nr[1],n);real_dot_binrev4(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;E conv=la+lr-1;
for(E 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,
E L){
QC ARU*Q=Qv.data();QC E nq=Qv.size();
QC E M0=3;
long ZZD qk=0,scale=1;
for(int i=0;i<8&&(E)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);
E M=M0;
for(int iter=0;iter<80;++iter){
QC E quse=(nq<2*M)?nq:2*M;
QC ARU*Dq=Q+(nq-quse);
QC E lr=R.size();
QC E ar_n=hintpowfft::int_ceil2(quse+lr-1);bool ar_keep=ar_n>=4096;if(ar_keep)ar_nr_prepare(R.data(),lr,ar_n);
E plen;ARU*P=ar_keep?ar_nr_product(Dq,quse,lr,ar_n,plen):vmul(Dq,quse,R.data(),lr,plen);
QC E fpow=M+quse;
E flen=(plen>fpow+2)?plen:fpow+2;
std::vector<ARU>F(flen+1,0);
F[fpow]=1;
int borrow=0;
for(E 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(E 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 E p=(fpow>F.size())?(fpow-F.size()):0;
if(M>=L&&p+6>=L)break;
E M2=(2*M<L)?2*M:L;
if(M2<=M)M2=2*M;
if(M<8192){E r=M+M/2+1;if(r<M2)M2=r;}
else{E w=1;while(w*2<=M2)w*=2;if(w>M)M2=w;}
QC E sh=quse;
std::vector<ARU>Rn(M+lr+((F.size()>lr)?F.size():lr)+3,0);
for(E i=0;i<lr;++i)Rn[M+i]=R[i];
if(F.size()>1||F[0]){
E glen;ARU*G=(ar_keep&&hintpowfft::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);
E 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){
E drop=M-L;
if(R.size()>drop)R.erase(R.begin(),R.begin()+drop);else{R.assign(1,0);}
vtrim(R);
}
E plen;ARU*P=vmul(Tv.data(),Tv.size(),R.data(),R.size(),plen);
E slen=plen>nq?plen-nq:0;
std::vector<ARU>S(L+3,0);
for(E i=0;i<slen&&i<L+3;++i)S[i]=P[nq+i];
S[L]+=1;
for(E 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()<=E(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){
E oa=A.v.size(),ob=B.v.size(),oc=C.v.size();if(oa<2||ob<2||oc<2)ZZR 0;
E za=0,zb=0,zc=0;while(A.v[za]==0)++za;while(B.v[zb]==0)++zb;while(C.v[zc]==0)++zc;
E la=oa-za,lb=ob-zb,lc=oc-zc;
if(la<2||lb<2||lc<2)ZZR 0;
E c1=la+lc-1,c2=lb+lc-1;
if(c1<4096||c2<4096||la*lc<=65536||lb*lc<=65536)ZZR 0;
E n=hintpowfft::int_ceil2(c1);if(hintpowfft::int_ceil2(c2)!=n)ZZR 0;
ZZS ZZD*F3[3]={0,0,0};ZZS E 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::limbs_to_double(a,A.v.data()+za,la);
memset(b+lb,0,(n-lb)*8);hint_arithm::limbs_to_double(b,B.v.data()+zb,lb);
memset(d+lc,0,(n-lc)*8);hint_arithm::limbs_to_double(d,C.v.data()+zc,lc);
using hintpowfft::transform::fft::FFTAVX;using hintpowfft::transform::fft::real_dot_binrev4;
FFTAVX::difRecLong<true>(d,n);
FFTAVX::difRecLong<true>(a,n);real_dot_binrev4(a,d,n);FFTAVX::iditRecLong<true,true>(a,n);
FFTAVX::difRecLong<true>(b,n);real_dot_binrev4(b,d,n);FFTAVX::iditRecLong<true,true>(b,n);
E 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(E i=0;i<c1;i++){k+=((QC ARL*)a)[i];p[i]=k%10000;k/=10000;}p[c1]=k%10000;
k=0;for(E 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);}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1389.493 ms140 MB + 652 KBAcceptedScore: 100


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