提交记录 166351


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_codex61s_agg5 1020a. 测测你的自然常数2 Accepted 100 399.829 ms 148636 KB C++17 99.86 KB
提交时间 评测时间
2026-11-17 09:19:35 2026-11-17 09:19:42
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/166157:完整3M e六项宽叶直接种子/递推/内存池及全部继承来源、勘误与HintFFT MIT声明保留如下。saffah_codex61s_agg5 https://duck.ac/submission/165852:独立118bit精确倒数;saffah_v41f1017_agg4 https://duck.ac/submission/165961:小realFFT调度思路。
Approach / 思路: 保留当前3M专用叶界与六项直接种子,结合已独立600万例精确证明的两乘118bit除法,并将1025..4095系数卷积路由至补零4096的AVX实数FFT;完整其他范围/精度/符号回退不变。
Experiment purpose / 试验目的: GCC9全部3M字符与输出保护对独立GMP逐字后立即官网;本地性能不作过滤。
*/
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/166157:完整算术引擎及全部原归属/勘误/HintFFT MIT保留。saffah_codex61s_agg5 https://duck.ac/submission/165852:独立118bit倒数;https://duck.ac/submission/165619:完整128bit回退。 Approach / 思路: x<2^118使用高字为1的精确倒数,两次64bit乘法和一次余数修正;其余输入完整回退,全部叶界/精度不变。 Experiment purpose / 试验目的: 已有600万例独立商余核验,再全请求GMP字符/保护后官网;本地速度不作过滤。 */
/* 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. */
/* 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. */
/* 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. */
/* */
#define arK constexpr
#define arW uint64_t
#define arD uint32_t
#define arN noexcept
#define arI inline
#define arR return
#define arS static
#define arU unsigned
#define arB __uint128_t
#define arV __m256i
#define arZ sizeof
#define arY size_t
#define arT template
#define azA SIZE_TYPE
#define azB fft_split_radix_dit_template
#define azC fft_split_radix_dif_template
#define azD fft_2point
#define azE fft_len
#define ARU arD
#define ARL arW
#define ARW arB
#define ARS arY
#define AXC arK
#define AXZ Complex
#define AXT arT
#define QZ arY
#define QY arW
#define QX arD
#define QO arU
#define QC const
#define QI arI
#define ZZD double
#define ZZS arS
#define ZZV __m256d
#define ZZW arB
#define ZZT typename
#define ZZR arR
#include <bits/stdc++.h>
#include <x86intrin.h>
#pragma GCC optimize("O3")
// Adapted from https://duck.ac/submission/47426 (TSKY), HintFFT MIT.
// Full attribution and complete MIT notice are retained in the leading reference block.
AXC auto statement="Do NOT modify this statement! "
"https://github.com/With-Sky/HintFFT "
"TSKY (WithSky)";
#include <complex>
#include <iostream>
#include <type_traits>
#include <cstdint>
#include <climits>
#include <cstring>
#include <immintrin.h>
#pragma GCC target("avx2,fma")
namespace hintpowfft
{
AXT<ZZT T,ARS ALIGN=64>
class AlignMem{
public:
using Ptr=T*;
using ConstPtr=QC T*;
~AlignMem(){
if(ptr){
_mm_free(ptr);}};
AlignMem():ptr(nullptr),len(0){}
AlignMem(ARS n):ptr(reinterpret_cast<Ptr>(_mm_malloc(n*arZ(T),ALIGN))),len(n){}
AlignMem(QC AlignMem&)=delete;
AlignMem&operator=(QC AlignMem&)=delete;
T&operator[](ARS i){
ZZR ptr[i];}
QC T&operator[](ARS i)QC{
ZZR ptr[i];}
Ptr begin(){
ZZR ptr;}
Ptr end(){
ZZR ptr+len;}
ConstPtr begin()QC{
ZZR ptr;}
ConstPtr end()QC{
ZZR ptr+len;}
ARS size()QC{
ZZR len;}
private:
T*ptr;
ARS len;};
AXT<ZZT YMM>
QI void transpose64_2X4(YMM&row0,YMM&row1){
auto t0=_mm256_unpacklo_pd(ZZV(row0),ZZV(row1));
auto t1=_mm256_unpackhi_pd(ZZV(row0),ZZV(row1));
row0=YMM(_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 operator+(QC F64X4&other)QC{
ZZR _mm256_add_pd(data,other.data);}
F64X4 operator-(QC F64X4&other)QC{
ZZR _mm256_sub_pd(data,other.data);}
F64X4 operator*(QC F64X4&other)QC{
ZZR _mm256_mul_pd(data,other.data);}
F64X4 operator/(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);}
operator 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 operator+(QC C64X4&other)QC{
ZZR C64X4(real+other.real,imag+other.imag);}
C64X4 operator-(QC C64X4&other)QC{
ZZR C64X4(real-other.real,imag-other.imag);}
C64X4 operator*(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(reinterpret_cast<QC F64*>(p));
imag.load(reinterpret_cast<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(reinterpret_cast<F64*>(p));
imag.store(reinterpret_cast<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,ARS OMEGA_LEN>
class TableFix{
alignas(64)Float table[OMEGA_LEN*2];
public:
TableFix(ARS theta_divider,ARS factor,ARS stride){
QC Float theta= -HINT_2PI*factor/theta_divider;
for(ARS begin=0,index=0;begin<OMEGA_LEN*2;begin+=stride*2)
{
for(ARS j=0;j<stride;j++,index++)
{
table[begin+j]=std::cos(theta*index);
table[begin+j+stride]=std::sin(theta*index);}}}
AXC QC Float&operator[](ARS index)QC{
ZZR table[index];}};
void initOmegaX4(F64*arr,ARS azE,int table_len,int factor){
table_len/=4;
QC F64 theta= -HINT_2PI*factor/azE;
auto arrx4=reinterpret_cast<C64X4*>(arr);
arr[0]=1,arr[4]=0;
arr[1]=std::cos(theta),arr[5]=std::sin(theta);
arr[2]=std::cos(theta*2),arr[6]=std::sin(theta*2);
arr[3]=std::cos(theta*3),arr[7]=std::sin(theta*3);
for(ARS begin=1;begin<table_len;begin*=2){
ARS nth=begin*4;
C64X4 unit;
unit.set1(std::cos(theta*nth),std::sin(theta*nth));
for(ARS i=0;i<begin;i++)
{
arrx4[begin+i]=arrx4[i].mul(unit);}}}
AXT<ZZT Float,int LOG_BEGIN,int LOG_END,int DIV>
class TableFixMulti{
static_assert(LOG_END>=LOG_BEGIN);
static_assert(is_2pow(DIV));
ZZS AXC ARS TABLE_CPX_LEN=(ARS(1)<<(LOG_END+1))/DIV;
alignas(64)Float table[TABLE_CPX_LEN*2];
public:
TableFixMulti(ARS factor,ARS stride=4){
initBottomUp(factor,stride);}
void initBottomUp(ARS factor,ARS stride){
static_assert(std::is_same<Float,Float64>::value);
ARS len=ARS(1)<<LOG_BEGIN,cpx_len=len/DIV;
auto it=getBeginLog(LOG_BEGIN);
initOmegaX4(it,len,cpx_len,factor);
for(int log_len=LOG_BEGIN+1;log_len<=LOG_END;log_len++)
{
len=ARS(1)<<log_len,cpx_len=len/DIV;
Float theta= -HINT_2PI*factor/len;
auto it=getBeginLog(log_len),it_last=getBeginLog(log_len-1);
C64X4 unit(std::cos(theta),std::sin(theta));
for(auto end=it+cpx_len*2;it<end;it+=16,it_last+=8)
{
C64X4 omega0,omega1;
omega0.load(it_last);
omega1=omega0.mul(unit);
transpose64_2X4(omega0.real,omega1.real);
transpose64_2X4(omega0.imag,omega1.imag);
omega0.store(it),omega1.store(it+8);}}}
AXC QC Float*getBeginLog(int log_rank)QC{
ZZR getBegin(ARS(1)<<log_rank);}
AXC Float*getBeginLog(int log_rank){
ZZR getBegin(ARS(1)<<log_rank);}
AXC QC Float*getBegin(ARS rank)QC{
ZZR&table[rank*2/DIV];}
AXC Float*getBegin(ARS rank){
ZZR&table[rank*2/DIV];}};
AXT<int CACHE_LOG_LEN>
class FFTSqrtTableC64X4{
public:
using F64=ZZD;
using C64=std::complex<ZZD>;
using C64X4=hintpowfft::Complex64X4;
ZZS AXC ARS CACHE_LEN=ARS(1)<<CACHE_LOG_LEN;
ZZS AXC ARS MASK=CACHE_LEN-1;
ZZS AXC ARS C4_COUNT=arZ(C64X4)/arZ(C64);
~FFTSqrtTableC64X4(){
if(high)
{
delete[]high;}}
FFTSqrtTableC64X4(){}
FFTSqrtTableC64X4(ARS azE,int len_div,int factor){
init(azE,len_div,factor);}
void init(ARS azE,int len_div,int factor){
ARS table_len=azE/len_div;
ARS low_len=CACHE_LEN*C4_COUNT,high_len=table_len/low_len;
if(high!=nullptr)
{
delete[]high;}
high=new C64[high_len];
auto p=reinterpret_cast<F64*>(&low[0]);
initOmegaX4(p,azE,low_len,factor);
QC F64 theta= -HINT_2PI*factor/azE;
high[0]=C64(1,0);
for(ARS begin=1;begin<high_len;begin*=2)
{
C64 unit=std::polar<F64>(1.0,theta*begin*low_len);
for(ARS i=0;i<begin;i++)
{
high[i+begin]=high[i]*unit;}}}
C64X4 operator[](ARS i)QC{
C64X4 hi;
auto p=reinterpret_cast<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 ARS SHORT_LEN=ARS(1)<<LOG_BEGIN;
ZZS AXC ARS TABLE_LEN=LOG_MAX-LOG_BEGIN+1;
public:
FFTTableSqrt(int factor){
for(int i=0;i<TABLE_LEN;i++)
{
ARS azE=SHORT_LEN<<i;
table[i].init(azE,DIV,factor);}}
QC TableLong&operator[](int log_len)QC{
log_len-=LOG_BEGIN;
ZZR table[log_len];}
TableLong&operator[](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=10,LOG_MID=25-crc32(statement)%15,LOG_MAX=27,LOG_CACHE=7;
ZZS AXC ARS SHORT_LEN=ARS(1)<<LOG_SHORT,MID_LEN=ARS(1)<<LOG_MID,MAX_LEN=ARS(1)<<LOG_MAX;
using TableFix4=QC TableFix<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=reinterpret_cast<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=reinterpret_cast<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=reinterpret_cast<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=reinterpret_cast<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[],ARS float_len,F32&&func32,F16&&func16){
if(hint_log2(float_len/2)%2==0)
{
for(auto end=in_out+float_len;in_out<end;in_out+=32)
{
func16(in_out);}}
else
{
for(auto end=in_out+float_len;in_out<end;in_out+=64)
{
func32(in_out);}}}
ZZS void difIter(Float64 in_out[],ARS float_len){
ARS azE=float_len/2;
C64X4 c0,c1,c2,c3;
ARS stride=azE/2;
auto it0=in_out,it1=it0+stride,it2=it1+stride,it3=it2+stride;
for(ARS rank=azE;rank>=64;rank/=4)
{
stride=rank/2;
for(auto begin=in_out,end=in_out+float_len;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,float_len,dif32,dif16);}
ZZS void iditIter(Float64 in_out[],ARS float_len){
ARS azE=float_len/2;
ARS rank=hint_log2(azE)%2==0?64:128;
fftTiny(in_out,float_len,idit32,idit16);
for(;rank<=azE;rank*=4)
{
QC ARS stride=rank/2;
for(auto begin=in_out,end=in_out+float_len;begin<end;begin+=rank*2)
{
auto table1=multi_table_2.getBegin(rank*2),table2=multi_table_2.getBegin(rank),table3=multi_table_3.getBegin(rank);
auto it0=begin,it1=it0+stride,it2=it1+stride,it3=it2+stride;
for(;it0<begin+stride;it0+=8,it1+=8,it2+=8,it3+=8,table1+=8,table2+=8,table3+=8)
{
C64X4 c0=it0,c1=it1,c2=it2,c3=it3;
c1=c1.mulConj(C64X4(table2)),c2=c2.mulConj(C64X4(table1)),c3=c3.mulConj(C64X4(table3));
idit4(c0.real,c0.imag,c1.real,c1.imag,c2.real,c2.imag,c3.real,c3.imag);
c0.store(it0),c1.store(it1),c2.store(it2),c3.store(it3);
}}}}
#define difLayer(dif_func, in_out, stride, table) \
do \
{ \
auto it0 = in_out, it1 = in_out + stride, it2 = it1 + stride, it3 = it2 + stride; \
ARS indx = 0; \
for (auto end = it1; 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; \
ARS indx = 0; \
for (auto end = it1; it0 < end; it0 += 8, it1 += 8, it2 += 8, it3 += 8, indx++) \
{ \
C64X4 c0 = it0, c1 = it1, c2 = it2, c3 = it3, omega1, omega2; \
omega1 = table[indx], c2 = c2.mulConj(omega1); \
omega2 = omega1.mul(omega1), c1 = c1.mulConj(omega2); \
c3 = c3.mulConj(omega2.mul(omega1)); \
idit4(c0.real, c0.imag, c1.real, c1.imag, c2.real, c2.imag, c3.real, c3.imag); \
c0 = c0.transToI64(ToI64{}), c1 = c1.transToI64(ToI64{}), c2 = c2.transToI64(ToI64{}), c3 = c3.transToI64(ToI64{}); \
c0.store(it0, ToRIRI{}), c1.store(it1, ToRIRI{}), c2.store(it2, ToRIRI{}), c3.store(it3, ToRIRI{}); \
} \
} while (0)
AXT<bool FROM_RIRI_PERM=false>
ZZS void difRecMid(Float64 in_out[],ARS float_len){
QC ARS azE=float_len/2;
if(azE<=SHORT_LEN)
{
difIter(in_out,float_len);
ZZR;}
using FromRIRI=std::integral_constant<bool,FROM_RIRI_PERM>;
auto table1=reinterpret_cast<QC C64X4*>(multi_table_1.getBegin(azE));
QC ARS stride=float_len/4;
difLayer(difRecMid,in_out,stride,table1);}
AXT<bool TO_RIRI_PERM=false,bool TO_INT64=false>
ZZS void iditRecMid(Float64 in_out[],ARS float_len){
QC ARS azE=float_len/2;
if(azE<=SHORT_LEN)
{
iditIter(in_out,float_len);
ZZR;}
using ToRIRI=std::integral_constant<bool,TO_RIRI_PERM>;
using ToI64=std::integral_constant<bool,TO_INT64>;
QC ARS stride=float_len/4;
auto table1=reinterpret_cast<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[],ARS float_len){
QC ARS azE=float_len/2;
if(azE<=MID_LEN)
{
difRecMid<FROM_RIRI_PERM>(in_out,float_len);
ZZR;}
using FromRIRI=std::integral_constant<bool,FROM_RIRI_PERM>;
QC auto&table1=sqrt_table_1[hint_log2(azE)];
QC ARS stride=float_len/4;
difLayer(difRecLong,in_out,stride,table1);}
AXT<bool TO_RIRI_PERM=false,bool TO_INT64=false>
ZZS void iditRecLong(Float64 in_out[],ARS float_len){
QC ARS azE=float_len/2;
if(azE<=MID_LEN)
{
iditRecMid<TO_RIRI_PERM,TO_INT64>(in_out,float_len);
ZZR;}
using ToRIRI=std::integral_constant<bool,TO_RIRI_PERM>;
using ToI64=std::integral_constant<bool,TO_INT64>;
QC ARS stride=float_len/4;
QC auto&table1=sqrt_table_1[hint_log2(azE)];
iditLayer(iditRecLong,in_out,stride,table1);}};
#undef difLayer
#undef iditLayer
AXC int FFTAVX::LOG_SHORT,FFTAVX::LOG_MID,FFTAVX::LOG_MAX,FFTAVX::LOG_CACHE;
AXC ARS FFTAVX::SHORT_LEN,FFTAVX::MID_LEN,FFTAVX::MAX_LEN;
FFTAVX::TableFix4 FFTAVX::table_8(8,1,4),FFTAVX::table_16_1(16,1,4),FFTAVX::table_16_3(16,3,4);
FFTAVX::TableFix8 FFTAVX::table_32_1(32,1,4),FFTAVX::table_32_3(32,3,4);
FFTAVX::TableMulti2 FFTAVX::multi_table_2(2);
FFTAVX::TableMulti3 FFTAVX::multi_table_3(3);
FFTAVX::TableMulti1 FFTAVX::multi_table_1(1);
FFTAVX::TableSqrt FFTAVX::sqrt_table_1(1);
AXC ARU bitrev32(ARU n){
AXC ARU mask55=0x55555555;
AXC ARU mask33=0x33333333;
AXC ARU mask0f=0x0f0f0f0f;
AXC ARU maskff=0x00ff00ff;
n=((n&mask55)<<1)|((n>>1)&mask55);
n=((n&mask33)<<2)|((n>>2)&mask33);
n=((n&mask0f)<<4)|((n>>4)&mask0f);
n=((n&maskff)<<8)|((n>>8)&maskff);
ZZR(n<<16)|(n>>16);}
AXC ARU bitrev(ARU n,int len){
ZZR bitrev32(n)>>(32-len);}
AXT<int MAX_LOG_LEN,int DIV>
class BinRevTableC64X4HP{
public:
ZZS AXC int LOG_BLOCK=2,BLOCK=1<<LOG_BLOCK;
ZZS AXC ARS MAX_LEN=ARS(1)<<MAX_LOG_LEN;
struct Unit{
C64 units[MAX_LOG_LEN]{};
F64 block[BLOCK*2]{};
Unit()
{
AXC F64 factor=F64(1)/DIV;
for(int i=0;i<MAX_LOG_LEN;i++)
{
units[i]=getOmega(ARS(1)<<(i+1),1,factor);}
block[0]=1,block[BLOCK]=0;
for(int i=1;i<BLOCK;i++)
{
C64 omega=getOmega(BLOCK,bitrev(i,LOG_BLOCK),factor);
block[i]=omega.real(),block[i+BLOCK]=omega.imag();}}};
BinRevTableC64X4HP():index(0),pop(0){
std::memcpy(table,unit_table.block,arZ(unit_table.block));}
void reset(ARS i=0){
if(i==0)
{
pop=0,index=i;
ZZR;}
pop=1,index=i/BLOCK;
int zero=__builtin_ctzll(index);
auto fp=reinterpret_cast<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=reinterpret_cast<QC F64*>(&unit_table.units[zero+2]);
unit4.load1(fp,fp+1);
pop-=zero;
table[pop+1]=table[pop].mul(unit4);
pop++;
ZZR res;}
ZZS C64 getOmega(ARS n,ARS index,F64 factor=1){
F64 theta= -HINT_2PI*index/n;
ZZR std::polar<F64>(1,theta*factor);}
private:
alignas(64)ZZS QC Unit unit_table;
alignas(64)C64X4 table[MAX_LOG_LEN];
ARS index;
int pop;
int log_max_iter,log_fft_len;};
AXT<int MAX_LOG_LEN,int DIV>
QC ZZT BinRevTableC64X4HP<MAX_LOG_LEN,DIV>::Unit BinRevTableC64X4HP<MAX_LOG_LEN,DIV>::unit_table;
AXT<ARS RI_DIFF=1,ZZT FloatTy>
QI void dot_rfft(FloatTy*inout0,FloatTy*inout1,QC FloatTy*in0,QC FloatTy*in1,
QC std::complex<FloatTy> &omega,QC FloatTy inv=1){
using AXZ=std::complex<FloatTy>;
auto addConj=[](AXZ c0,AXZ c1){ZZR AXZ(c0.real()+c1.real(),c0.imag()-c1.imag());};
AXZ x0(inout0[0],inout0[RI_DIFF]),x1(inout1[0],inout1[RI_DIFF]),
y0(in0[0],in0[RI_DIFF]),y1(in1[0],in1[RI_DIFF]);
auto t0=x0*y0,t1=x1*y1,xy0=addConj(x0,x1),xy1=addConj(y0,y1);
auto t2=xy0*xy1;
y1=addConj(t0,t1);
x1=(y1+y1-t2)*omega*omega;
QC auto inv2=inv+inv;
x0=(t2-x1)*inv,x1=AXZ(t0.real()-t1.real(),t0.imag()+t1.imag())*inv2;
AXZ out0=x0+x1,out1(x0.real()-x1.real(),x1.imag()-x0.imag());
inout0[0]=out0.real(),inout0[RI_DIFF]=out0.imag();
inout1[0]=out1.real(),inout1[RI_DIFF]=out1.imag();}
QI void dot_rfftX4(F64*inout0,F64*inout1,QC F64*in0,QC F64*in1,QC C64X4&omega,QC F64X4&inv){
auto addConj=[](QC C64X4&x0,QC C64X4&x1){
ZZR C64X4(x0.real+x1.real,x0.imag-x1.imag);};
C64X4 x0=inout0,x1=inout1,y0=in0,y1=in1;
x1=x1.reverse();
y1=y1.reverse();
C64X4 t0=x0.mul(y0),t1=x1.mul(y1);
C64X4 xy0=addConj(x0,x1),xy1=addConj(y0,y1);
C64X4 t2=xy0.mul(xy1);
y1=addConj(t0,t1);
x1=(y1+y1-t2).mul(omega);
QC F64X4 inv2=inv+inv;
x0=(t2-x1)*inv,x1=C64X4(t0.real-t1.real,t0.imag+t1.imag)*inv2;
C64X4 out0=x0+x1,out1(x0.real-x1.real,x1.imag-x0.imag);
out0.store(inout0),out1.reverse().store(inout1);}
QI void real_dot_binrev4(Float64 in_out[],Float64 in[],ARS float_len){
Float64 inv=2.0/float_len;{
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/float_len);
BinRevTableC64X4HP<28,1>table;
for(ARS begin=16;begin<float_len;begin*=2){
table.reset(begin/2);
auto it0=in_out+begin,it1=it0+begin-8,it2=in+begin,it3=it2+begin-8;
for(;it0<it1;it0+=8,it1-=8,it2+=8,it3-=8)
{
dot_rfftX4(it0,it1,it2,it3,table.iterate(),inv4);}}}
AXT<bool TO_INT=false>
QI void real_conv_avx(F64*in_out1,F64*in2,ARS float_len){
FFTAVX::difRecLong<true>(in_out1,float_len);
FFTAVX::difRecLong<true>(in2,float_len);
real_dot_binrev4(in_out1,in2,float_len);
FFTAVX::iditRecLong<true,TO_INT>(in_out1,float_len);}}}}
/*
MIT License
Copyright(c)2023 With-Sky
Permission is hereby granted,free of charge,to any person obtaining a copy
of this software and associated documentation files(the"Software"),to deal
in the Software without restriction,including without limitation the rights
to use,copy,modify,merge,publish,distribute,sublicense,and/or sell
copies of the Software,and to permit persons to whom the Software is
furnished to do so,subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED"AS IS",WITHOUT WARRANTY OF ANY KIND,EXPRESS OR
IMPLIED,INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,DAMAGES OR OTHER
LIABILITY,WHETHER IN AN ACTION OF CONTRACT,TORT OR OTHERWISE,ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/
#include <algorithm>
#include <atomic>
#include <complex>
#include <future>
#include <iostream>
#include <random>
#include <string>
#include <cstdlib>
#include <cstring>
#include <immintrin.h>
#ifndef HINT_SIMD_HPP
#define HINT_SIMD_HPP
#pragma GCC target("fma")
using AXZ=std::complex<ZZD>;
struct Complex2
{
ZZV data;
Complex2()
{
data=_mm256_setzero_pd();
}
Complex2(ZZD input)
{
data=_mm256_set1_pd(input);
}
Complex2(ZZV input)
{
data=input;
}
Complex2(QC Complex2&input)
{
data=input.data;
}
Complex2(ZZD QC*ptr)
{
data=_mm256_loadu_pd(ptr);
}
Complex2(AXZ a)
{
data=_mm256_broadcast_pd((__m128d*)&a);
}
Complex2(QC AXZ*ptr)
{
data=_mm256_loadu_pd((QC ZZD*)ptr);
}
void clr()
{
data=_mm256_setzero_pd();
}
void store(AXZ*a)QC
{
_mm256_storeu_pd((ZZD*)a,data);
}
AXT<int M>
Complex2 element_permute()QC
{
ZZR _mm256_permute_pd(data,M);
}
Complex2 all_real()QC
{
ZZR _mm256_movedup_pd(data);
}
Complex2 all_imag()QC
{
ZZR element_permute<0XF>();
}
Complex2 swap()QC
{
ZZR element_permute<0X5>();
}
Complex2 mul_neg_i()QC
{
ZZS QC ZZV subber{};
ZZR Complex2(_mm256_addsub_pd(subber,data)).swap();
}
Complex2 operator+(Complex2 input)QC
{
ZZR _mm256_add_pd(data,input.data);
}
Complex2 operator-(Complex2 input)QC
{
ZZR _mm256_sub_pd(data,input.data);
}
Complex2 operator*(Complex2 input)QC
{
auto imag=_mm256_mul_pd(all_imag().data,input.swap().data);
ZZR _mm256_fmaddsub_pd(all_real().data,input.data,imag);
}
Complex2 operator/(Complex2 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 AXZ=std::complex<ZZD>;
AXC ZZD HINT_PI=3.1415926535897932384626433832795;
AXC ZZD HINT_2PI=HINT_PI*2;
AXT<ZZT T>
AXC T min_2pow(T n)
{
T res=1;
while(res<n)
{
res*=2;
}
ZZR res;
}
AXT<ZZT T>
QI void ary_clr(T*ptr,ARS len)
{
memset(ptr,0,len*arZ(T));
}
AXT<ZZT T>
AXC bool is_neg(T x)
{
ZZR x<0;
}
AXT<ZZT T>
AXC ARS hint_log2(T n)
{
T res=0;
while(n>1)
{
n/=2;
res++;
}
ZZR res;
}
AXT<ZZT T>
AXC bool is_odd(T x)
{
ZZR 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,ARS len)
{
if(len==0||target==source)
{
ZZR;
}
if(len>=INT64_MAX)
{
throw("Ary too long\n");
}
std::memcpy(target,source,len*arZ(T));
}
AXT<ZZT T>
QI T*ary_realloc(T*ptr,ARS len)
{
if(len*arZ(T)<INT64_MAX)
{
ptr=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(AXZ*target,QC T&source1,ARS len1,QC T&source2,ARS len2)
{
ARS min_len=std::min(len1,len2);
ARS i=0;
while(i<min_len)
{
target[i]=AXZ(source1[i],source2[i]);
i++;
}
while(i<len1)
{
target[i].real(source1[i]);
i++;
}
while(i<len2)
{
target[i].imag(source2[i]);
i++;
}
}
namespace hint_transform
{
class ComplexTableY
{
private:
std::vector<std::vector<AXZ>>table1;
std::vector<std::vector<AXZ>>table3;
INT_32 max_log_size=2;
INT_32 cur_log_size=2;
ZZS AXC ARS FAC=1;
ComplexTableY(QC ComplexTableY&)=delete;
ComplexTableY&operator=(QC ComplexTableY&)=delete;
public:
~ComplexTableY(){}
ComplexTableY(UINT_32 max_shift)
{
max_shift=std::max<ARS>(max_shift,1);
max_log_size=max_shift;
table1.resize(max_shift+1);
table3.resize(max_shift+1);
table1[0]=table1[1]=table3[0]=table3[1]=std::vector<AXZ>{1};
table1[2]=table3[2]=std::vector<AXZ>{1};
#if TABLE_PRELOAD == 1
expand(max_shift);
#endif
}
void expand(INT_32 shift)
{
shift=std::max<INT_32>(shift,2);
if(shift>max_log_size)
{
throw("FFT length too long for lut\n");
}
for(INT_32 i=cur_log_size+1;i<=shift;i++)
{
ARS len=1ull<<i,vec_size=len*FAC/4;
table1[i].resize(vec_size);
table3[i].resize(vec_size);
table1[i][0]=table3[i][0]=AXZ(1,0);
for(ARS pos=0;pos<vec_size/2;pos++)
{
table1[i][pos*2]=table1[i-1][pos];
table3[i][pos*2]=table3[i-1][pos];
}
for(ARS pos=1;pos<vec_size/2;pos+=2)
{
ZZD cos_theta=std::cos(HINT_2PI*pos/len);
ZZD sin_theta=std::sin(HINT_2PI*pos/len);
table1[i][pos]=AXZ(cos_theta,-sin_theta);
table1[i][vec_size-pos]=AXZ(sin_theta,-cos_theta);
}
table1[i][vec_size/2]=std::conj(unit_root(8,1));
for(ARS pos=1;pos<vec_size/2;pos+=2)
{
AXZ tmp=get_omega(i,pos*3);
table3[i][pos]=tmp;
table3[i][vec_size-pos]=AXZ(tmp.imag(),tmp.real());
}
table3[i][vec_size/2]=std::conj(unit_root(8,3));
}
cur_log_size=std::max(cur_log_size,shift);
}
ZZS AXZ unit_root(ZZD theta)
{
ZZR std::polar<ZZD>(1.0,theta);
}
ZZS AXZ unit_root(ARS m,ARS n)
{
ZZR unit_root((HINT_2PI*n)/m);
}
AXZ get_omega(UINT_32 shift,ARS n)QC
{
ARS rank=1ull<<shift;
QC ARS rank_ff=rank-1,quad_n=n<<2;
ARS zone=quad_n>>shift;
if((quad_n&rank_ff)==0)
{
ZZS AXC AXZ ONES[4]={AXZ(1,0),AXZ(0,-1),AXZ(-1,0),AXZ(0,1)};
ZZR ONES[zone];
}
AXZ tmp;
if((zone&2)==0)
{
if((zone&1)==0)
{
tmp=table1[shift][n];
}
else
{
tmp=table1[shift][rank/2-n];
tmp.real(-tmp.real());
}
}
else
{
if((zone&1)==0)
{
tmp= -table1[shift][n-rank/2];
}
else
{
tmp=table1[shift][rank-n];
tmp.imag(-tmp.imag());
}
}
ZZR tmp;
}
AXZ get_omega3(UINT_32 shift,ARS n)QC
{
ZZR table3[shift][n];
}
Complex2 get_omegaX2(UINT_32 shift,ARS n)QC
{
ZZR Complex2(table1[shift].data()+n);
}
Complex2 get_omega3X2(UINT_32 shift,ARS n)QC
{
ZZR Complex2(table3[shift].data()+n);
}
};
AXC ARS lut_max_rank=23;
ZZS ComplexTableY TABLE(lut_max_rank);
AXT<ZZT T>
void binary_reverse_swap(T&ary,ARS len)
{
ARS i=0;
for(ARS j=1;j<len-1;j++)
{
ARS k=len>>1;
i^=k;
while(k>i)
{
k>>=1;
i^=k;
};
if(j<i)
{
std::swap(ary[i],ary[j]);
}
}
}
AXT<ZZT SizeType=UINT_32,ZZT T>
void quaternary_reverse_swap(T&ary,ARS len)
{
SizeType log_n=hint_log2(len);
SizeType*rev=new SizeType[len/4];
rev[0]=0;
for(SizeType i=1;i<len;i++)
{
SizeType index=(rev[i>>2]>>2)|((i&3)<<(log_n-2));
if(i<len/4)
{
rev[i]=index;
}
if(i<index)
{
std::swap(ary[i],ary[index]);
}
}
delete[]rev;
}
AXT<ZZT T>
QI void azD(T&sum,T&diff)
{
T tmp0=sum;
T tmp1=diff;
sum=tmp0+tmp1;
diff=tmp0-tmp1;
}
QI void fft_4point(AXZ*input,ARS rank=1)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank];
AXZ tmp2=input[rank*2];
AXZ tmp3=input[rank*3];
azD(tmp0,tmp2);
azD(tmp1,tmp3);
tmp3=AXZ(tmp3.imag(),-tmp3.real());
input[0]=tmp0+tmp1;
input[rank]=tmp2+tmp3;
input[rank*2]=tmp0-tmp1;
input[rank*3]=tmp2-tmp3;
}
QI void fft_dit_4point(AXZ*input,ARS rank=1)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank];
AXZ tmp2=input[rank*2];
AXZ tmp3=input[rank*3];
azD(tmp0,tmp1);
azD(tmp2,tmp3);
tmp3=AXZ(tmp3.imag(),-tmp3.real());
input[0]=tmp0+tmp2;
input[rank]=tmp1+tmp3;
input[rank*2]=tmp0-tmp2;
input[rank*3]=tmp1-tmp3;
}
QI void fft_dit_8point(AXZ*input,ARS rank=1)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank];
AXZ tmp2=input[rank*2];
AXZ tmp3=input[rank*3];
AXZ tmp4=input[rank*4];
AXZ tmp5=input[rank*5];
AXZ tmp6=input[rank*6];
AXZ tmp7=input[rank*7];
azD(tmp0,tmp1);
azD(tmp2,tmp3);
azD(tmp4,tmp5);
azD(tmp6,tmp7);
tmp3=AXZ(tmp3.imag(),-tmp3.real());
tmp7=AXZ(tmp7.imag(),-tmp7.real());
azD(tmp0,tmp2);
azD(tmp1,tmp3);
azD(tmp4,tmp6);
azD(tmp5,tmp7);
ZZS AXC ZZD cos_1_8=0.70710678118654752440084436210485;
tmp5=cos_1_8*AXZ(tmp5.imag()+tmp5.real(),tmp5.imag()-tmp5.real());
tmp6=AXZ(tmp6.imag(),-tmp6.real());
tmp7= -cos_1_8*AXZ(tmp7.real()-tmp7.imag(),tmp7.real()+tmp7.imag());
input[0]=tmp0+tmp4;
input[rank]=tmp1+tmp5;
input[rank*2]=tmp2+tmp6;
input[rank*3]=tmp3+tmp7;
input[rank*4]=tmp0-tmp4;
input[rank*5]=tmp1-tmp5;
input[rank*6]=tmp2-tmp6;
input[rank*7]=tmp3-tmp7;
}
QI void fft_dif_4point(AXZ*input,ARS rank=1)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank];
AXZ tmp2=input[rank*2];
AXZ tmp3=input[rank*3];
azD(tmp0,tmp2);
azD(tmp1,tmp3);
tmp3=AXZ(tmp3.imag(),-tmp3.real());
input[0]=tmp0+tmp1;
input[rank]=tmp0-tmp1;
input[rank*2]=tmp2+tmp3;
input[rank*3]=tmp2-tmp3;
}
QI void fft_dif_8point(AXZ*input,ARS rank=1)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank];
AXZ tmp2=input[rank*2];
AXZ tmp3=input[rank*3];
AXZ tmp4=input[rank*4];
AXZ tmp5=input[rank*5];
AXZ tmp6=input[rank*6];
AXZ tmp7=input[rank*7];
azD(tmp0,tmp4);
azD(tmp1,tmp5);
azD(tmp2,tmp6);
azD(tmp3,tmp7);
ZZS AXC ZZD cos_1_8=0.70710678118654752440084436210485;
tmp5=cos_1_8*AXZ(tmp5.imag()+tmp5.real(),tmp5.imag()-tmp5.real());
tmp6=AXZ(tmp6.imag(),-tmp6.real());
tmp7= -cos_1_8*AXZ(tmp7.real()-tmp7.imag(),tmp7.real()+tmp7.imag());
azD(tmp0,tmp2);
azD(tmp1,tmp3);
azD(tmp4,tmp6);
azD(tmp5,tmp7);
tmp3=AXZ(tmp3.imag(),-tmp3.real());
tmp7=AXZ(tmp7.imag(),-tmp7.real());
input[0]=tmp0+tmp1;
input[rank]=tmp0-tmp1;
input[rank*2]=tmp2+tmp3;
input[rank*3]=tmp2-tmp3;
input[rank*4]=tmp4+tmp5;
input[rank*5]=tmp4-tmp5;
input[rank*6]=tmp6+tmp7;
input[rank*7]=tmp6-tmp7;
}
QI void fft_radix2_dit_butterfly(AXZ omega,AXZ*input,ARS rank)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank]*omega;
input[0]=tmp0+tmp1;
input[rank]=tmp0-tmp1;
}
QI void fft_radix2_dif_butterfly(AXZ omega,AXZ*input,ARS rank)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank];
input[0]=tmp0+tmp1;
input[rank]=(tmp0-tmp1)*omega;
}
QI void fft_split_radix_dit_butterfly(AXZ omega,AXZ omega_cube,
AXZ*input,ARS rank)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank];
AXZ tmp2=input[rank*2]*omega;
AXZ tmp3=input[rank*3]*omega_cube;
azD(tmp2,tmp3);
tmp3=AXZ(tmp3.imag(),-tmp3.real());
input[0]=tmp0+tmp2;
input[rank]=tmp1+tmp3;
input[rank*2]=tmp0-tmp2;
input[rank*3]=tmp1-tmp3;
}
QI void fft_split_radix_dif_butterfly(AXZ omega,AXZ omega_cube,
AXZ*input,ARS rank)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank];
AXZ tmp2=input[rank*2];
AXZ tmp3=input[rank*3];
azD(tmp0,tmp2);
azD(tmp1,tmp3);
tmp3=AXZ(tmp3.imag(),-tmp3.real());
input[0]=tmp0;
input[rank]=tmp1;
input[rank*2]=(tmp2+tmp3)*omega;
input[rank*3]=(tmp2-tmp3)*omega_cube;
}
QI void fft_split_radix_dit_butterfly(Complex2 omega,Complex2 omega_cube,
AXZ*input,ARS rank)
{
Complex2 tmp0=input;
Complex2 tmp1=input+rank;
Complex2 tmp2=Complex2(input+rank*2)*omega;
Complex2 tmp3=Complex2(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(Complex2 omega,Complex2 omega_cube,
AXZ*input,ARS rank)
{
Complex2 tmp0=(input);
Complex2 tmp1=(input+rank);
Complex2 tmp2=(input+rank*2);
Complex2 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(AXZ omega,AXZ omega_sqr,AXZ omega_cube,
AXZ*input,ARS rank)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank]*omega;
AXZ tmp2=input[rank*2]*omega_sqr;
AXZ tmp3=input[rank*3]*omega_cube;
azD(tmp0,tmp2);
azD(tmp1,tmp3);
tmp3=AXZ(tmp3.imag(),-tmp3.real());
input[0]=tmp0+tmp1;
input[rank]=tmp2+tmp3;
input[rank*2]=tmp0-tmp1;
input[rank*3]=tmp2-tmp3;
}
QI void fft_radix4_dif_butterfly(AXZ omega,AXZ omega_sqr,AXZ omega_cube,
AXZ*input,ARS rank)
{
AXZ tmp0=input[0];
AXZ tmp1=input[rank];
AXZ tmp2=input[rank*2];
AXZ tmp3=input[rank*3];
azD(tmp0,tmp2);
azD(tmp1,tmp3);
tmp3=AXZ(tmp3.imag(),-tmp3.real());
input[0]=tmp0+tmp1;
input[rank]=(tmp2+tmp3)*omega;
input[rank*2]=(tmp0-tmp1)*omega_sqr;
input[rank*3]=(tmp2-tmp3)*omega_cube;
}
QI void fft_conj(AXZ*input,ARS azE,ZZD div=1)
{
for(ARS i=0;i<azE;i++)
{
input[i]=std::conj(input[i])/div;
}
}
QI void fft_normalize(AXZ*input,ARS azE)
{
ZZD len=static_cast<ZZD>(azE);
for(ARS i=0;i<azE;i++)
{
input[i]/=len;
}
}
AXT<ARS LEN>
void azB(AXZ*input)
{
AXC ARS log_len=hint_log2(LEN);
AXC ARS half_len=LEN/2,quarter_len=LEN/4;
azB<half_len>(input);
azB<quarter_len>(input+half_len);
azB<quarter_len>(input+half_len+quarter_len);
for(ARS 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>(AXZ*input){}
AXT<>
void azB<1>(AXZ*input){}
AXT<>
void azB<2>(AXZ*input)
{
azD(input[0],input[1]);
}
AXT<>
void azB<4>(AXZ*input)
{
fft_dit_4point(input,1);
}
AXT<>
void azB<8>(AXZ*input)
{
fft_dit_8point(input,1);
}
AXT<ARS LEN>
void azC(AXZ*input)
{
AXC ARS log_len=hint_log2(LEN);
AXC ARS half_len=LEN/2,quarter_len=LEN/4;
for(ARS 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>(AXZ*input){}
AXT<>
void azC<1>(AXZ*input){}
AXT<>
void azC<2>(AXZ*input)
{
azD(input[0],input[1]);
}
AXT<>
void azC<4>(AXZ*input)
{
fft_dif_4point(input,1);
}
AXT<>
void azC<8>(AXZ*input)
{
fft_dif_8point(input,1);
}
AXT<ARS LEN=1>
void fft_dit_template(AXZ*input,ARS azE)
{
if(azE>LEN)
{
fft_dit_template<LEN*2>(input,azE);
ZZR;
}
TABLE.expand(hint_log2(LEN));
azB<LEN>(input);
}
AXT<>
void fft_dit_template<1<<24>(AXZ*input,ARS azE){}
AXT<ARS LEN=1>
void fft_dif_template(AXZ*input,ARS azE)
{
if(azE>LEN)
{
fft_dif_template<LEN*2>(input,azE);
ZZR;
}
TABLE.expand(hint_log2(LEN));
azC<LEN>(input);
}
AXT<>
void fft_dif_template<1<<24>(AXZ*input,ARS azE){}
QI void fft_dit(AXZ*input,ARS azE,bool bit_rev=true)
{
azE=max_2pow(azE);
if(bit_rev)
{
binary_reverse_swap(input,azE);
}
fft_dit_template<1>(input,azE);
}
QI void fft_dif(AXZ*input,ARS azE,bool bit_rev=true)
{
azE=max_2pow(azE);
fft_dif_template<1>(input,azE);
if(bit_rev)
{
binary_reverse_swap(input,azE);
}
}
}
AXT<UINT_64 BASE,ZZT T>
AXC void save_num_to_ary(T ary[],UINT_64 num,ARS digit)
{
ARS 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);
change_length(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);
change_length(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;
ARS len=input.length();
resize(len);
change_length(len);
change_sign(input.sign());
ary_copy(ary_ptr,input.ary_ptr,len);
}
}
HintVector(HintVector&&input)
{
if(input.ary_ptr!=nullptr)
{
size=input.size;
change_length(input.length());
change_sign(input.sign());
if(ary_ptr!=nullptr)
{
delete[]ary_ptr;
}
ary_ptr=input.ary_ptr;
input.ary_ptr=nullptr;
}
}
HintVector&operator=(QC HintVector&input)
{
if(this!= &input)
{
if(ary_ptr!=nullptr)
{
delete[]ary_ptr;
}
ary_ptr=nullptr;
ARS len=input.length();
resize(len);
change_length(len);
change_sign(input.sign());
ary_copy(ary_ptr,input.ary_ptr,len);
}
ZZR*this;
}
HintVector&operator=(HintVector&&input)
{
if(this!= &input)
{
size=input.size;
change_length(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&operator[](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];
change_length(0);
}
else if(size!=new_size)
{
size=new_size;
ary_ptr=ary_realloc(ary_ptr,size);
change_length(length());
}
}
void change_length(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--;
}
change_length(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 ARS ary_true_len(QC T&ary,ARS len)
{
while(len>0&&ary[len-1]==0)
{
len--;
}
ZZR len;
}
AXT<ZZT T>
AXC INT_32 abs_compare(QC T ary1[],QC T ary2[],ARS len1,ARS len2)
{
len1=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[],ARS len)
{
len=ary_true_len(in,len);
num%=BASE;
UINT_64 prod=0;
if(num==1)
{
ary_copy(out,in,len);
}
else
{
for(ARS 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[],ARS len)
{
ARS 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[],
ARS len1,ARS len2)
{
if(len1<len2)
{
std::swap(in1,in2);
std::swap(len1,len2);
}
ARS 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[],
ARS len1,ARS len2)
{
if(len1<len2)
{
ZZR;
}
ARS 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[],
ARS len1,ARS len2)
{
using namespace hint_transform;
if(len1==0||len2==0||in1==nullptr||in2==nullptr)
{
ZZR;
}
QC ARS conv_res_len=len1+len2-1;
QC ARS azE=min_2pow(conv_res_len);
ZZS AXZ*fft_buf=nullptr;ZZS ARS fft_cap=0;
if(fft_cap<azE){free(fft_buf);fft_buf=(AXZ*)malloc(azE*arZ(AXZ));fft_cap=azE;}
AXZ*fft_ary=fft_buf;
{ARS mnz=len1<len2?len1:len2;
memset((char*)(fft_ary+mnz),0,(azE-mnz)*arZ(AXZ));}
com_ary_combine_copy(fft_ary,in1,len1,in2,len2);
fft_dif(fft_ary,azE,false);
ZZD inv= -1/(2.0*azE);
for(ARS i=0;i<azE;i++)
{
AXZ tmp=fft_ary[i];
fft_ary[i]=std::conj(tmp*tmp*inv);
}
fft_dit(fft_ary,azE,false);
hint::UINT_64 carry=0;
for(ARS 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,ARS n)
{
ARS 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,ARS count){
__m128i p1=_mm_setzero_si128(),p2=p1,p3=p1;
for(ARS i=0;i<=count;i+=4){
arV mask=_mm256_set_epi64x(i+3<count?-1LL:0,i+2<count?-1LL:0,i+1<count?-1LL:0,i<count?-1LL:0);
arV raw=_mm256_maskload_epi64((QC long long*)(c+i),mask);
__m128i sum=carry550fold(raw,p1,p2,p3);
if(i+4<=count+1)_mm_storeu_si128((__m128i*)(out+i),sum);
else{QO tail[4];_mm_storeu_si128((__m128i*)tail,sum);__builtin_memcpy(out+i,tail,(count+1-i)*4);}
}
QC arV zero=_mm256_setzero_si256(),base=_mm256_set1_epi32(10000),one=_mm256_set1_epi32(1),shifts=_mm256_setr_epi32(0,1,2,3,4,5,6,7),indices=_mm256_setr_epi32(0,0,1,2,3,4,5,6);
QO carry=0;ARS i=0;
for(;i+8<=count+1;i+=8){
arV s=_mm256_loadu_si256((QC arV*)(out+i));
arV q=_mm256_sub_epi32(zero,_mm256_add_epi32(_mm256_add_epi32(_mm256_cmpgt_epi32(s,_mm256_set1_epi32(9999)),_mm256_cmpgt_epi32(s,_mm256_set1_epi32(19999))),_mm256_cmpgt_epi32(s,_mm256_set1_epi32(29999))));
arV prior=_mm256_blend_epi32(_mm256_permutevar8x32_epi32(q,indices),_mm256_set1_epi32(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,_mm256_set1_epi32(9999))));
QO p=(QO)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpeq_epi32(y,_mm256_set1_epi32(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(_mm256_set1_epi32(e),shifts),one);
arV before=_mm256_and_si256(_mm256_srlv_epi32(_mm256_set1_epi32(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[],ARS len1,ARS len2){
if(!len1||!len2||!in1||!in2)ZZR;
QC ARS conv=len1+len2-1;
if AXC(BASE==10000&&arZ(T)==4){if(len1*len2<=65536){
QC T*aa=in1,*bb=in2;ARS na=len1,nb=len2;if(na>nb){std::swap(aa,bb);std::swap(na,nb);}
ZZS ARU*bp=nullptr,*ap=nullptr,*tmp=nullptr;ZZS ARS bc=0,ac=0,tc=0;
QC ARS need=nb+34,an=(na+1)/2;if(bc<need){free(bp);bp=(ARU*)malloc(need*4);bc=need;}if(ac<an){free(ap);ap=(ARU*)malloc(an*4);ac=an;}
memset(bp,0,16*4);ARU*packed=bp+16;for(ARS k=0;k<nb;k++)packed[k]=bb[k]|(k?bb[k-1]<<16:0);packed[nb]=bb[nb-1]<<16;memset(packed+nb+1,0,17*4);
for(ARS k=0;k<an;k++)ap[k]=aa[2*k]|(2*k+1<na?aa[2*k+1]<<16:0);
uintptr_t ob=(uintptr_t)out,oe=(uintptr_t)(out+conv+1),ab=(uintptr_t)in1,ae=(uintptr_t)(in1+len1),bbeg=(uintptr_t)in2,be=(uintptr_t)(in2+len2);
QC bool overlap=(ob<ae&&oe>ab)||(ob<be&&oe>bbeg);T*o=out;if(overlap){if(tc<conv+1){free(tmp);tmp=(ARU*)malloc((conv+1)*4);tc=conv+1;}o=(T*)tmp;}
ARL carry=0;ARS m=0;
for(;m+16<=conv;m+=16){
ARL sums[16]={};QC ARS lo=m>=nb-1?m-(nb-1):0,hi=std::min(na-1,m+15);
for(ARS i0=lo&~ARS(1);i0<=hi;i0+=40){
QC ARS end=std::min(hi+1,i0+40);arV s0=_mm256_setzero_si256(),s1=s0;
for(ARS i=i0;i<end;i+=2){arV av=_mm256_set1_epi32(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 ARS lo=m>=nb-1?m-(nb-1):0,hi=std::min(na-1,m);for(ARS i=lo;i<=hi;i++)sum+=(ARL)aa[i]*bb[m-i];sum+=carry;o[m]=sum%10000;carry=sum/10000;}
o[conv]=carry;if(overlap)memcpy(out,o,(conv+1)*4);ZZR;
}}
if(conv<=1024){fft_mul_old<BASE>(in1,in2,out,len1,len2);return;}
ARS n=hintpowfft::int_ceil2(conv);if(n<4096)n=4096;
ZZS ZZD*g_abuf=nullptr,*g_bbuf=nullptr;ZZS ARS g_acap=0,g_bcap=0;
if(g_acap<n){_mm_free(g_abuf);g_abuf=(ZZD*)_mm_malloc(n*arZ(ZZD),64);g_acap=n;}
ZZD*a=g_abuf;
memset(a+len1,0,(n-len1)*arZ(ZZD));
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(ARS 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[],ARS len)
{
if(in==out)
{
throw("In can't be same as out\n");
}
T multiplier=1;
if(len==1)
{
multiplier=(BASE-1)/in[0];
out[0]=in[0]*multiplier;
}
else if(in[len-1]>=(BASE/2))
{
ary_copy(out,in,len);
}
else
{
multiplier=(BASE-1)*BASE/(BASE*in[len-1]+in[len-2]);
abs_mul_num<BASE,false>(in,multiplier,out,len);
if(out[len-1]<(BASE/2))
{
multiplier++;
abs_add<BASE,false>(out,in,out,len,len);
}
}
ZZR multiplier;
}
AXT<UINT_64 BASE,ZZT T>
void abs_long_div(T dividend[],QC T divisor[],T quot[],
ARS len1,ARS len2)
{
len1=ary_true_len(dividend,len1);
len2=ary_true_len(divisor,len2);
if(divisor==nullptr||len2==0)
{
throw("Can't divide by zero\n");
}
if(dividend==nullptr||len1==0)
{
ZZR;
}
if(abs_compare(dividend,divisor,len1,len2)<0)
{
ZZR;
}
if(len2==1)
{
T rem=abs_div_num<BASE>(dividend,divisor[0],quot,len1);
dividend[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(dividend,divisor,len1,len2)>=0)
{
sub.change_length(len2+1);
UINT_64 dividend_2digits=dividend[len1-1]*BASE+dividend[len1-2];
T quo_digit=0;
ARS 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();
ARS sub_len=sub.length();
if(abs_compare(dividend+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(dividend+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();
ARS sub_len=sub.length();
if(abs_compare(dividend+shift,sub.data(),len1-shift,sub_len)<0)
{
quo_digit--;
abs_sub<BASE>(sub.data(),divisor,sub.data(),sub_len,len2);
if(abs_compare(dividend+shift,sub.data(),len1-shift,sub_len)<0)
{
quo_digit--;
abs_sub<BASE>(sub.data(),divisor,sub.data(),sub_len,len2);
}
}
}
abs_sub<BASE>(dividend+shift,sub.data(),dividend+shift,len1-shift,sub.length());
len1=ary_true_len(dividend,len1);
quot[shift]=quo_digit;
}
}
AXT<UINT_64 BASE,ZZT T>
void abs_rec_div(T dividend[],T divisor[],hintvector<T> &quot,
ARS len1,ARS len2)
{
len1=ary_true_len(dividend,len1);
len2=ary_true_len(divisor,len2);
if(divisor==nullptr||len2==0)
{
throw("Can't divide by zero\n");
}
if(dividend==nullptr||len1==0)
{
ZZR;
}
if(abs_compare(dividend,divisor,len1,len2)<0)
{
ZZR;
}
if(divisor[len2-1]<(BASE/2))
{
throw("Can't call this proc before normalize the divisor\n");
}
ARS quot_len=len1-len2+1;
quot.change_length(quot_len);
AXC ARS LONG_DIV_THRESHOLD=50;
if(len2<=LONG_DIV_THRESHOLD)
{
abs_long_div<BASE>(dividend,divisor,quot.data(),len1,len2);
}
else if(len1>=len2*2||len1>((len2+1)/2)*3)
{
ARS base_len=(len1+3)/4;
ARS quot_tmp_len=base_len*3-len2+2;
hintvector<T>quot_tmp(quot_tmp_len,0);
abs_rec_div<BASE>(dividend+base_len,divisor,quot_tmp,len1-base_len,len2);
quot_tmp_len=quot_tmp.set_true_len();
ARS dividend_len=ary_true_len(dividend,len1);
abs_rec_div<BASE>(dividend,divisor,quot,dividend_len,len2);
quot.change_length(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.change_length(len1-len2+1);
}
else
{
ARS base_len=len2/2;
abs_rec_div<BASE>(dividend+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);
ARS prod_len=prod.set_true_len();
len1=ary_true_len(dividend,len1);
while(abs_compare(prod.data(),dividend,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>(dividend+base_len,divisor+base_len,dividend+base_len,len1-base_len,len2-base_len);
quot_len=quot.set_true_len();
prod_len=prod.set_true_len();
len1=ary_true_len(dividend,std::max(len1,len2)+1);
}
abs_sub<BASE>(dividend,prod.data(),dividend,len1,prod_len);
}
}
AXT<UINT_64 BASE,ZZT T>
hintvector<T>abs_div(QC T dividend[],T divisor[],hintvector<T> &quot,
ARS len1,ARS len2,bool ret_rem=true)
{
hintvector<T>normalized_divisor(len2);
normalized_divisor.change_length(len2);
hintvector<T>normalized_dividend(len1+1);
normalized_dividend.change_length(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>(dividend,multiplier,dividend_ptr,len1);
len1=normalized_dividend.set_true_len();
quot=hintvector<T>(len1-len2+2,0);
if((!ret_rem)&&(len1+2<len2*2))
{
ARS shift=len2*2-len1-2;
abs_rec_div<BASE>(dividend_ptr+shift,divisor_ptr+shift,quot,len1-shift,len2-shift);
quot.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::operator new(w*16);void*p=h[c];if(p)h[c]=*(void**)p;else p=::operator 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){::operator delete(p);arR;}*(void**)p=h[c];h[c]=p;}};
AXT<class T>struct NoInitAlloc{
using value_type=T;
NoInitAlloc()arN=default;
AXT<class U>NoInitAlloc(QC NoInitAlloc<U>&)arN{}
T*allocate(std::ARS n){ZZR static_cast<T*>(LP648::get(n*arZ(T)));}
void deallocate(T*p,std::ARS n)arN{LP648::put(p,n*arZ(T));}
AXT<class U>void construct(U*p){::new(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 operator==(QC NoInitAlloc&)QC arN{ZZR true;}
bool operator!=(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;
}
#include <cstdint>
__attribute__((always_inline))static inline __uint128_t iv608dm(__uint128_t x,uint64_t&remainder){
constexpr uint64_t D=10000000000000000ULL;
if((x>>118)==0){
constexpr __uint128_t M=((__uint128_t)1<<118)/D;
static_assert((M>>64)==1);
const uint64_t al=(uint64_t)x,ah=(uint64_t)(x>>64),bl=(uint64_t)M;
const __uint128_t p0=(__uint128_t)al*bl,p1=(__uint128_t)ah*bl;
const __uint128_t mid=(p0>>64)+(uint64_t)p1+(__uint128_t)al;
const uint64_t high=(uint64_t)(p1>>64)+ah+(uint64_t)(mid>>64);
__uint128_t q=((__uint128_t)high<<10)|((uint64_t)mid>>54);
uint64_t r=(uint64_t)(x-q*D);if(r>=D){r-=D;++q;}
remainder=r;return q;
}
return iv603dm(x,remainder);
}

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=iv608dm(a,part);
QY up=part/100000000ULL,low=part-up*100000000ULL;
d[n++]=low%10000;d[n++]=low/10000;d[n++]=up%10000;d[n++]=up/10000;}
ARL tail=(ARL)a;while(tail){d[n++]=tail%10000;tail/=10000;}
Big x;x.v.assign(d,d+n);ZZR x;
}
bool zero()QC{ZZR v.empty();}
void trim(){while(!v.empty()&&!v.back())v.pop_back();if(v.empty())neg=false;}
int cmpabs(QC Big&b)QC{if(v.size()!=b.v.size())ZZR v.size()<b.v.size()?-1:1;for(ARS i=v.size();i--;)if(v[i]!=b.v[i])ZZR v[i]<b.v[i]?-1:1;ZZR 0;}
Big operator-()QC{Big r=*this;if(!zero())r.neg=!neg;ZZR r;}
Big operator+(QC Big&b)QC&{
if(zero())ZZR b;if(b.zero())ZZR*this;
if(neg!=b.neg){int c=cmpabs(b);if(!c)ZZR Big();QC Big&a=c>0?*this:b;QC Big&bb=c>0?b:*this;Big r;r.neg=a.neg;r.v.resize(a.v.size());int borrow=0;ARS i=0;for(;i<bb.v.size();++i){int q=int(a.v[i])-int(bb.v[i])-borrow;borrow=q<0;r.v[i]=q+(borrow?10000:0);}for(;i<a.v.size();++i){int q=int(a.v[i])-borrow;borrow=q<0;r.v[i]=q+(borrow?10000:0);}r.trim();ZZR r;}
Big r;r.neg=neg;r.v.resize(std::max(v.size(),b.v.size())+1);QO carry=0;for(ARS i=0;i+1<r.v.size();++i){QO q=carry+(i<v.size()?v[i]:0)+(i<b.v.size()?b.v[i]:0);carry=q>=10000;r.v[i]=q-(carry?10000:0);}r.v.back()=carry;r.trim();ZZR r;
}
Big operator+(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;
ARS n=std::max(v.size(),b.v.size());v.resize(n,0);
QO carry=0;ARS i=0;
for(;i<b.v.size();++i){QO q=v[i]+b.v[i]+carry;carry=q>=10000;v[i]=q-(carry?10000:0);}
while(carry&&i<n){QO q=v[i]+carry;carry=q>=10000;v[i]=q-(carry?10000:0);++i;}
if(carry)v.push_back(carry);
ZZR std::move(*this);
}
Big operator-(QC Big&b)QC{ZZR*this+(-b);}
Big mulnum(ARL m)QC{if(zero()||!m)ZZR Big();if(m<=UINT64_MAX/10000){Big r;r.neg=neg;r.v.resize(v.size());ARL carry=0;for(ARS i=0;i<v.size();++i){carry+=(ARL)v[i]*m;r.v[i]=carry%10000;carry/=10000;}while(carry){r.v.push_back(carry%10000);carry/=10000;}ZZR r;}Big r;r.neg=neg;r.v.resize(v.size());ARW carry=0;for(ARS i=0;i<v.size();++i){carry+=(ARW)v[i]*m;r.v[i]=(ARU)(carry%10000);carry/=10000;}while(carry){r.v.push_back(carry%10000);carry/=10000;}ZZR r;}
Big divnum(ARU d)QC{Big r;r.neg=neg;r.v.resize(v.size());ARL rem=0;for(ARS i=v.size();i--;){rem=rem*10000+v[i];r.v[i]=rem/d;rem%=d;}r.trim();ZZR r;}
Big operator*(QC Big&b)QC{
if(zero()||b.zero())ZZR Big();if(v.size()==1){Big r=b.mulnum(v[0]);r.neg=neg!=b.neg;ZZR r;}if(b.v.size()==1){Big r=mulnum(b.v[0]);r.neg=neg!=b.neg;ZZR r;}
Big r;r.neg=neg!=b.neg;r.v.resize(v.size()+b.v.size());
if(v.size()*b.v.size()<=1024){std::memset(r.v.data(),0,r.v.size()*arZ(ARU));
QC ARU*aa=v.data(),*bb=b.v.data();ARU*cc=r.v.data();
for(ARS i=0;i<v.size();++i)for(ARS j=0;j<b.v.size();++j)cc[i+j]+=aa[i]*bb[j];
ARU carry=0;for(ARS i=0;i<r.v.size();++i){ARU x=cc[i]+carry;cc[i]=x%10000;carry=x/10000;}
}
else hint_arithm::fft_mul<10000>(v.data(),b.v.data(),r.v.data(),v.size(),b.v.size());
r.trim();ZZR r;
}
ZZS Big negative_one(){Big x(1);x.neg=true;ZZR x;}
Big operator/(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(ARS limbs)QC{if(zero())ZZR Big();Big r;r.neg=neg;r.v.resize(limbs+v.size(),0);std::copy(v.begin(),v.end(),r.v.begin()+limbs);ZZR r;}
Big high(ARS cut)QC{if(cut>=v.size())ZZR Big();Big r;r.neg=neg;r.v.assign(v.begin()+cut,v.end());ZZR r;}
};
ZZS bool MP(QC Big&A,QC Big&B,QC Big&C,Big&o1,Big&o2);
struct QT{Big q,t;};
struct iv586w{ARL x[4];};
ZZS void iv586step(iv586w&w,ARL k,ARL carry){for(QO j=0;j<4;j++){ARW q=(ARW)w.x[j]*k+carry;w.x[j]=q;carry=q>>64;}}
ZZS Big iv586big(iv586w w){Big r;r.v.resize(20);ARS used=0;int top=3;QC ARL D=10000000000000000ULL;
while(top>=0){while(top>=0&&!w.x[top])--top;if(top<0)break;ARL rem=0;QY first=w.x[top];if(first<D){w.x[top]=0;rem=first;}else{w.x[top]=first/D;rem=first%D;}for(int i=top-1;i>=0;--i){ZZW cur=((ZZW)rem<<64)|w.x[i];w.x[i]=(QY)iv608dm(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(ARS i=digits;i+1<s.size();++i){lo&=s[i]=='0';hi&=s[i]=='9';}
ZZR!(lo&&s.back()<'2')&&!(hi&&s.back()>='8');
}
AXT<class Vec>ZZS void iv486write(QC Vec&x,QO digits,char*out){
struct Dec4{char d[10000][4];AXC Dec4():d{}{for(QO i=0;i<10000;++i){d[i][0]='0'+i/1000;d[i][1]='0'+i/100%10;d[i][2]='0'+i/10%10;d[i][3]='0'+i%10;}}};ZZS AXC Dec4 table{};
QO written=0;out[1]='.';auto emit=[&](char c){if(written<digits){out[written?written+1:0]=c;++written;}};
QO q=x.back();if(q>=1000)emit('0'+q/1000);if(q>=100)emit('0'+q/100%10);if(q>=10)emit('0'+q/10%10);emit('0'+q%10);
for(ARS i=x.size()-1;i--&&written<digits;){q=x[i];QO left=digits-written;if(left>=4){std::memcpy(out+written+1,table.d[q],4);written+=4;}else{emit(table.d[q][0]);if(left>=2)emit(table.d[q][1]);if(left>=3)emit(table.d[q][2]);}}
}
ZZS ARU*g_vbuf=nullptr;ZZS ARS g_vcap=0;
ZZS ARU*vmul(QC ARU*a,ARS la,QC ARU*b,ARS lb,ARS&outlen){
QC ARS need=la+lb+1;
if(g_vcap<need){free(g_vbuf);g_vbuf=(ARU*)malloc(need*arZ(ARU));if(!g_vbuf)abort();g_vcap=need;}
outlen=need;
if(!la||!lb){memset(g_vbuf,0,need*arZ(ARU));ZZR g_vbuf;}
hint_arithm::fft_mul<10000>(a,b,g_vbuf,la,lb);
g_vbuf[la+lb]=0;
ZZR g_vbuf;
}
ZZS void vtrim(std::vector<ARU>&v){ARS n=v.size();while(n>1&&v[n-1]==0)--n;v.resize(n);}
ZZS ZZD*ar_nr[2]={nullptr,nullptr};ZZS ARS ar_nr_cap=0;
ZZS void ar_nr_prepare(QC ARU*r,ARS lr,ARS n){
if(ar_nr_cap<n){for(QO j=0;j<2;j++){_mm_free(ar_nr[j]);ar_nr[j]=(ZZD*)_mm_malloc(n*8,64);}ar_nr_cap=n;}
hint_arithm::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,ARS la,ARS lr,ARS n,ARS&outlen){
outlen=la+lr+1;if(g_vcap<outlen){free(g_vbuf);g_vbuf=(ARU*)malloc(outlen*4);if(!g_vbuf)abort();g_vcap=outlen;}
hint_arithm::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;ARS conv=la+lr-1;
for(ARS j=0;j<conv;j++){carry+=c[j];g_vbuf[j]=carry%10000;carry/=10000;}g_vbuf[conv]=carry%10000;g_vbuf[conv+1]=0;ZZR g_vbuf;
}
AXT<class VA,class VB>ZZS std::vector<ARU>scaled_newton(QC VA&Tv,
QC VB&Qv,
ARS L){
QC ARU*Q=Qv.data();QC ARS nq=Qv.size();
QC ARS M0=3;
long ZZD qk=0,scale=1;
for(int i=0;i<8&&(ARS)i<nq;++i){qk=qk*10000.0L+(long ZZD)Q[nq-1-i];scale*=10000.0L;}
long ZZD rho=scale/(qk+1.0L);
ARL R0=(ARL)(rho*1e12L);
std::vector<ARU>R;
while(R0){R.push_back((ARU)(R0%10000));R0/=10000;}
if(R.empty())R.push_back(1);
ARS M=M0;
for(int iter=0;iter<80;++iter){
QC ARS quse=(nq<2*M)?nq:2*M;
QC ARU*Dq=Q+(nq-quse);
QC ARS lr=R.size();
QC ARS ar_n=hintpowfft::int_ceil2(quse+lr-1);bool ar_keep=ar_n>=4096;if(ar_keep)ar_nr_prepare(R.data(),lr,ar_n);
ARS plen;ARU*P=ar_keep?ar_nr_product(Dq,quse,lr,ar_n,plen):vmul(Dq,quse,R.data(),lr,plen);
QC ARS fpow=M+quse;
ARS flen=(plen>fpow+2)?plen:fpow+2;
std::vector<ARU>F(flen+1,0);
F[fpow]=1;
int borrow=0;
for(ARS i=0;i<flen;++i){
int d=int(F[i])-int((i<plen)?P[i]:0)-borrow;
borrow=d<0;F[i]=ARU(d+(borrow?10000:0));
}
int neg=borrow!=0;
if(neg){
int carry=0;
for(ARS i=0;i<flen;++i){
int d=int((i<plen)?P[i]:0)-int(i==fpow?1:0)-carry;
carry=d<0;F[i]=ARU(d+(carry?10000:0));
}
}
vtrim(F);
QC ARS p=(fpow>F.size())?(fpow-F.size()):0;
if(M>=L&&p+6>=L)break;
ARS M2=(2*M<L)?2*M:L;
if(M2<=M)M2=2*M;
if(M<8192){ARS r=M+M/2+1;if(r<M2)M2=r;}
else{ARS w=1;while(w*2<=M2)w*=2;if(w>M)M2=w;}
QC ARS sh=quse;
std::vector<ARU>Rn(M+lr+((F.size()>lr)?F.size():lr)+3,0);
for(ARS i=0;i<lr;++i)Rn[M+i]=R[i];
if(F.size()>1||F[0]){
ARS glen;ARU*G=(ar_keep&&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);
ARS i=0;
if(!neg){
QO carry=0;
for(;sh+i<glen;++i){QO q=Rn[i]+G[sh+i]+carry;carry=q>=10000;Rn[i]=q-(carry?10000:0);}
for(;carry&&i<Rn.size();++i){QO q=Rn[i]+carry;carry=q>=10000;Rn[i]=q-(carry?10000:0);}
}else{
int br=0;
for(;sh+i<glen;++i){int q=int(Rn[i])-int(G[sh+i])-br;br=q<0;Rn[i]=ARU(q+(br?10000:0));}
for(;br&&i<Rn.size();++i){int q=int(Rn[i])-br;br=q<0;Rn[i]=ARU(q+(br?10000:0));}
}
}
if(2*M!=M2&&Rn.size()>2*M-M2)Rn.erase(Rn.begin(),Rn.begin()+(2*M-M2));
vtrim(Rn);
R.swap(Rn);M=M2;
}
if(M>L){
ARS drop=M-L;
if(R.size()>drop)R.erase(R.begin(),R.begin()+drop);else{R.assign(1,0);}
vtrim(R);
}
ARS plen;ARU*P=vmul(Tv.data(),Tv.size(),R.data(),R.size(),plen);
ARS slen=plen>nq?plen-nq:0;
std::vector<ARU>S(L+3,0);
for(ARS i=0;i<slen&&i<L+3;++i)S[i]=P[nq+i];
S[L]+=1;
for(ARS i=L;i+1<S.size()&&S[i]>=10000;++i){S[i]-=10000;S[i+1]+=1;}
while(S.size()>1&&S.back()==0)S.pop_back();
ZZR S;
}
struct Result{std::string digits;QO terms;ARL bs_ticks,divide_ticks,format_ticks;bool guard_stable;};
__attribute__((noinline,noclone))Result compute(QO digits,char*out){
if(!digits)ZZR{"",0,0,0,0,true};
QC QO limbs=(digits+50)/4,dec=limbs*4,terms=choose_terms(dec);
_mm_lfence();QC ARL t0=__rdtsc();QT r=binary_split(1,terms+1);
if(r.q.v.size()<=ARS(limbs)+6)abort();
_mm_lfence();QC ARL t1=__rdtsc();
auto scaled=scaled_newton(r.t.v,r.q.v,limbs);
_mm_lfence();QC ARL t2=__rdtsc();
iv486write(scaled,digits,out);std::string s;bool ok=true;
_mm_lfence();QC ARL t3=__rdtsc();
ZZR{std::move(s),terms,t1-t0,t2-t1,t3-t2,ok};
}
// Shared-operand ZZD product: o1 = A*C, o2 = B*C (base 10000, exact).
// Each binary-splitting node forms t=l.t*r.q and q=l.q*r.q. Both products use
// r.q and land on the same transform length, so r.q is converted and forward
// transformed once and its spectrum reused: 3 forward + 2 inverse transforms
// instead of 4 + 2. The pointwise products and inverses are the inherited ones.
ZZS bool MP(QC Big&A,QC Big&B,QC Big&C,Big&o1,Big&o2){
ARS oa=A.v.size(),ob=B.v.size(),oc=C.v.size();if(oa<2||ob<2||oc<2)ZZR 0;
ARS za=0,zb=0,zc=0;while(A.v[za]==0)++za;while(B.v[zb]==0)++zb;while(C.v[zc]==0)++zc;
ARS la=oa-za,lb=ob-zb,lc=oc-zc;
if(la<2||lb<2||lc<2)ZZR 0;
ARS c1=la+lc-1,c2=lb+lc-1;
if(c1<4096||c2<4096||la*lc<=65536||lb*lc<=65536)ZZR 0;
ARS n=hintpowfft::int_ceil2(c1);if(hintpowfft::int_ceil2(c2)!=n)ZZR 0;
ZZS ZZD*F3[3]={0,0,0};ZZS ARS cap=0;
if(cap<n){for(int i=0;i<3;i++){_mm_free(F3[i]);F3[i]=(ZZD*)_mm_malloc(n*8,64);}cap=n;}
ZZD*a=F3[0],*b=F3[1],*d=F3[2];
memset(a+la,0,(n-la)*8);hint_arithm::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);
ARS s1=za+zc,s2=zb+zc;o1.v.resize(oa+oc);o2.v.resize(ob+oc);
if(s1)memset(o1.v.data(),0,s1*4);if(s2)memset(o2.v.data(),0,s2*4);
ARU*p=o1.v.data()+s1,*q=o2.v.data()+s2;
ARL k=0;for(ARS i=0;i<c1;i++){k+=((QC ARL*)a)[i];p[i]=k%10000;k/=10000;}p[c1]=k%10000;
k=0;for(ARS i=0;i<c2;i++){k+=((QC ARL*)b)[i];q[i]=k%10000;k/=10000;}q[c2]=k%10000;
o1.neg=o2.neg=0;o1.trim();o2.trim();ZZR 1;
}
}
void calc_e(QO n,char*s){if(!n)ZZR;if(n==1){s[0]='2';ZZR;}e_compute::compute(n-1,s);}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1399.829 ms145 MB + 156 KBAcceptedScore: 100


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