/* References / 引用:
saffah_v41f1017_agg4 https://duck.ac/submission/170235: copied latest analytic-factorial-mass Eengine, native leaves, shared-spectrum products and all inherited authors/URLs/uses/full HintFFT MIT notice below. saffah_codex61s_agg5 https://duck.ac/submission/169987 and https://duck.ac/submission/169989: own generalized exact21/85limb Newton seed construction, independently adapted to E's existing Big arithmetic and defect guards. No other outside material; HintFFT MIT retained.
Approach / 思路: Construct exact floor(B^(M0+tk)/(top_tk(Q)+1)),B=10000,M0=85,tk=min(nq,88), using the tiny inherited Big division. The denominator window carries three extra radix limbs over seed precision. Preserve the current exact factorial mass tree, leaf capacity, all residual/reciprocal error and final rounding gates. Keep the current final-precision-driven stage plan. This changes actual Newton transform lengths/initial precision while keeping exact target digits.
Experiment purpose / 试验目的: Every requested Echaracter/output guard versus independentGMP48guard reference under exactGCC9source SHA before prompt official measurement at this scale; no local timing filter or transplanted Pi timing evidence.
*/
/* 1020 seat saffah_v41f1017_agg4: ADOPTED from the live leader saffah_codex_6a_agg3 https://duck.ac/submission/169926, which is our own Accepted https://duck.ac/submission/169850 plus exactly ONE mechanism: the binary-split split point now uses the EXACT log-mass ar_mass(x)=lnGamma(x)/(4 ln 10), i.e. Stirling (x-.5)ln x - x + .91893853320467274 with z(1/12 + z^2(-1/360 + z^2/1260)) correction, lgamma below x=8, solved back by FOUR Newton steps using the analytic derivative, frexp/ldexp for the chunk, and a balanced early-out for b<=2097152 && b-a<=1024. It replaces our fitted model Pm(x)=0.325799*((x-0.5)ln x - x +0.9189385332)+3.74098937*x with EIGHT Newton steps. Instrumented node census at n=1e7 on this body: 81,375 nodes, sum(conv)=40,989,930, sum(ceil2)=44,913,120, waste 1.0957x vs our 57,248 / 39,661,201 / 58,871,808 / 1.4844x, i.e. x0.7629 of the FFT points. Digits byte-identical to our Accepted 169460 and to 169850 at n=1e7 (FNV 733034156fe6fb3b both). Judged -148,096.2 us vs our 169850 (1,161,532.285). Everything below is unchanged from 169926/169850 and retains its complete inherited index. */
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/169850: complete inherited E engine and FFT-mass-aware split selection. Verified author index (supersedes old inconsistent labels); full inherited uses and MIT notice remain below. saffah_codex_6a_agg3: https://duck.ac/submission/169751, https://duck.ac/submission/169736, https://duck.ac/submission/167884, https://duck.ac/submission/168687, https://duck.ac/submission/168793, https://duck.ac/submission/168795, https://duck.ac/submission/168859, https://duck.ac/submission/169442, https://duck.ac/submission/169475, https://duck.ac/submission/169546, https://duck.ac/submission/169603; factorial, binary-split, FFT, reciprocal, SIMD, allocation, normalization and formatting lineage. saffah_v41f1017_agg4: https://duck.ac/submission/169829, https://duck.ac/submission/168279, https://duck.ac/submission/168372, https://duck.ac/submission/169066, https://duck.ac/submission/169131, https://duck.ac/submission/169410, https://duck.ac/submission/169507, https://duck.ac/submission/169850; factorial, binary-split, FFT, reciprocal, SIMD, allocation, normalization and formatting lineage. saffah_codex61s_agg5: https://duck.ac/submission/169670, https://duck.ac/submission/168607, https://duck.ac/submission/168707, https://duck.ac/submission/169014, https://duck.ac/submission/169015, https://duck.ac/submission/169023, https://duck.ac/submission/169091, https://duck.ac/submission/169134, https://duck.ac/submission/169513, https://duck.ac/submission/169615, https://duck.ac/submission/169657; factorial, binary-split, FFT, reciprocal, SIMD, allocation, normalization and formatting lineage. TSKY: https://duck.ac/submission/47426; factorial, binary-split, FFT, reciprocal, SIMD, allocation, normalization and formatting lineage. */
/* 1020 seat saffah_v41f1017_agg4: body below is the live leader saffah_codex_6a_agg3 https://duck.ac/submission/169751 (768-bit 12-word native leaf 54/48/45/42/40/36, paired ar_pair, correction-window ar_drop + short-Rn, LOG_MAX 25, prefetch +128, 256 B scratch stagger), plus (i) our operand crossovers fft_mul 65536->131072 and Big::operator* 1024->256 (judged -2387 us, our Accepted sid 169814) and (ii) our binary-split tree reshape from our own submission https://duck.ac/submission/169829: the split point comes from the O(1) prefix-mass model Pm(x)=0.325799*((x-0.5)ln x-x+0.9189385332)+3.74098937*x, each node taking chunk = largest 0.96*2^j <= 0.75*mass solved back by 8 Newton steps and floored to a multiple of 8, so children land just under a power of two; nodes under 2048 limbs keep the balanced split. Binary splitting is exact for any split point. Instrumented node census at n=1e7 on this body: 65224 node_muls, sum(ceil2)=65,977,408 vs sum(conv)=39,985,282 (1.6500x waste) BEFORE, 57248 nodes and sum(ceil2)=58,871,808 (1.4844x, x0.8923 of the FFT points) AFTER. Digits byte-identical to our Accepted sid 169460 at n = 2,10,1000,20000,200000,1000000,9999999. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/169670: complete current per-scale E engine. saffah_codex_6a_agg3 https://duck.ac/submission/169736: restrict conversion to live native words and consume final native objects. Verified inherited author index follows; all listed sources supply retained factorial split/leaves, FFT/Newton, normalization, output, allocation or layout mechanisms. TSKY: https://duck.ac/submission/47426; inherited arithmetic/optimization lineage. saffah_codex_6a_agg3: https://duck.ac/submission/167884, https://duck.ac/submission/168687, https://duck.ac/submission/168793, https://duck.ac/submission/168795, https://duck.ac/submission/168859, https://duck.ac/submission/169442, https://duck.ac/submission/169475, https://duck.ac/submission/169546, https://duck.ac/submission/169603, https://duck.ac/submission/169736; inherited arithmetic/optimization lineage. saffah_v41f1017_agg4: https://duck.ac/submission/168279, https://duck.ac/submission/168372, https://duck.ac/submission/169066, https://duck.ac/submission/169131, https://duck.ac/submission/169410, https://duck.ac/submission/169507; inherited arithmetic/optimization lineage. saffah_codex61s_agg5: https://duck.ac/submission/168607, https://duck.ac/submission/168707, https://duck.ac/submission/169014, https://duck.ac/submission/169015, https://duck.ac/submission/169023, https://duck.ac/submission/169091, https://duck.ac/submission/169134, https://duck.ac/submission/169513, https://duck.ac/submission/169615, https://duck.ac/submission/169657, https://duck.ac/submission/169670; inherited arithmetic/optimization lineage. TSKY (With-Sky) https://github.com/With-Sky/HintFFT: inherited FFT library; complete MIT notice follows, body identification remains. This index supersedes historical attribution errors in inherited notices. */
/* 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.
*/
/* Idea / 思路: Keep the latest768-bit factorial leaves and pass their exact used-word count into paired native-to-decimal conversion. Start at active-1 rather than scan from the maximum object width, and consume the final native Q/T objects by reference to eliminate their complete copies. Preserve the existing direct Big-vector digit writes and reciprocal arithmetic. Purpose: independent exact QT checks including all wider maximum ranges, followed by complete GMP characters and output guards at powers/boundaries/requested scale, then official time. */
/* Idea / 思路: Use the actual factorial logarithmic mass for every scale, evaluated by a double Stirling expression with three correction terms. Invert this monotone model using four Newton steps and its analytic derivative instead of ten steps with three lgammal evaluations each. Subtrees of at most1024 terms below2^21 bypass the model: their exact logarithmic mass is below2048 radix10000 limbs, so the inherited balanced rule applies. Split choice only changes an exact binary-splitting association; all precision, native leaf capacity and output arithmetic remain unchanged. Experimental purpose: independent native QT cases and full GMP digit/guard checks at powers and the full target, then official measurement. */
#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.
constexpr 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
{
template<typename T,size_t ALIGN=64>
class AlignMem{
public:
using Ptr=T*;
using ConstPtr=const T*;
~AlignMem(){
if(ptr){
_mm_free(ptr);}};
AlignMem():ptr(nullptr),len(0){}
AlignMem(size_t n):ptr(reinterpret_cast<Ptr>(_mm_malloc(n*sizeof(T),ALIGN))),len(n){}
AlignMem(const AlignMem&)=delete;
AlignMem&operator=(const AlignMem&)=delete;
T&operator[](size_t i){
return ptr[i];}
const T&operator[](size_t i)const{
return ptr[i];}
Ptr begin(){
return ptr;}
Ptr end(){
return ptr+len;}
ConstPtr begin()const{
return ptr;}
ConstPtr end()const{
return ptr+len;}
size_t size()const{
return len;}
private:
T*ptr;
size_t len;};
template<typename YMM>
inline void transpose64_2X4(YMM&row0,YMM&row1){
auto t0=_mm256_unpacklo_pd(__m256d(row0),__m256d(row1));
auto t1=_mm256_unpackhi_pd(__m256d(row0),__m256d(row1));
row0=YMM(_mm256_permute2f128_pd(t0,t1,0x20));
row1=YMM(_mm256_permute2f128_pd(t0,t1,0x31));}
template<typename YMM>
inline void transpose64_4X2(YMM&row0,YMM&row1){
auto t0=_mm256_permute2f128_pd(__m256d(row0),__m256d(row1),0x20);
auto t1=_mm256_permute2f128_pd(__m256d(row0),__m256d(row1),0x31);
row0=YMM(_mm256_unpacklo_pd(t0,t1));
row1=YMM(_mm256_unpackhi_pd(t0,t1));}
template<typename YMM>
inline void transpose64_4X4(YMM&row0,YMM&row1,YMM&row2,YMM&row3){
auto t0=_mm256_unpacklo_pd(__m256d(row0),__m256d(row1));
auto t1=_mm256_unpackhi_pd(__m256d(row0),__m256d(row1));
auto t2=_mm256_unpacklo_pd(__m256d(row2),__m256d(row3));
auto t3=_mm256_unpackhi_pd(__m256d(row2),__m256d(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=double;
using F64X4=Float64X4;
Float64X4():data(_mm256_setzero_pd()){}
Float64X4(__m256d in_data):data(in_data){}
Float64X4(F64 in_data):data(_mm256_set1_pd(in_data)){}
Float64X4(const F64*in_data):data(_mm256_load_pd(in_data)){}
F64X4 operator+(const F64X4&other)const{
return _mm256_add_pd(data,other.data);}
F64X4 operator-(const F64X4&other)const{
return _mm256_sub_pd(data,other.data);}
F64X4 operator*(const F64X4&other)const{
return _mm256_mul_pd(data,other.data);}
F64X4 operator/(const F64X4&other)const{
return _mm256_div_pd(data,other.data);}
static F64X4 fmadd(const F64X4&a,const F64X4&b,const F64X4&c){
return _mm256_fmadd_pd(a.data,b.data,c.data);}
static F64X4 fmsub(const F64X4&a,const F64X4&b,const F64X4&c){
return _mm256_fmsub_pd(a.data,b.data,c.data);}
template<int N>
F64X4 permute4x64()const{
return _mm256_permute4x64_pd(data,N);}
F64X4 reverse()const{
return permute4x64<0b00011011>();}
void load(const F64*p){
data=_mm256_load_pd(p);}
void load1(const F64*p){
data=_mm256_broadcast_sd(p);}
void store(F64*p)const{
_mm256_store_pd(p,data);}
operator __m256d()const{
return data;}
__m256i toI64X4()const{
constexpr uint64_t mask=(uint64_t(1)<<52)-1;
constexpr uint64_t offset=(uint64_t(1)<<10)-1;
const __m256i f64bits=_mm256_castpd_si256(data);
__m256i tail=_mm256_and_si256(f64bits,_mm256_set1_epi64x(mask));
tail=_mm256_or_si256(tail,_mm256_set1_epi64x(mask+1));
__m256i exp=_mm256_srli_epi64(f64bits,52);
exp=_mm256_sub_epi64(_mm256_set1_epi64x(offset+52),exp);
return _mm256_srlv_epi64(tail,exp);}
private:
__m256d data;};
struct Complex64X4{
using C64X4=Complex64X4;
using F64X4=Float64X4;
using F64=double;
Complex64X4(){}
Complex64X4(F64X4 real,F64X4 imag):real(real),imag(imag){}
Complex64X4(const F64*p):real(p),imag(p+4){}
Complex64X4(const F64*p_real,const F64*p_imag):real(p_real),imag(p_imag){}
C64X4 operator+(const C64X4&other)const{
return C64X4(real+other.real,imag+other.imag);}
C64X4 operator-(const C64X4&other)const{
return C64X4(real-other.real,imag-other.imag);}
C64X4 operator*(const F64X4&other)const{
return C64X4(real*other,imag*other);}
C64X4 mul(const C64X4&other)const{
const F64X4 ii=imag*other.imag;
const F64X4 ri=real*other.imag;
const F64X4 r=F64X4::fmsub(real,other.real,ii);
const F64X4 i=F64X4::fmadd(imag,other.real,ri);
return C64X4(r,i);}
C64X4 mulConj(const C64X4&other)const{
const F64X4 ii=imag*other.imag;
const F64X4 ri=real*other.imag;
const F64X4 r=F64X4::fmadd(real,other.real,ii);
const F64X4 i=F64X4::fmsub(imag,other.real,ri);
return C64X4(r,i);}
C64X4 reverse()const{
return C64X4(real.reverse(),imag.reverse());}
void set1(F64 real_in,F64 imag_in){
real=F64X4(real_in);
imag=F64X4(imag_in);}
template<typename T>
void load(const T*p,std::false_type){
this->load(p);}
template<typename T>
void load(const T*p,std::true_type){
this->load(p);
*this=this->toRRIIPermu();}
template<typename T>
void load(const T*p){
real.load(reinterpret_cast<const F64*>(p));
imag.load(reinterpret_cast<const F64*>(p)+4);}
void load1(const F64*real_p,const F64*imag_p){
real.load1(real_p);
imag.load1(imag_p);}
template<typename T>
void store(T*p,std::false_type)const{
this->store(p);}
template<typename T>
void store(T*p,std::true_type)const{
this->toRIRIPermu().store(p);}
template<typename T>
void store(T*p)const{
real.store(reinterpret_cast<F64*>(p));
imag.store(reinterpret_cast<F64*>(p)+4);}
C64X4 toRIRIPermu()const{
C64X4 res= *this;
transpose64_2X4(res.real,res.imag);
return res;}
C64X4 toRRIIPermu()const{
C64X4 res= *this;
transpose64_4X2(res.real,res.imag);
return res;}
C64X4 transToI64(std::false_type)const{
return*this;}
C64X4 transToI64(std::true_type)const{
constexpr int64_t F1_2=4602678819172646912;
auto F1_2X4=F64X4(__m256d(_mm256_set1_epi64x(F1_2)));
auto real_i64=(real+F1_2X4).toI64X4();
auto imag_i64=(imag+F1_2X4).toI64X4();
return C64X4(__m256d(real_i64),__m256d(imag_i64));}
F64X4 real,imag;};
using Float32=float;
using Float64=double;
constexpr Float64 HINT_PI=3.141592653589793238462643;
constexpr Float64 HINT_2PI=HINT_PI*2;
constexpr Float64 COS_PI_8=0.707106781186547524400844;
template<typename T>
constexpr T int_floor2(T n){
constexpr int bits=sizeof(n)*8;
for(int i=1;i<bits;i*=2){
n|=(n>>i);}
return(n>>1)+1;}
template<typename T>
constexpr T int_ceil2(T n){
constexpr int bits=sizeof(n)*8;
n--;
for(int i=1;i<bits;i*=2){
n|=(n>>i);}
return n+1;}
template<typename IntTy>
constexpr bool is_2pow(IntTy n){
return n!=0&&(n&(n-1))==0;}
template<typename T>
constexpr int hint_log2(T n){
constexpr int bits=sizeof(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;}}
return l;}
constexpr uint32_t crc32(const char*str){
uint32_t crc=0xFFFFFFFF;
while(*str!='\0'){
crc^= *str;
for(int i=0;i<8;++i){
crc=(crc>>1)^(0-(crc&1))&0xEDB88320;}
str++;}
return~crc;}
namespace transform{
template<typename T>
inline 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;
template<typename Float,size_t OMEGA_LEN>
class TableFix{
alignas(64)Float table[OMEGA_LEN*2];
public:
TableFix(size_t theta_divider,size_t factor,size_t stride){
const Float theta= -HINT_2PI*factor/theta_divider;
for(size_t begin=0,index=0;begin<OMEGA_LEN*2;begin+=stride*2)
{
for(size_t j=0;j<stride;j++,index++)
{
table[begin+j]=std::cos(theta*index);
table[begin+j+stride]=std::sin(theta*index);}}}
constexpr const Float&operator[](size_t index)const{
return table[index];}};
void initOmegaX4(F64*arr,size_t fft_len,int table_len,int factor){
table_len/=4;
const F64 theta= -HINT_2PI*factor/fft_len;
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(size_t begin=1;begin<table_len;begin*=2){
size_t nth=begin*4;
C64X4 unit;
unit.set1(std::cos(theta*nth),std::sin(theta*nth));
for(size_t i=0;i<begin;i++)
{
arrx4[begin+i]=arrx4[i].mul(unit);}}}
template<typename Float,int LOG_BEGIN,int LOG_END,int DIV>
class TableFixMulti{
static_assert(LOG_END>=LOG_BEGIN);
static_assert(is_2pow(DIV));
static constexpr size_t TABLE_CPX_LEN=(size_t(1)<<(LOG_END+1))/DIV;
alignas(64)Float table[TABLE_CPX_LEN*2];
public:
TableFixMulti(size_t factor,size_t stride=4){
initBottomUp(factor,stride);}
void initBottomUp(size_t factor,size_t stride){
static_assert(std::is_same<Float,Float64>::value);
size_t len=size_t(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=size_t(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);}}}
constexpr const Float*getBeginLog(int log_rank)const{
return getBegin(size_t(1)<<log_rank);}
constexpr Float*getBeginLog(int log_rank){
return getBegin(size_t(1)<<log_rank);}
constexpr const Float*getBegin(size_t rank)const{
return&table[rank*2/DIV];}
constexpr Float*getBegin(size_t rank){
return&table[rank*2/DIV];}};
template<int CACHE_LOG_LEN>
class FFTSqrtTableC64X4{
public:
using F64=double;
using C64=std::complex<double>;
using C64X4=hintpowfft::Complex64X4;
static constexpr size_t CACHE_LEN=size_t(1)<<CACHE_LOG_LEN;
static constexpr size_t MASK=CACHE_LEN-1;
static constexpr size_t C4_COUNT=sizeof(C64X4)/sizeof(C64);
~FFTSqrtTableC64X4(){
if(high)
{
delete[]high;}}
FFTSqrtTableC64X4(){}
FFTSqrtTableC64X4(size_t fft_len,int len_div,int factor){
init(fft_len,len_div,factor);}
void init(size_t fft_len,int len_div,int factor){
size_t table_len=fft_len/len_div;
size_t 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,fft_len,low_len,factor);
const F64 theta= -HINT_2PI*factor/fft_len;
high[0]=C64(1,0);
for(size_t begin=1;begin<high_len;begin*=2)
{
C64 unit=std::polar<F64>(1.0,theta*begin*low_len);
for(size_t i=0;i<begin;i++)
{
high[i+begin]=high[i]*unit;}}}
C64X4 operator[](size_t i)const{
C64X4 hi;
auto p=reinterpret_cast<const F64*>(&high[i>>CACHE_LOG_LEN]);
hi.load1(p,p+1);
return low[i&MASK].mul(hi);}
private:
alignas(64)C64X4 low[CACHE_LEN];
C64*high=nullptr;};
template<int DIV,int LOG_BEGIN,int LOG_MAX,int CACHE_LOG_LEN>
class FFTTableSqrt{
using TableLong=FFTSqrtTableC64X4<CACHE_LOG_LEN>;
static constexpr size_t SHORT_LEN=size_t(1)<<LOG_BEGIN;
static constexpr size_t TABLE_LEN=LOG_MAX-LOG_BEGIN+1;
public:
FFTTableSqrt(int factor){
for(int i=0;i<TABLE_LEN;i++)
{
size_t fft_len=SHORT_LEN<<i;
table[i].init(fft_len,DIV,factor);}}
const TableLong&operator[](int log_len)const{
log_len-=LOG_BEGIN;
return table[log_len];}
TableLong&operator[](int log_len){
log_len-=LOG_BEGIN;
return table[log_len];}
private:
TableLong table[TABLE_LEN];};
struct FFT{
template<typename Float>
static 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;}
template<typename Float>
static 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;}
template<typename Float>
static 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);}
template<typename Float>
static 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);}
template<typename Float>
static 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);}
template<typename Float>
static 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{
static constexpr int LOG_SHORT=7,LOG_MID=25-crc32(statement)%15,LOG_MAX=25,LOG_CACHE=8;
static constexpr size_t SHORT_LEN=size_t(1)<<LOG_SHORT,MID_LEN=size_t(1)<<LOG_MID,MAX_LEN=size_t(1)<<LOG_MAX;
using TableFix4=const TableFix<Float64,4>;
using TableFix8=const TableFix<Float64,8>;
using TableMulti1=const TableFixMulti<Float64,LOG_SHORT+1,LOG_MID,4>;
using TableMulti2=const TableFixMulti<Float64,6,LOG_SHORT+1,4>;
using TableMulti3=const TableFixMulti<Float64,6,LOG_SHORT,4>;
using TableSqrt=const FFTTableSqrt<4,LOG_MID+1,LOG_MAX,LOG_CACHE>;
static TableFix4 table_8,table_16_1,table_16_3;
static TableFix8 table_32_1,table_32_3;
static TableMulti2 multi_table_2;
static TableMulti3 multi_table_3;
static TableMulti1 multi_table_1;
static TableSqrt sqrt_table_1;
static constexpr const 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];
static 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);}
static 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);}
static 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);}
static 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);}
static 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;}
static 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;}
static 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);}
static 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;}
template<typename F32,typename F16>
static void fftTiny(Float64 in_out[],size_t 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);}}}
static void difIter(Float64 in_out[],size_t float_len){
size_t fft_len=float_len/2;
C64X4 c0,c1,c2,c3;
size_t stride=fft_len/2;
auto it0=in_out,it1=it0+stride,it2=it1+stride,it3=it2+stride;
for(size_t rank=fft_len;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);}
static void iditIter(Float64 in_out[],size_t float_len){
size_t fft_len=float_len/2;
size_t rank=hint_log2(fft_len)%2==0?64:128;
fftTiny(in_out,float_len,idit32,idit16);
for(;rank<=fft_len;rank*=4)
{
const size_t 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; \
size_t indx = 0; \
for (auto end = it1; FROM_RIRI_PERM && it0 < end; it0 += 8, it1 += 8, it2 += 8, it3 += 8, indx++) \
{ \
if(stride>64){_mm_prefetch((const char*)(it0+128),_MM_HINT_T0);_mm_prefetch((const char*)(it1+128),_MM_HINT_T0);_mm_prefetch((const char*)(it2+128),_MM_HINT_T0);_mm_prefetch((const char*)(it3+128),_MM_HINT_T0);} \
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++) \
{ \
if(stride>64){_mm_prefetch((const char*)(it0+128),_MM_HINT_T0);_mm_prefetch((const char*)(it1+128),_MM_HINT_T0);_mm_prefetch((const char*)(it2+128),_MM_HINT_T0);_mm_prefetch((const char*)(it3+128),_MM_HINT_T0);} \
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; \
size_t indx = 0; \
for (auto end = it1; it0 < end; it0 += 8, it1 += 8, it2 += 8, it3 += 8, indx++) \
{ \
if(stride>64){_mm_prefetch((const char*)(it0+128),_MM_HINT_T0);_mm_prefetch((const char*)(it1+128),_MM_HINT_T0);_mm_prefetch((const char*)(it2+128),_MM_HINT_T0);_mm_prefetch((const char*)(it3+128),_MM_HINT_T0);} \
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)
template<bool FROM_RIRI_PERM=false>
static void difRecMid(Float64 in_out[],size_t float_len){
const size_t fft_len=float_len/2;
if(fft_len<=SHORT_LEN)
{
difIter(in_out,float_len);
return;}
using FromRIRI=std::integral_constant<bool,FROM_RIRI_PERM>;
auto table1=reinterpret_cast<const C64X4*>(multi_table_1.getBegin(fft_len));
const size_t stride=float_len/4;
difLayer(difRecMid,in_out,stride,table1);}
template<bool TO_RIRI_PERM=false,bool TO_INT64=false>
static void iditRecMid(Float64 in_out[],size_t float_len){
const size_t fft_len=float_len/2;
if(fft_len<=SHORT_LEN)
{
iditIter(in_out,float_len);
return;}
using ToRIRI=std::integral_constant<bool,TO_RIRI_PERM>;
using ToI64=std::integral_constant<bool,TO_INT64>;
const size_t stride=float_len/4;
auto table1=reinterpret_cast<const C64X4*>(multi_table_1.getBegin(fft_len));
iditLayer(iditRecMid,in_out,stride,table1);}
template<bool FROM_RIRI_PERM=false>
static void difRecLong(Float64 in_out[],size_t float_len){
const size_t fft_len=float_len/2;
if(fft_len<=MID_LEN)
{
difRecMid<FROM_RIRI_PERM>(in_out,float_len);
return;}
using FromRIRI=std::integral_constant<bool,FROM_RIRI_PERM>;
const auto&table1=sqrt_table_1[hint_log2(fft_len)];
const size_t stride=float_len/4;
difLayer(difRecLong,in_out,stride,table1);}
template<bool TO_RIRI_PERM=false,bool TO_INT64=false>
static void iditRecLong(Float64 in_out[],size_t float_len){
const size_t fft_len=float_len/2;
if(fft_len<=MID_LEN)
{
iditRecMid<TO_RIRI_PERM,TO_INT64>(in_out,float_len);
return;}
using ToRIRI=std::integral_constant<bool,TO_RIRI_PERM>;
using ToI64=std::integral_constant<bool,TO_INT64>;
const size_t stride=float_len/4;
const auto&table1=sqrt_table_1[hint_log2(fft_len)];
iditLayer(iditRecLong,in_out,stride,table1);}};
#undef difLayer
#undef iditLayer
constexpr int FFTAVX::LOG_SHORT,FFTAVX::LOG_MID,FFTAVX::LOG_MAX,FFTAVX::LOG_CACHE;
constexpr size_t 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);
constexpr uint32_t bitrev32(uint32_t n){
constexpr uint32_t mask55=0x55555555;
constexpr uint32_t mask33=0x33333333;
constexpr uint32_t mask0f=0x0f0f0f0f;
constexpr uint32_t 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);
return(n<<16)|(n>>16);}
constexpr uint32_t bitrev(uint32_t n,int len){
return bitrev32(n)>>(32-len);}
template<int MAX_LOG_LEN,int DIV>
class BinRevTableC64X4HP{
public:
static constexpr int LOG_BLOCK=2,BLOCK=1<<LOG_BLOCK;
static constexpr size_t MAX_LEN=size_t(1)<<MAX_LOG_LEN;
struct Unit{
C64 units[MAX_LOG_LEN]{};
F64 block[BLOCK*2]{};
Unit()
{
constexpr F64 factor=F64(1)/DIV;
for(int i=0;i<MAX_LOG_LEN;i++)
{
units[i]=getOmega(size_t(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,sizeof(unit_table.block));}
void reset(size_t i=0){
if(i==0)
{
pop=0,index=i;
return;}
pop=1,index=i/BLOCK;
int zero=__builtin_ctzll(index);
auto fp=reinterpret_cast<const 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<const F64*>(&unit_table.units[zero+2]);
unit4.load1(fp,fp+1);
pop-=zero;
table[pop+1]=table[pop].mul(unit4);
pop++;
return res;}
static C64 getOmega(size_t n,size_t index,F64 factor=1){
F64 theta= -HINT_2PI*index/n;
return std::polar<F64>(1,theta*factor);}
private:
alignas(64)static const Unit unit_table;
alignas(64)C64X4 table[MAX_LOG_LEN];
size_t index;
int pop;
int log_max_iter,log_fft_len;};
template<int MAX_LOG_LEN,int DIV>
const typename BinRevTableC64X4HP<MAX_LOG_LEN,DIV>::Unit BinRevTableC64X4HP<MAX_LOG_LEN,DIV>::unit_table;
template<size_t RI_DIFF=1,typename FloatTy>
inline void dot_rfft(FloatTy*inout0,FloatTy*inout1,const FloatTy*in0,const FloatTy*in1,
const std::complex<FloatTy> &omega,const FloatTy inv=1){
using Complex=std::complex<FloatTy>;
auto addConj=[](Complex c0,Complex c1){return Complex(c0.real()+c1.real(),c0.imag()-c1.imag());};
Complex 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;
const auto inv2=inv+inv;
x0=(t2-x1)*inv,x1=Complex(t0.real()-t1.real(),t0.imag()+t1.imag())*inv2;
Complex 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();}
inline void dot_rfftX4(F64*inout0,F64*inout1,const F64*in0,const F64*in1,const C64X4&omega,const F64X4&inv){
auto addConj=[](const C64X4&x0,const C64X4&x1){
return 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);
const 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);}
inline void real_dot_binrev4(Float64 in_out[],Float64 in[],size_t 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);
constexpr Float64 COS_16_1=0.92387953251128675612818318939;
constexpr 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);
const Float64X4 inv4=F64X4(0.5/float_len);
BinRevTableC64X4HP<28,1>table;
for(size_t 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);}}}
template<bool TO_INT=false>
inline void real_conv_avx(F64*in_out1,F64*in2,size_t 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);}}}}
#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 Complex=std::complex<double>;
struct Complex2
{
__m256d data;
Complex2()
{
data=_mm256_setzero_pd();
}
Complex2(double input)
{
data=_mm256_set1_pd(input);
}
Complex2(__m256d input)
{
data=input;
}
Complex2(const Complex2&input)
{
data=input.data;
}
Complex2(double const*ptr)
{
data=_mm256_loadu_pd(ptr);
}
Complex2(Complex a)
{
data=_mm256_broadcast_pd((__m128d*)&a);
}
Complex2(const Complex*ptr)
{
data=_mm256_loadu_pd((const double*)ptr);
}
void clr()
{
data=_mm256_setzero_pd();
}
void store(Complex*a)const
{
_mm256_storeu_pd((double*)a,data);
}
template<int M>
Complex2 element_permute()const
{
return _mm256_permute_pd(data,M);
}
Complex2 all_real()const
{
return _mm256_movedup_pd(data);
}
Complex2 all_imag()const
{
return element_permute<0XF>();
}
Complex2 swap()const
{
return element_permute<0X5>();
}
Complex2 mul_neg_i()const
{
static const __m256d subber{};
return Complex2(_mm256_addsub_pd(subber,data)).swap();
}
Complex2 operator+(Complex2 input)const
{
return _mm256_add_pd(data,input.data);
}
Complex2 operator-(Complex2 input)const
{
return _mm256_sub_pd(data,input.data);
}
Complex2 operator*(Complex2 input)const
{
auto imag=_mm256_mul_pd(all_imag().data,input.swap().data);
return _mm256_fmaddsub_pd(all_real().data,input.data,imag);
}
Complex2 operator/(Complex2 input)const
{
return _mm256_div_pd(data,input.data);
}
};
#endif
namespace hint
{
using UINT_8=uint8_t;
using UINT_16=uint16_t;
using UINT_32=uint32_t;
using UINT_64=uint64_t;
using INT_32=int32_t;
using INT_64=int64_t;
using LONG=long;
using Complex=std::complex<double>;
constexpr double HINT_PI=3.1415926535897932384626433832795;
constexpr double HINT_2PI=HINT_PI*2;
template<typename T>
constexpr T min_2pow(T n)
{
T res=1;
while(res<n)
{
res*=2;
}
return res;
}
template<typename T>
inline void ary_clr(T*ptr,size_t len)
{
memset(ptr,0,len*sizeof(T));
}
template<typename T>
constexpr bool is_neg(T x)
{
return x<0;
}
template<typename T>
constexpr size_t hint_log2(T n)
{
T res=0;
while(n>1)
{
n/=2;
res++;
}
return res;
}
template<typename T>
constexpr bool is_odd(T x)
{
return static_cast<bool>(x&1);
}
template<typename T>
constexpr std::pair<T,T>div_mod(T a,T b)
{
return std::make_pair(a/b,a%b);
}
template<typename T>
void ary_copy(T*target,const T*source,size_t len)
{
if(len==0||target==source)
{
return;
}
if(len>=INT64_MAX)
{
throw("Ary too long\n");
}
std::memcpy(target,source,len*sizeof(T));
}
template<typename T>
inline T*ary_realloc(T*ptr,size_t len)
{
if(len*sizeof(T)<INT64_MAX)
{
ptr=static_cast<T*>(realloc(ptr,len*sizeof(T)));
}
if(ptr==nullptr)
{
throw("realloc error");
}
return ptr;
}
template<typename T>
constexpr T max_2pow(T n)
{
T res=1;
res<<=(sizeof(T)*8-1);
while(res>n)
{
res/=2;
}
return res;
}
constexpr UINT_64 qpow(UINT_64 m,UINT_64 n,UINT_64 mod)
{
if(m<=1)
{
return m;
}
UINT_64 result=1;
while(n>0)
{
if((n&1)!=0)
{
result=result*m%mod;
}
m=m*m%mod;
n>>=1;
}
return result;
}
constexpr UINT_64 mod_inv(UINT_64 n,UINT_64 mod)
{
return qpow(n,mod-2,mod);
}
template<typename T>
inline void com_ary_combine_copy(Complex*target,const T&source1,size_t len1,const T&source2,size_t len2)
{
size_t min_len=std::min(len1,len2);
size_t i=0;
while(i<min_len)
{
target[i]=Complex(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<Complex>>table1;
std::vector<std::vector<Complex>>table3;
INT_32 max_log_size=2;
INT_32 cur_log_size=2;
static constexpr size_t FAC=1;
ComplexTableY(const ComplexTableY&)=delete;
ComplexTableY&operator=(const ComplexTableY&)=delete;
public:
~ComplexTableY(){}
ComplexTableY(UINT_32 max_shift)
{
max_shift=std::max<size_t>(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<Complex>{1};
table1[2]=table3[2]=std::vector<Complex>{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++)
{
size_t len=1ull<<i,vec_size=len*FAC/4;
table1[i].resize(vec_size);
table3[i].resize(vec_size);
table1[i][0]=table3[i][0]=Complex(1,0);
for(size_t pos=0;pos<vec_size/2;pos++)
{
table1[i][pos*2]=table1[i-1][pos];
table3[i][pos*2]=table3[i-1][pos];
}
for(size_t pos=1;pos<vec_size/2;pos+=2)
{
double cos_theta=std::cos(HINT_2PI*pos/len);
double sin_theta=std::sin(HINT_2PI*pos/len);
table1[i][pos]=Complex(cos_theta,-sin_theta);
table1[i][vec_size-pos]=Complex(sin_theta,-cos_theta);
}
table1[i][vec_size/2]=std::conj(unit_root(8,1));
for(size_t pos=1;pos<vec_size/2;pos+=2)
{
Complex tmp=get_omega(i,pos*3);
table3[i][pos]=tmp;
table3[i][vec_size-pos]=Complex(tmp.imag(),tmp.real());
}
table3[i][vec_size/2]=std::conj(unit_root(8,3));
}
cur_log_size=std::max(cur_log_size,shift);
}
static Complex unit_root(double theta)
{
return std::polar<double>(1.0,theta);
}
static Complex unit_root(size_t m,size_t n)
{
return unit_root((HINT_2PI*n)/m);
}
Complex get_omega(UINT_32 shift,size_t n)const
{
size_t rank=1ull<<shift;
const size_t rank_ff=rank-1,quad_n=n<<2;
size_t zone=quad_n>>shift;
if((quad_n&rank_ff)==0)
{
static constexpr Complex ONES[4]={Complex(1,0),Complex(0,-1),Complex(-1,0),Complex(0,1)};
return ONES[zone];
}
Complex 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());
}
}
return tmp;
}
Complex get_omega3(UINT_32 shift,size_t n)const
{
return table3[shift][n];
}
Complex2 get_omegaX2(UINT_32 shift,size_t n)const
{
return Complex2(table1[shift].data()+n);
}
Complex2 get_omega3X2(UINT_32 shift,size_t n)const
{
return Complex2(table3[shift].data()+n);
}
};
constexpr size_t lut_max_rank=23;
static ComplexTableY TABLE(lut_max_rank);
template<typename T>
void binary_reverse_swap(T&ary,size_t len)
{
size_t i=0;
for(size_t j=1;j<len-1;j++)
{
size_t k=len>>1;
i^=k;
while(k>i)
{
k>>=1;
i^=k;
};
if(j<i)
{
std::swap(ary[i],ary[j]);
}
}
}
template<typename SizeType=UINT_32,typename T>
void quaternary_reverse_swap(T&ary,size_t 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;
}
template<typename T>
inline void fft_2point(T&sum,T&diff)
{
T tmp0=sum;
T tmp1=diff;
sum=tmp0+tmp1;
diff=tmp0-tmp1;
}
inline void fft_4point(Complex*input,size_t rank=1)
{
Complex tmp0=input[0];
Complex tmp1=input[rank];
Complex tmp2=input[rank*2];
Complex tmp3=input[rank*3];
fft_2point(tmp0,tmp2);
fft_2point(tmp1,tmp3);
tmp3=Complex(tmp3.imag(),-tmp3.real());
input[0]=tmp0+tmp1;
input[rank]=tmp2+tmp3;
input[rank*2]=tmp0-tmp1;
input[rank*3]=tmp2-tmp3;
}
inline void fft_dit_4point(Complex*input,size_t rank=1)
{
Complex tmp0=input[0];
Complex tmp1=input[rank];
Complex tmp2=input[rank*2];
Complex tmp3=input[rank*3];
fft_2point(tmp0,tmp1);
fft_2point(tmp2,tmp3);
tmp3=Complex(tmp3.imag(),-tmp3.real());
input[0]=tmp0+tmp2;
input[rank]=tmp1+tmp3;
input[rank*2]=tmp0-tmp2;
input[rank*3]=tmp1-tmp3;
}
inline void fft_dit_8point(Complex*input,size_t rank=1)
{
Complex tmp0=input[0];
Complex tmp1=input[rank];
Complex tmp2=input[rank*2];
Complex tmp3=input[rank*3];
Complex tmp4=input[rank*4];
Complex tmp5=input[rank*5];
Complex tmp6=input[rank*6];
Complex tmp7=input[rank*7];
fft_2point(tmp0,tmp1);
fft_2point(tmp2,tmp3);
fft_2point(tmp4,tmp5);
fft_2point(tmp6,tmp7);
tmp3=Complex(tmp3.imag(),-tmp3.real());
tmp7=Complex(tmp7.imag(),-tmp7.real());
fft_2point(tmp0,tmp2);
fft_2point(tmp1,tmp3);
fft_2point(tmp4,tmp6);
fft_2point(tmp5,tmp7);
static constexpr double cos_1_8=0.70710678118654752440084436210485;
tmp5=cos_1_8*Complex(tmp5.imag()+tmp5.real(),tmp5.imag()-tmp5.real());
tmp6=Complex(tmp6.imag(),-tmp6.real());
tmp7= -cos_1_8*Complex(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;
}
inline void fft_dif_4point(Complex*input,size_t rank=1)
{
Complex tmp0=input[0];
Complex tmp1=input[rank];
Complex tmp2=input[rank*2];
Complex tmp3=input[rank*3];
fft_2point(tmp0,tmp2);
fft_2point(tmp1,tmp3);
tmp3=Complex(tmp3.imag(),-tmp3.real());
input[0]=tmp0+tmp1;
input[rank]=tmp0-tmp1;
input[rank*2]=tmp2+tmp3;
input[rank*3]=tmp2-tmp3;
}
inline void fft_dif_8point(Complex*input,size_t rank=1)
{
Complex tmp0=input[0];
Complex tmp1=input[rank];
Complex tmp2=input[rank*2];
Complex tmp3=input[rank*3];
Complex tmp4=input[rank*4];
Complex tmp5=input[rank*5];
Complex tmp6=input[rank*6];
Complex tmp7=input[rank*7];
fft_2point(tmp0,tmp4);
fft_2point(tmp1,tmp5);
fft_2point(tmp2,tmp6);
fft_2point(tmp3,tmp7);
static constexpr double cos_1_8=0.70710678118654752440084436210485;
tmp5=cos_1_8*Complex(tmp5.imag()+tmp5.real(),tmp5.imag()-tmp5.real());
tmp6=Complex(tmp6.imag(),-tmp6.real());
tmp7= -cos_1_8*Complex(tmp7.real()-tmp7.imag(),tmp7.real()+tmp7.imag());
fft_2point(tmp0,tmp2);
fft_2point(tmp1,tmp3);
fft_2point(tmp4,tmp6);
fft_2point(tmp5,tmp7);
tmp3=Complex(tmp3.imag(),-tmp3.real());
tmp7=Complex(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;
}
inline void fft_radix2_dit_butterfly(Complex omega,Complex*input,size_t rank)
{
Complex tmp0=input[0];
Complex tmp1=input[rank]*omega;
input[0]=tmp0+tmp1;
input[rank]=tmp0-tmp1;
}
inline void fft_radix2_dif_butterfly(Complex omega,Complex*input,size_t rank)
{
Complex tmp0=input[0];
Complex tmp1=input[rank];
input[0]=tmp0+tmp1;
input[rank]=(tmp0-tmp1)*omega;
}
inline void fft_split_radix_dit_butterfly(Complex omega,Complex omega_cube,
Complex*input,size_t rank)
{
Complex tmp0=input[0];
Complex tmp1=input[rank];
Complex tmp2=input[rank*2]*omega;
Complex tmp3=input[rank*3]*omega_cube;
fft_2point(tmp2,tmp3);
tmp3=Complex(tmp3.imag(),-tmp3.real());
input[0]=tmp0+tmp2;
input[rank]=tmp1+tmp3;
input[rank*2]=tmp0-tmp2;
input[rank*3]=tmp1-tmp3;
}
inline void fft_split_radix_dif_butterfly(Complex omega,Complex omega_cube,
Complex*input,size_t rank)
{
Complex tmp0=input[0];
Complex tmp1=input[rank];
Complex tmp2=input[rank*2];
Complex tmp3=input[rank*3];
fft_2point(tmp0,tmp2);
fft_2point(tmp1,tmp3);
tmp3=Complex(tmp3.imag(),-tmp3.real());
input[0]=tmp0;
input[rank]=tmp1;
input[rank*2]=(tmp2+tmp3)*omega;
input[rank*3]=(tmp2-tmp3)*omega_cube;
}
inline void fft_split_radix_dit_butterfly(Complex2 omega,Complex2 omega_cube,
Complex*input,size_t rank)
{
Complex2 tmp0=input;
Complex2 tmp1=input+rank;
Complex2 tmp2=Complex2(input+rank*2)*omega;
Complex2 tmp3=Complex2(input+rank*3)*omega_cube;
fft_2point(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);
}
inline void fft_split_radix_dif_butterfly(Complex2 omega,Complex2 omega_cube,
Complex*input,size_t rank)
{
Complex2 tmp0=(input);
Complex2 tmp1=(input+rank);
Complex2 tmp2=(input+rank*2);
Complex2 tmp3=(input+rank*3);
fft_2point(tmp0,tmp2);
fft_2point(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);
}
inline void fft_radix4_dit_butterfly(Complex omega,Complex omega_sqr,Complex omega_cube,
Complex*input,size_t rank)
{
Complex tmp0=input[0];
Complex tmp1=input[rank]*omega;
Complex tmp2=input[rank*2]*omega_sqr;
Complex tmp3=input[rank*3]*omega_cube;
fft_2point(tmp0,tmp2);
fft_2point(tmp1,tmp3);
tmp3=Complex(tmp3.imag(),-tmp3.real());
input[0]=tmp0+tmp1;
input[rank]=tmp2+tmp3;
input[rank*2]=tmp0-tmp1;
input[rank*3]=tmp2-tmp3;
}
inline void fft_radix4_dif_butterfly(Complex omega,Complex omega_sqr,Complex omega_cube,
Complex*input,size_t rank)
{
Complex tmp0=input[0];
Complex tmp1=input[rank];
Complex tmp2=input[rank*2];
Complex tmp3=input[rank*3];
fft_2point(tmp0,tmp2);
fft_2point(tmp1,tmp3);
tmp3=Complex(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;
}
inline void fft_conj(Complex*input,size_t fft_len,double div=1)
{
for(size_t i=0;i<fft_len;i++)
{
input[i]=std::conj(input[i])/div;
}
}
inline void fft_normalize(Complex*input,size_t fft_len)
{
double len=static_cast<double>(fft_len);
for(size_t i=0;i<fft_len;i++)
{
input[i]/=len;
}
}
template<size_t LEN>
void fft_split_radix_dit_template(Complex*input)
{
constexpr size_t log_len=hint_log2(LEN);
constexpr size_t half_len=LEN/2,quarter_len=LEN/4;
fft_split_radix_dit_template<half_len>(input);
fft_split_radix_dit_template<quarter_len>(input+half_len);
fft_split_radix_dit_template<quarter_len>(input+half_len+quarter_len);
for(size_t 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);
}
}
template<>
void fft_split_radix_dit_template<0>(Complex*input){}
template<>
void fft_split_radix_dit_template<1>(Complex*input){}
template<>
void fft_split_radix_dit_template<2>(Complex*input)
{
fft_2point(input[0],input[1]);
}
template<>
void fft_split_radix_dit_template<4>(Complex*input)
{
fft_dit_4point(input,1);
}
template<>
void fft_split_radix_dit_template<8>(Complex*input)
{
fft_dit_8point(input,1);
}
template<size_t LEN>
void fft_split_radix_dif_template(Complex*input)
{
constexpr size_t log_len=hint_log2(LEN);
constexpr size_t half_len=LEN/2,quarter_len=LEN/4;
for(size_t 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);
}
fft_split_radix_dif_template<half_len>(input);
fft_split_radix_dif_template<quarter_len>(input+half_len);
fft_split_radix_dif_template<quarter_len>(input+half_len+quarter_len);
}
template<>
void fft_split_radix_dif_template<0>(Complex*input){}
template<>
void fft_split_radix_dif_template<1>(Complex*input){}
template<>
void fft_split_radix_dif_template<2>(Complex*input)
{
fft_2point(input[0],input[1]);
}
template<>
void fft_split_radix_dif_template<4>(Complex*input)
{
fft_dif_4point(input,1);
}
template<>
void fft_split_radix_dif_template<8>(Complex*input)
{
fft_dif_8point(input,1);
}
template<size_t LEN=1>
void fft_dit_template(Complex*input,size_t fft_len)
{
if(fft_len>LEN)
{
fft_dit_template<LEN*2>(input,fft_len);
return;
}
TABLE.expand(hint_log2(LEN));
fft_split_radix_dit_template<LEN>(input);
}
template<>
void fft_dit_template<1<<24>(Complex*input,size_t fft_len){}
template<size_t LEN=1>
void fft_dif_template(Complex*input,size_t fft_len)
{
if(fft_len>LEN)
{
fft_dif_template<LEN*2>(input,fft_len);
return;
}
TABLE.expand(hint_log2(LEN));
fft_split_radix_dif_template<LEN>(input);
}
template<>
void fft_dif_template<1<<24>(Complex*input,size_t fft_len){}
inline void fft_dit(Complex*input,size_t fft_len,bool bit_rev=true)
{
fft_len=max_2pow(fft_len);
if(bit_rev)
{
binary_reverse_swap(input,fft_len);
}
fft_dit_template<1>(input,fft_len);
}
inline void fft_dif(Complex*input,size_t fft_len,bool bit_rev=true)
{
fft_len=max_2pow(fft_len);
fft_dif_template<1>(input,fft_len);
if(bit_rev)
{
binary_reverse_swap(input,fft_len);
}
}
}
template<UINT_64 BASE,typename T>
constexpr void save_num_to_ary(T ary[],UINT_64 num,size_t digit)
{
size_t i=digit;
while(i>0)
{
i--;
ary[i]=num%BASE;
num/=BASE;
}
}
UINT_64 stoui64(const std::string::const_iterator&begin,
const std::string::const_iterator&end,const 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;
}
}
return result;
}
UINT_64 stoui64(const std::string&str,const UINT_32 base=10)
{
return 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;
}
return result;
}
template<typename T=UINT_32,typename SIZE_TYPE=UINT_32>
class HintVector
{
private:
T*ary_ptr=nullptr;
SIZE_TYPE sign_n_len=0;
SIZE_TYPE size=0;
public:
~HintVector()
{
if(ary_ptr!=nullptr)
{
delete[]ary_ptr;
ary_ptr=nullptr;
}
}
HintVector()
{
ary_ptr=nullptr;
}
HintVector(SIZE_TYPE ele_size)
{
if(ele_size>0)
{
resize(ele_size);
}
}
HintVector(SIZE_TYPE ele_size,T ele)
{
if(ele_size>0)
{
resize(ele_size);
change_length(ele_size);
fill_element(ele,ele_size);
}
}
HintVector(const T*ary,SIZE_TYPE 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(const HintVector&input)
{
if(input.ary_ptr!=nullptr)
{
if(ary_ptr!=nullptr)
{
delete[]ary_ptr;
}
ary_ptr=nullptr;
size_t 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=(const HintVector&input)
{
if(this!= &input)
{
if(ary_ptr!=nullptr)
{
delete[]ary_ptr;
}
ary_ptr=nullptr;
size_t len=input.length();
resize(len);
change_length(len);
change_sign(input.sign());
ary_copy(ary_ptr,input.ary_ptr,len);
}
return*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;
}
return*this;
}
T&operator[](SIZE_TYPE index)const
{
return ary_ptr[index];
}
T*data()const
{
return ary_ptr;
}
static SIZE_TYPE size_generator(SIZE_TYPE new_size)
{
constexpr SIZE_TYPE SIZE_TYPE_BITS=sizeof(SIZE_TYPE)*8;
constexpr SIZE_TYPE SIZE_80=(1ull<<(SIZE_TYPE_BITS-1));
constexpr SIZE_TYPE LEN_MAX=SIZE_80-1;
new_size=std::min<SIZE_TYPE>(new_size,LEN_MAX);
if(new_size<=2)
{
return 2;
}
else if(new_size<=4)
{
return 4;
}
SIZE_TYPE size1=min_2pow(new_size);
SIZE_TYPE size2=size1/2;
size2=size2+size2/2;
if(new_size<=size2)
{
return size2;
}
else
{
return size1;
}
}
SIZE_TYPE length()const
{
constexpr SIZE_TYPE SIZE_TYPE_BITS=sizeof(SIZE_TYPE)*8;
constexpr SIZE_TYPE SIZE_80=(1ull<<(SIZE_TYPE_BITS-1));
constexpr SIZE_TYPE LEN_MAX=SIZE_80-1;
return sign_n_len&LEN_MAX;
}
bool sign()const
{
constexpr SIZE_TYPE SIZE_TYPE_BITS=sizeof(SIZE_TYPE)*8;
constexpr SIZE_TYPE SIZE_80=(1ull<<(SIZE_TYPE_BITS-1));
return(SIZE_80&sign_n_len)!=0;
}
constexpr void resize(SIZE_TYPE new_size,SIZE_TYPE(size_func)(SIZE_TYPE)=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(SIZE_TYPE new_length)
{
constexpr SIZE_TYPE SIZE_TYPE_BITS=sizeof(SIZE_TYPE)*8;
constexpr SIZE_TYPE SIZE_80=(1ull<<(SIZE_TYPE_BITS-1));
constexpr SIZE_TYPE 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)
{
constexpr SIZE_TYPE SIZE_TYPE_BITS=sizeof(SIZE_TYPE)*8;
constexpr SIZE_TYPE SIZE_80=(1ull<<(SIZE_TYPE_BITS-1));
constexpr SIZE_TYPE 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;
}
}
SIZE_TYPE set_true_len()
{
if(ary_ptr==nullptr)
{
return 0;
}
SIZE_TYPE t_len=length();
while(t_len>0&&ary_ptr[t_len-1]==0)
{
t_len--;
}
change_length(t_len);
return length();
}
void fill_element(T ele,SIZE_TYPE count,SIZE_TYPE begin=0)
{
if(begin>=size||ary_ptr==nullptr)
{
return;
}
if(begin+count>=size)
{
count=size-begin;
}
std::fill(ary_ptr+begin,ary_ptr+begin+count,ele);
}
};
}
namespace hint_arithm
{
using namespace hint;
using SIZE_TYPE=UINT_32;
template<typename T>
using hintvector=HintVector<T,SIZE_TYPE>;
template<typename T>
constexpr size_t ary_true_len(const T&ary,size_t len)
{
while(len>0&&ary[len-1]==0)
{
len--;
}
return len;
}
template<typename T>
constexpr INT_32 abs_compare(const T ary1[],const T ary2[],size_t len1,size_t len2)
{
len1=ary_true_len(ary1,len1);
len2=ary_true_len(ary2,len2);
if(len1!=len2)
{
return len1>len2?1: -1;
}
if(ary1==ary2)
{
return 0;
}
while(len1>0)
{
len1--;
T num1=ary1[len1],num2=ary2[len1];
if(num1!=num2)
{
return num1>num2?1: -1;
}
}
return 0;
}
template<UINT_64 BASE,bool is_carry=true,typename T>
constexpr void abs_mul_num(const T in[],T num,T out[],size_t len)
{
len=ary_true_len(in,len);
num%=BASE;
UINT_64 prod=0;
if(num==1)
{
ary_copy(out,in,len);
}
else
{
for(size_t 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;
}
}
template<UINT_64 BASE,typename T>
constexpr INT_64 abs_div_num(const T in[],T num,T out[],size_t len)
{
size_t pos=ary_true_len(in,len);
num%=BASE;
if(num==1)
{
ary_copy(out,in,len);
return 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);
}
return last_rem;
}
template<INT_64 BASE,bool is_carry=true,typename T>
constexpr void abs_add(const T in1[],const T in2[],T out[],
size_t len1,size_t len2)
{
if(len1<len2)
{
std::swap(in1,in2);
std::swap(len1,len2);
}
size_t 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;
}
}
template<INT_64 BASE,typename T>
constexpr void abs_sub(const T in1[],const T in2[],T out[],
size_t len1,size_t len2)
{
if(len1<len2)
{
return;
}
size_t 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);
}
template<UINT_64 BASE,typename T>
void fft_mul_old(const T in1[],const T in2[],T out[],
size_t len1,size_t len2)
{
using namespace hint_transform;
if(len1==0||len2==0||in1==nullptr||in2==nullptr)
{
return;
}
const size_t conv_res_len=len1+len2-1;
const size_t fft_len=min_2pow(conv_res_len);
static Complex*fft_buf=nullptr;static size_t fft_cap=0;
if(fft_cap<fft_len){free(fft_buf);fft_buf=(Complex*)malloc(fft_len*sizeof(Complex));fft_cap=fft_len;}
Complex*fft_ary=fft_buf;
{size_t mnz=len1<len2?len1:len2;
memset((char*)(fft_ary+mnz),0,(fft_len-mnz)*sizeof(Complex));}
com_ary_combine_copy(fft_ary,in1,len1,in2,len2);
fft_dif(fft_ary,fft_len,false);
double inv= -1/(2.0*fft_len);
for(size_t i=0;i<fft_len;i++)
{
Complex tmp=fft_ary[i];
fft_ary[i]=std::conj(tmp*tmp*inv);
}
fft_dit(fft_ary,fft_len,false);
hint::UINT_64 carry=0;
for(size_t 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;
}
template<typename T>
static inline void limbs_to_double(double*dst,const T*src,size_t n)
{
size_t i=0;
if constexpr(sizeof(T)==4)
{
for(;i+8<=n;i+=8)
{
__m256i v=_mm256_loadu_si256((const __m256i*)(const 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]=(double)src[i];
}
// Independent radix10000 coefficient folding and eight-lane carry lookahead.
static inline __m128i carry550fold(__m256i raw,__m128i&p1,__m128i&p2,__m128i&p3){
const __m256d x=_mm256_sub_pd(_mm256_castsi256_pd(_mm256_or_si256(raw,_mm256_castpd_si256(_mm256_set1_pd(4503599627370496.0)))),_mm256_set1_pd(4503599627370496.0)),q1=_mm256_floor_pd(_mm256_mul_pd(x,_mm256_set1_pd(1e-4)));
const __m128i q2=_mm256_cvttpd_epi32(_mm256_mul_pd(x,_mm256_set1_pd(1e-8))),q3=_mm256_cvttpd_epi32(_mm256_mul_pd(x,_mm256_set1_pd(1e-12)));
const __m128i r0=_mm256_cvttpd_epi32(_mm256_sub_pd(x,_mm256_mul_pd(q1,_mm256_set1_pd(10000.0)))),r1=_mm256_cvttpd_epi32(_mm256_sub_pd(q1,_mm256_mul_pd(_mm256_cvtepi32_pd(q2),_mm256_set1_pd(10000.0)))),r2=_mm_sub_epi32(q2,_mm_mullo_epi32(q3,_mm_set1_epi32(10000))),r3=q3;
__m128i s=_mm_add_epi32(_mm_add_epi32(r0,_mm_alignr_epi8(r1,p1,12)),_mm_add_epi32(_mm_alignr_epi8(r2,p2,8),_mm_alignr_epi8(r3,p3,4)));
p1=r1;p2=r2;p3=r3;return s;
}
static void carry550(const unsigned long long*c,unsigned*out,size_t count){
__m128i p1=_mm_setzero_si128(),p2=p1,p3=p1;
const __m256i 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);
unsigned carry=0;size_t i=0;
for(;i+8<=count;i+=8){
__m128i low=carry550fold(_mm256_loadu_si256((const __m256i*)(c+i)),p1,p2,p3);
__m128i high=carry550fold(_mm256_loadu_si256((const __m256i*)(c+i+4)),p1,p2,p3);
__m256i s=_mm256_inserti128_si256(_mm256_castsi128_si256(low),high,1);
__m256i 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))));
__m256i prior=_mm256_blend_epi32(_mm256_permutevar8x32_epi32(q,indices),_mm256_set1_epi32(carry),1);
__m256i y=_mm256_add_epi32(_mm256_sub_epi32(s,_mm256_mullo_epi32(q,base)),prior);
unsigned e=(unsigned)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(y,_mm256_set1_epi32(9999))));
unsigned p=(unsigned)_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;
__m256i bits=_mm256_and_si256(_mm256_srlv_epi32(_mm256_set1_epi32(e),shifts),one);
__m256i 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((__m256i*)(out+i),y);carry=(unsigned)_mm256_extract_epi32(q,7)+(e>>7);
}
for(;i<=count;i+=4){
__m256i mask=_mm256_set_epi64x(i+3<count?-1LL:0,i+2<count?-1LL:0,i+1<count?-1LL:0,i<count?-1LL:0);
__m128i folded=carry550fold(_mm256_maskload_epi64((const long long*)(c+i),mask),p1,p2,p3);
unsigned tail[4];_mm_storeu_si128((__m128i*)tail,folded);
for(unsigned j=0;j<4&&i+j<=count;j++){unsigned v=tail[j]+carry;out[i+j]=v%10000;carry=v/10000;}
}
}
template<UINT_64 BASE,typename T>
void fft_mul(const T in1[],const T in2[],T out[],size_t len1,size_t len2){
if(!len1||!len2||!in1||!in2)return;
const size_t conv=len1+len2-1;
if constexpr(BASE==10000&&sizeof(T)==4){if(len1*len2<=131072){
const T*aa=in1,*bb=in2;size_t na=len1,nb=len2;if(na>nb){std::swap(aa,bb);std::swap(na,nb);}
static uint32_t*bp=nullptr,*ap=nullptr,*tmp=nullptr;static size_t bc=0,ac=0,tc=0;
const size_t need=nb+34,an=(na+1)/2;if(bc<need){free(bp);bp=(uint32_t*)malloc(need*4);bc=need;}if(ac<an){free(ap);ap=(uint32_t*)malloc(an*4);ac=an;}
memset(bp,0,16*4);uint32_t*packed=bp+16;for(size_t 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(size_t 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);
const bool overlap=(ob<ae&&oe>ab)||(ob<be&&oe>bbeg);T*o=out;if(overlap){if(tc<conv+1){free(tmp);tmp=(uint32_t*)malloc((conv+1)*4);tc=conv+1;}o=(T*)tmp;}
uint64_t carry=0;size_t m=0;
for(;m+16<=conv;m+=16){
uint64_t sums[16]={};const size_t lo=m>=nb-1?m-(nb-1):0,hi=std::min(na-1,m+15);
for(size_t i0=lo&~size_t(1);i0<=hi;i0+=40){
const size_t end=std::min(hi+1,i0+40);__m256i s0=_mm256_setzero_si256(),s1=s0;
for(size_t i=i0;i<end;i+=2){__m256i av=_mm256_set1_epi32(ap[i/2]);const uint32_t*p=packed+ptrdiff_t(m)-ptrdiff_t(i);
s0=_mm256_add_epi32(s0,_mm256_madd_epi16(av,_mm256_loadu_si256((const __m256i*)p)));
s1=_mm256_add_epi32(s1,_mm256_madd_epi16(av,_mm256_loadu_si256((const __m256i*)(p+8))));}
_mm256_storeu_si256((__m256i*)sums,_mm256_add_epi64(_mm256_loadu_si256((const __m256i*)sums),_mm256_cvtepu32_epi64(_mm256_castsi256_si128(s0))));
_mm256_storeu_si256((__m256i*)(sums+4),_mm256_add_epi64(_mm256_loadu_si256((const __m256i*)(sums+4)),_mm256_cvtepu32_epi64(_mm256_extracti128_si256(s0,1))));
_mm256_storeu_si256((__m256i*)(sums+8),_mm256_add_epi64(_mm256_loadu_si256((const __m256i*)(sums+8)),_mm256_cvtepu32_epi64(_mm256_castsi256_si128(s1))));
_mm256_storeu_si256((__m256i*)(sums+12),_mm256_add_epi64(_mm256_loadu_si256((const __m256i*)(sums+12)),_mm256_cvtepu32_epi64(_mm256_extracti128_si256(s1,1))));
}
for(unsigned j=0;j<16;j++){uint64_t v=sums[j]+carry;o[m+j]=v%10000;carry=v/10000;}
}
for(;m<conv;m++){uint64_t sum=0;const size_t lo=m>=nb-1?m-(nb-1):0,hi=std::min(na-1,m);for(size_t i=lo;i<=hi;i++)sum+=(uint64_t)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);return;
}}
if(conv<512){fft_mul_old<BASE>(in1,in2,out,len1,len2);return;}
size_t n=hintpowfft::int_ceil2(conv);
static double*g_abuf=nullptr,*g_bbuf=nullptr,*ar_ab=nullptr,*ar_bb=nullptr;static size_t g_acap=0,g_bcap=0;
if(g_acap<n){_mm_free(ar_ab);ar_ab=(double*)_mm_malloc((n+384)*sizeof(double),64);g_abuf=ar_ab;g_acap=n;}
double*a=g_abuf;
memset(a+len1,0,(n-len1)*sizeof(double));
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(ar_bb);ar_bb=(double*)_mm_malloc((n+384)*sizeof(double),64);g_bbuf=ar_bb+32;g_bcap=n;}
double*b=g_bbuf;memset(b+len2,0,(n-len2)*sizeof(double));
limbs_to_double(b,in2,len2);
hintpowfft::transform::fft::real_conv_avx<true>(a,b,n);
}
const uint64_t*coeff=(const uint64_t*)a;if constexpr(BASE==10000){if(std::min(len1,len2)<=40000000){carry550((const unsigned long long*)coeff,(unsigned*)out,conv);return;}}UINT_64 carry=0;
for(size_t i=0;i<conv;++i){carry+=coeff[i];out[i]=carry%BASE;carry/=BASE;}
out[conv]=carry%BASE;
}
template<UINT_64 BASE,typename T>
constexpr T divisor_normalize(const T in[],T out[],size_t 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);
}
}
return multiplier;
}
template<UINT_64 BASE,typename T>
void abs_long_div(T dividend[],const T divisor[],T quot[],
size_t len1,size_t 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)
{
return;
}
if(abs_compare(dividend,divisor,len1,len2)<0)
{
return;
}
if(len2==1)
{
T rem=abs_div_num<BASE>(dividend,divisor[0],quot,len1);
dividend[0]=rem;
return;
}
if(divisor[len2-1]<(BASE/2))
{
throw("Can't call this proc before normalize the divisor\n");
}
quot[len1-len2]=0;
const 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;
size_t 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();
size_t 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();
size_t 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;
}
}
template<UINT_64 BASE,typename T>
void abs_rec_div(T dividend[],T divisor[],hintvector<T> ",
size_t len1,size_t 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)
{
return;
}
if(abs_compare(dividend,divisor,len1,len2)<0)
{
return;
}
if(divisor[len2-1]<(BASE/2))
{
throw("Can't call this proc before normalize the divisor\n");
}
size_t quot_len=len1-len2+1;
quot.change_length(quot_len);
constexpr size_t 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)
{
size_t base_len=(len1+3)/4;
size_t 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();
size_t 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
{
size_t base_len=len2/2;
abs_rec_div<BASE>(dividend+base_len,divisor+base_len,quot,len1-base_len,len2-base_len);
constexpr 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);
size_t 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);
}
}
template<UINT_64 BASE,typename T>
hintvector<T>abs_div(const T dividend[],T divisor[],hintvector<T> ",
size_t len1,size_t 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))
{
size_t shift=len2*2-len1-2;
abs_rec_div<BASE>(dividend_ptr+shift,divisor_ptr+shift,quot,len1-shift,len2-shift);
quot.set_true_len();
return 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();
}
return 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{inline static void*h[24]={};static void*get(std::size_t b){std::size_t w=(b+15)/16;if(!w)w=1;int c=w<=1?0:64-__builtin_clzll(w-1);if(c>23)return::operator new(w*16);void*p=h[c];if(p)h[c]=*(void**)p;else p=::operator new(((std::size_t)1<<c)*16);return p;}static void put(void*p,std::size_t b){std::size_t w=(b+15)/16;if(!w)w=1;int c=w<=1?0:64-__builtin_clzll(w-1);if(c>23){::operator delete(p);return;}*(void**)p=h[c];h[c]=p;}};
template<class T>struct NoInitAlloc{
using value_type=T;
NoInitAlloc()noexcept=default;
template<class U>NoInitAlloc(const NoInitAlloc<U>&)noexcept{}
T*allocate(std::size_t n){return static_cast<T*>(LP648::get(n*sizeof(T)));}
void deallocate(T*p,std::size_t n)noexcept{LP648::put(p,n*sizeof(T));}
template<class U>void construct(U*p){::new(static_cast<void*>(p))U;}
template<class U,class...A>void construct(U*p,A&&...a){::new(static_cast<void*>(p))U(std::forward<A>(a)...);}
template<class U>void destroy(U*p){p->~U();}
bool operator==(const NoInitAlloc&)const noexcept{return true;}
bool operator!=(const NoInitAlloc&)const noexcept{return false;}
};
namespace e_compute{
#include <cstdint>
__attribute__((always_inline))static inline __uint128_t iv603dm(__uint128_t x,uint64_t&remainder){
constexpr uint64_t D=10000000000000000ULL;
constexpr __uint128_t M=(~(__uint128_t)0)/D;
const uint64_t al=(uint64_t)x,ah=(uint64_t)(x>>64),bl=(uint64_t)M,bh=(uint64_t)(M>>64);
const __uint128_t p00=(__uint128_t)al*bl,p01=(__uint128_t)al*bh,p10=(__uint128_t)ah*bl,p11=(__uint128_t)ah*bh;
const __uint128_t mid=(p00>>64)+(uint64_t)p01+(uint64_t)p10;
__uint128_t q=p11+(p01>>64)+(p10>>64)+(mid>>64);
uint64_t r=(uint64_t)(x-q*D);
if(r>=D){r-=D;++q;}remainder=r;return 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<uint32_t,NoInitAlloc<uint32_t>>v;bool neg=false;
Big()=default;
Big(uint64_t a){uint32_t d[5];unsigned n=0;while(a){d[n++]=a%10000;a/=10000;}v.assign(d,d+n);}
static Big wide(__uint128_t a){
if(!(a>>64))return Big((uint64_t)a);
uint32_t d[10];unsigned n=0;
while(a>UINT64_MAX){uint64_t part;a=iv608dm(a,part);
uint64_t up=part/100000000ULL,low=part-up*100000000ULL;
d[n++]=low%10000;d[n++]=low/10000;d[n++]=up%10000;d[n++]=up/10000;}
uint64_t tail=(uint64_t)a;while(tail){d[n++]=tail%10000;tail/=10000;}
Big x;x.v.assign(d,d+n);return x;
}
bool zero()const{return v.empty();}
void trim(){while(!v.empty()&&!v.back())v.pop_back();if(v.empty())neg=false;}
int cmpabs(const Big&b)const{if(v.size()!=b.v.size())return v.size()<b.v.size()?-1:1;for(size_t i=v.size();i--;)if(v[i]!=b.v[i])return v[i]<b.v[i]?-1:1;return 0;}
Big operator-()const{Big r=*this;if(!zero())r.neg=!neg;return r;}
Big operator+(const Big&b)const&{
if(zero())return b;if(b.zero())return*this;
if(neg!=b.neg){int c=cmpabs(b);if(!c)return Big();const Big&a=c>0?*this:b;const Big&bb=c>0?b:*this;Big r;r.neg=a.neg;r.v.resize(a.v.size());int borrow=0;size_t 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();return r;}
Big r;r.neg=neg;r.v.resize(std::max(v.size(),b.v.size())+1);unsigned carry=0;for(size_t i=0;i+1<r.v.size();++i){unsigned 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();return r;
}
Big operator+(const Big&b)&&{
if(neg!=b.neg)return static_cast<const Big&>(*this)+b;
if(b.zero())return std::move(*this);
if(zero())return b;
size_t n=std::max(v.size(),b.v.size());v.resize(n,0);
unsigned carry=0;size_t i=0;
for(;i<b.v.size();++i){unsigned q=v[i]+b.v[i]+carry;carry=q>=10000;v[i]=q-(carry?10000:0);}
while(carry&&i<n){unsigned q=v[i]+carry;carry=q>=10000;v[i]=q-(carry?10000:0);++i;}
if(carry)v.push_back(carry);
return std::move(*this);
}
Big operator-(const Big&b)const{return*this+(-b);}
Big mulnum(uint64_t m)const{if(zero()||!m)return Big();if(m<=UINT64_MAX/10000){Big r;r.neg=neg;r.v.resize(v.size());uint64_t carry=0;for(size_t i=0;i<v.size();++i){carry+=(uint64_t)v[i]*m;r.v[i]=carry%10000;carry/=10000;}while(carry){r.v.push_back(carry%10000);carry/=10000;}return r;}Big r;r.neg=neg;r.v.resize(v.size());__uint128_t carry=0;for(size_t i=0;i<v.size();++i){carry+=(__uint128_t)v[i]*m;r.v[i]=(uint32_t)(carry%10000);carry/=10000;}while(carry){r.v.push_back(carry%10000);carry/=10000;}return r;}
Big divnum(uint32_t d)const{Big r;r.neg=neg;r.v.resize(v.size());uint64_t rem=0;for(size_t i=v.size();i--;){rem=rem*10000+v[i];r.v[i]=rem/d;rem%=d;}r.trim();return r;}
Big operator*(const Big&b)const{
if(zero()||b.zero())return Big();if(v.size()==1){Big r=b.mulnum(v[0]);r.neg=neg!=b.neg;return r;}if(b.v.size()==1){Big r=mulnum(b.v[0]);r.neg=neg!=b.neg;return r;}
Big r;r.neg=neg!=b.neg;r.v.resize(v.size()+b.v.size());
if(v.size()*b.v.size()<=256){std::memset(r.v.data(),0,r.v.size()*sizeof(uint32_t));
const uint32_t*aa=v.data(),*bb=b.v.data();uint32_t*cc=r.v.data();
for(size_t i=0;i<v.size();++i)for(size_t j=0;j<b.v.size();++j)cc[i+j]+=aa[i]*bb[j];
uint32_t carry=0;for(size_t i=0;i<r.v.size();++i){uint32_t 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();return r;
}
static Big negative_one(){Big x(1);x.neg=true;return x;}
Big operator/(const Big&b)const{
assert(!b.zero());if(cmpabs(b)<0)return Big();if(b.v.size()==1){Big r=divnum(b.v[0]);r.neg=neg!=b.neg;return r;}
hint::HintVector<uint32_t>q;hint_arithm::abs_div<10000>(v.data(),const_cast<uint32_t*>(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();return r;
}
Big shift(size_t limbs)const{if(zero())return Big();Big r;r.neg=neg;r.v.resize(limbs+v.size(),0);std::copy(v.begin(),v.end(),r.v.begin()+limbs);return r;}
Big high(size_t cut)const{if(cut>=v.size())return Big();Big r;r.neg=neg;r.v.assign(v.begin()+cut,v.end());return r;}
};
static bool MP(const Big&A,const Big&B,const Big&C,Big&o1,Big&o2);
struct QT{Big q,t;};
struct iv586w{uint64_t x[4];};
static void iv586step(iv586w&w,uint64_t k,uint64_t carry){for(unsigned j=0;j<4;j++){__uint128_t q=(__uint128_t)w.x[j]*k+carry;w.x[j]=q;carry=q>>64;}}
static Big iv586big(iv586w w){uint32_t d[20];unsigned used=0;int top=3;const uint64_t D=10000000000000000ULL;while(top>=0){while(top>=0&&!w.x[top])--top;if(top<0)break;uint64_t rem=w.x[top]%D;w.x[top]/=D;for(int i=top-1;i>=0;i--)w.x[i]=(uint64_t)iv608dm(((__uint128_t)rem<<64)|w.x[i],rem);uint64_t hi=rem/100000000ULL,lo=rem-hi*100000000ULL;d[used++]=lo%10000;d[used++]=lo/10000;d[used++]=hi%10000;d[used++]=hi/10000;}while(used&&!d[used-1])--used;Big r;r.v.assign(d,d+used);return r;}
static QT arithmetic_pair_big(iv586w q,iv586w t){uint32_t qd[20],td[20];unsigned qn=0,tn=0;int qt=3,tt=3;constexpr uint64_t D=10000000000000000ull;
while(true){while(qt>=0&&!q.x[qt])--qt;while(tt>=0&&!t.x[tt])--tt;if(qt<0&&tt<0)break;uint64_t qr=0,tr=0;
#pragma GCC unroll 4
for(int i=3;i>=0;--i){if(i==qt){qr=q.x[i]%D;q.x[i]/=D;}else if(i<qt)q.x[i]=(uint64_t)iv608dm(((__uint128_t)qr<<64)|q.x[i],qr);
if(i==tt){tr=t.x[i]%D;t.x[i]/=D;}else if(i<tt)t.x[i]=(uint64_t)iv608dm(((__uint128_t)tr<<64)|t.x[i],tr);}
if(qt>=0){uint64_t hi=qr/100000000ull,lo=qr-hi*100000000ull;qd[qn++]=lo%10000;qd[qn++]=lo/10000;qd[qn++]=hi%10000;qd[qn++]=hi/10000;}
if(tt>=0){uint64_t hi=tr/100000000ull,lo=tr-hi*100000000ull;td[tn++]=lo%10000;td[tn++]=lo/10000;td[tn++]=hi%10000;td[tn++]=hi/10000;}}
while(qn&&!qd[qn-1])--qn;while(tn&&!td[tn-1])--tn;Big qb,tb;qb.v.assign(qd,qd+qn);tb.v.assign(td,td+tn);return{std::move(qb),std::move(tb)};}
struct iv827w{uint64_t x[12];};
static inline void ar_pair_step(iv827w&q,iv827w&t,uint64_t k,uint64_t carryt,unsigned&used){uint64_t carryq=0;for(unsigned j=0;j<used;++j){__uint128_t x=(__uint128_t)q.x[j]*k+carryq,y=(__uint128_t)t.x[j]*k+carryt;q.x[j]=x;t.x[j]=y;carryq=x>>64;carryt=y>>64;}if(used<12){q.x[used]=carryq;t.x[used]=carryt;used+=(carryq|carryt)!=0;}}
static QT ar_pair_big(iv827w&q,iv827w&t,unsigned active){Big Q,T;Q.v.resize(60);T.v.resize(60);unsigned used=0;int top=int(active)-1;constexpr uint64_t D=10000000000000000ULL;while(top>=0){while(top>=0&&!(q.x[top]|t.x[top]))--top;if(top<0)break;uint64_t rq,rt,qh=q.x[top],th=t.x[top];if(qh<D){q.x[top]=0;rq=qh;}else{q.x[top]=qh/D;rq=qh%D;}if(th<D){t.x[top]=0;rt=th;}else{t.x[top]=th/D;rt=th%D;}for(int i=top-1;i>=0;--i){__uint128_t x=((__uint128_t)rq<<64)|q.x[i],y=((__uint128_t)rt<<64)|t.x[i];q.x[i]=(uint64_t)iv603dm(x,rq);t.x[i]=(uint64_t)iv603dm(y,rt);}for(unsigned j=0;j<4;j++){Q.v[used]=rq%10000;T.v[used]=rt%10000;rq/=10000;rt/=10000;++used;}}Q.v.resize(used);T.v.resize(used);Q.trim();T.trim();return{std::move(Q),std::move(T)};}
static QT iv827leaf(unsigned a,unsigned b){uint64_t f0=uint64_t(a)*(a+1)*(a+2),v0=uint64_t(a+1)*(a+2)+a+3,f1=uint64_t(a+3)*(a+4)*(a+5),v1=uint64_t(a+4)*(a+5)+a+6;__uint128_t q0=(__uint128_t)f0*f1,t0=(__uint128_t)v0*f1+v1;iv827w q{{(uint64_t)q0,(uint64_t)(q0>>64),0,0,0,0,0,0}},t{{(uint64_t)t0,(uint64_t)(t0>>64),0,0,0,0,0,0}};unsigned used=2,k=a+6;for(;b-k>=3;k+=3){uint64_t last=k+2,triple=uint64_t(k)*(k+1)*last;ar_pair_step(q,t,triple,uint64_t(k+1)*last+last+1,used);}for(;b-k>=2;k+=2){uint64_t pair=uint64_t(k)*(k+1);ar_pair_step(q,t,pair,k+2,used);}if(k<b){ar_pair_step(q,t,k,1,used);}return ar_pair_big(q,t,used);}
static constexpr double ar_log_radix=0.10857362047581295691278222972915127;
static inline double ar_mass(double x){if(x<=1.0)return 0.0;if(x<8.0)return lgamma(x)*ar_log_radix;double z=1.0/x,z2=z*z;return ((x-.5)*log(x)-x+0.91893853320467274178032973640561764+z*(1.0/12.0+z2*(-1.0/360.0+z2/1260.0)))*ar_log_radix;}
static unsigned ar_mass_split(unsigned a,unsigned b){unsigned bal=a+(b-a)/2;if(b<=2097152u&&b-a<=1024u)return bal;
double pa=ar_mass(a),ms=ar_mass(b)-pa;if(ms<2048.0)return bal;
int ex;frexp((.75*ms)/.96,&ex);double chunk=ldexp(.96,ex-1),target=pa+chunk,c=a+(b-a)*chunk/ms;
for(unsigned j=0;j<4;j++){double z=1/c,z2=z*z,der=(log(c)-.5*z-z2*(1.0/12.0-z2/120.0))*ar_log_radix;c-=(ar_mass(c)-target)/der;c=std::max(double(a)+1.0,std::min(double(b)-1.0,c));}
unsigned m=unsigned(c)&~7u;if(m<=a+7||m+7>=b)m=bal;return m;}
static QT binary_split(unsigned a,unsigned b){unsigned iv827n=b-a;if(iv827n>9&&((iv827n<=54&&b<=16384u)||(iv827n<=48&&b<=65536u)||(iv827n<=45&&b<=131072u)||(iv827n<=42&&b<=262144u)||(iv827n<=40&&b<=524288u)||(iv827n<=36&&b<=2097152u)))return iv827leaf(a,b);
const unsigned size=b-a;if((size<=9&&b<=16384u)||(size<=8&&b<=65536u)||(size<=7&&b<=262144u)){__uint128_t q=1,t=0;unsigned k=a;for(;b-k>=3;k+=3){uint64_t last=k+2,triple=uint64_t(k)*(k+1)*last;q*=triple;t=t*triple+uint64_t(k+1)*last+last+1;}for(;b-k>=2;k+=2){uint64_t pair=uint64_t(k)*(k+1);q*=pair;t=t*pair+k+2;}if(k<b){q*=k;t=t*k+1;}return{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))){uint64_t f0=uint64_t(a)*(a+1)*(a+2),v0=uint64_t(a+1)*(a+2)+a+3,f1=uint64_t(a+3)*(a+4)*(a+5),v1=uint64_t(a+4)*(a+5)+a+6;__uint128_t q0=(__uint128_t)f0*f1,t0=(__uint128_t)v0*f1+v1;unsigned k=a+6,take=std::min(3u,b-k);uint64_t ff=1,vv=0;if(take==3){ff=uint64_t(k)*(k+1)*(k+2);vv=uint64_t(k+1)*(k+2)+k+3;}else if(take==2){ff=uint64_t(k)*(k+1);vv=k+2;}else if(take==1){ff=k;vv=1;}__uint128_t ql=(__uint128_t)(uint64_t)q0*ff,qh=(__uint128_t)(uint64_t)(q0>>64)*ff+(ql>>64),tl=(__uint128_t)(uint64_t)t0*ff+vv,th=(__uint128_t)(uint64_t)(t0>>64)*ff+(tl>>64);iv586w q={{(uint64_t)ql,(uint64_t)qh,(uint64_t)(qh>>64),0}},t={{(uint64_t)tl,(uint64_t)th,(uint64_t)(th>>64),0}};k+=take;for(;b-k>=3;k+=3){uint64_t last=k+2,triple=uint64_t(k)*(k+1)*last;iv586step(q,triple,0);iv586step(t,triple,uint64_t(k+1)*last+last+1);}for(;b-k>=2;k+=2){uint64_t pair=uint64_t(k)*(k+1);iv586step(q,pair,0);iv586step(t,pair,k+2);}if(k<b){iv586step(q,k,0);iv586step(t,k,1);}return arithmetic_pair_big(q,t);}
if(size<=4||(size<=6&&b<=2097152u)){
__uint128_t q=1,t=0;unsigned k=a;for(;b-k>=3;k+=3){uint64_t last=k+2,triple=uint64_t(k)*(k+1)*last;q*=triple;t=t*triple+uint64_t(k+1)*last+last+1;}for(;b-k>=2;k+=2){uint64_t pair=uint64_t(k)*(k+1);q*=pair;t=t*pair+k+2;}if(k<b){q*=k;t=t*k+1;}
return{Big::wide(q),Big::wide(t)};
}
unsigned m=ar_mass_split(a,b);if(m<=a||m>=b)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;return{std::move(q),std::move(t)};
}
static unsigned choose_terms(unsigned dec){
const long double need=(long double)dec+30;
const long double invln10=1.0L/logl(10.0L);
auto lower=[&](unsigned m){return((long double)m*logl((long double)m)-m+1)*invln10;};
unsigned lo=1,hi=2;while(lower(hi)<need){if(hi>2000000000u)abort();hi*=2;}
while(lo+1<hi){const unsigned m=lo+(hi-lo)/2;if(lower(m)>=need)hi=m;else lo=m;}
return hi;
}
static bool stable_prefix(const std::string&s,unsigned digits){
if(s.size()<=digits)return false;
bool lo=true,hi=true;
for(size_t i=digits;i+1<s.size();++i){lo&=s[i]=='0';hi&=s[i]=='9';}
return!(lo&&s.back()<'2')&&!(hi&&s.back()>='8');
}
static inline __m256i iv796encode(__m256i q){
q=_mm256_permutevar8x32_epi32(q,_mm256_setr_epi32(7,6,5,4,3,2,1,0));
__m256i h=_mm256_srli_epi32(_mm256_mulhi_epu16(q,_mm256_set1_epi32(5243)),3),r=_mm256_sub_epi16(q,_mm256_mullo_epi16(h,_mm256_set1_epi32(100)));
__m256i p=_mm256_or_si256(h,_mm256_slli_epi32(r,16)),t=_mm256_mulhi_epu16(p,_mm256_set1_epi16(6554)),u=_mm256_sub_epi16(p,_mm256_mullo_epi16(t,_mm256_set1_epi16(10)));
return _mm256_add_epi8(_mm256_or_si256(t,_mm256_slli_epi16(u,8)),_mm256_set1_epi8('0'));
}
static void iv486write(const std::vector<unsigned>&x,unsigned digits,char*out){
unsigned written=0;out[1]='.';auto emit=[&](char c){if(written<digits){out[written?written+1:0]=c;++written;}};
unsigned 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);
std::size_t i=x.size()-1;
for(;i>=8&&digits-written>=32;i-=8,written+=32){__m256i raw=_mm256_loadu_si256((const __m256i*)(x.data()+i-8)),text=iv796encode(raw);asm volatile("vmovdqu %1,%0":"=m"(*(__m256i_u*)(out+written+1)):"x"(text));}
while(i&&written<digits){q=x[--i];unsigned left=digits-written;emit('0'+q/1000);if(left>=2)emit('0'+q/100%10);if(left>=3)emit('0'+q/10%10);if(left>=4)emit('0'+q%10);}
}
static uint32_t*g_vbuf=nullptr;static size_t g_vcap=0;
static uint32_t*vmul(const uint32_t*a,size_t la,const uint32_t*b,size_t lb,size_t&outlen){
const size_t need=la+lb+1;
if(g_vcap<need){free(g_vbuf);g_vbuf=(uint32_t*)malloc(need*sizeof(uint32_t));if(!g_vbuf)abort();g_vcap=need;}
outlen=need;
if(!la||!lb){memset(g_vbuf,0,need*sizeof(uint32_t));return g_vbuf;}
hint_arithm::fft_mul<10000>(a,b,g_vbuf,la,lb);
g_vbuf[la+lb]=0;
return g_vbuf;
}
static void vtrim(std::vector<uint32_t>&v){size_t n=v.size();while(n>1&&v[n-1]==0)--n;v.resize(n);}
static double*ar_nr[2]={nullptr,nullptr},*ar_nrb[2]={nullptr,nullptr};static size_t ar_nr_cap=0;
static void ar_nr_prepare(const uint32_t*r,size_t lr,size_t n){
if(ar_nr_cap<n){for(unsigned j=0;j<2;j++){_mm_free(ar_nrb[j]);ar_nrb[j]=(double*)_mm_malloc((n+384)*8,64);ar_nr[j]=ar_nrb[j]+j*32;}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);
}
static uint32_t*ar_nr_product(const uint32_t*a,size_t la,size_t lr,size_t n,size_t&outlen){
outlen=la+lr+1;if(g_vcap<outlen){free(g_vbuf);g_vbuf=(uint32_t*)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);
const uint64_t*c=(const uint64_t*)ar_nr[1];uint64_t carry=0;size_t conv=la+lr-1;
for(size_t 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;return g_vbuf;
}
template<class VA,class VB>static std::vector<uint32_t>scaled_newton(const VA&Tv,
const VB&Qv,
size_t L){
const uint32_t*Q=Qv.data();const size_t nq=Qv.size();
const size_t M0=85;std::vector<uint32_t>R;{const unsigned tk=nq<88?(unsigned)nq:88u;Big dn;for(unsigned i=0;i<tk;++i)dn.v.push_back(Q[nq-tk+i]);unsigned carry=1;for(unsigned i=0;i<dn.v.size()&&carry;++i){unsigned t=dn.v[i]+carry;dn.v[i]=t%10000;carry=t/10000;}if(carry)dn.v.push_back(carry);Big nu;nu.v.assign(M0+tk+1,0);nu.v[M0+tk]=1;Big r0=nu/dn;R.assign(r0.v.begin(),r0.v.end());if(R.empty())R.push_back(1);}
std::vector<size_t>iv525plan;for(size_t z=L;z>M0;z=(z+1)/2)iv525plan.push_back(z);std::reverse(iv525plan.begin(),iv525plan.end());size_t iv525next=0;size_t M=M0;
for(int iter=0;iter<80;++iter){
const size_t quse=(nq<2*M)?nq:2*M;
const uint32_t*Dq=Q+(nq-quse);
const size_t lr=R.size();
const size_t ar_n=hintpowfft::int_ceil2(quse+lr-1);bool ar_keep=ar_n>=512;if(ar_keep)ar_nr_prepare(R.data(),lr,ar_n);
size_t plen;uint32_t*P=ar_keep?ar_nr_product(Dq,quse,lr,ar_n,plen):vmul(Dq,quse,R.data(),lr,plen);
const size_t fpow=M+quse;
// Exact error against a power of the radix: all low borrow digits are independent complements.
std::size_t ar_pn=plen;while(ar_pn&&!P[ar_pn-1])--ar_pn;
int neg=ar_pn>fpow;
std::vector<unsigned>F;
if(neg){F.assign(P,P+ar_pn);std::size_t ar_j=fpow;while(F[ar_j]==0){F[ar_j]=9999;++ar_j;}--F[ar_j];}
else{F.assign(fpow+1,0);std::size_t ar_j=0;while(ar_j<ar_pn&&!P[ar_j])++ar_j;
if(ar_j==ar_pn)F[fpow]=1;else{F[ar_j]=10000-P[ar_j];++ar_j;for(;ar_j<ar_pn;++ar_j)F[ar_j]=9999-P[ar_j];for(;ar_j<fpow;++ar_j)F[ar_j]=9999;}}
vtrim(F);
const size_t p=(fpow>F.size())?(fpow-F.size()):0;
if(M>=L&&p+6>=L)break;
size_t M2=iv525next<iv525plan.size()?iv525plan[iv525next++]:2*M;
if(M2<=M)M2=2*M;
bool fin=((2*p+6)>=L)&&(M2>=L);
const size_t sh=quse;
std::vector<uint32_t>Rn(std::max<std::size_t>(M+lr,lr+F.size()+1>sh?lr+F.size()+1-sh:0)+2,0);
for(size_t i=0;i<lr;++i)Rn[M+i]=R[i];
if(F.size()>1||F[0]){
size_t ar_drop=(sh+1>lr)?sh+1-lr:0;if(ar_drop>=F.size())ar_drop=0;const size_t ar_fs=F.size()-ar_drop,ar_shift=sh-ar_drop;
size_t glen;uint32_t*G=(ar_keep&&hintpowfft::int_ceil2(lr+ar_fs-1)>=512&&hintpowfft::int_ceil2(lr+ar_fs-1)<=ar_n)?ar_nr_product(F.data()+ar_drop,ar_fs,lr,hintpowfft::int_ceil2(lr+ar_fs-1),glen):vmul(R.data(),lr,F.data()+ar_drop,ar_fs,glen);
size_t i=0;
if(!neg){
unsigned carry=0;
for(;ar_shift+i<glen;++i){unsigned q=Rn[i]+G[ar_shift+i]+carry;carry=q>=10000;Rn[i]=q-(carry?10000:0);}
for(;carry&&i<Rn.size();++i){unsigned q=Rn[i]+carry;carry=q>=10000;Rn[i]=q-(carry?10000:0);}
}else{
int br=0;
for(;ar_shift+i<glen;++i){int q=int(Rn[i])-int(G[ar_shift+i])-br;br=q<0;Rn[i]=uint32_t(q+(br?10000:0));}
for(;br&&i<Rn.size();++i){int q=int(Rn[i])-br;br=q<0;Rn[i]=uint32_t(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(fin)break;
}
if(M>L){
size_t drop=M-L;
if(R.size()>drop)R.erase(R.begin(),R.begin()+drop);else{R.assign(1,0);}
vtrim(R);
}
size_t plen;uint32_t*P=vmul(Tv.data(),Tv.size(),R.data(),R.size(),plen);
size_t slen=plen>nq?plen-nq:0;
std::vector<uint32_t>S(L+3,0);
for(size_t i=0;i<slen&&i<L+3;++i)S[i]=P[nq+i];
S[L]+=1;
for(size_t 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();
return S;
}
struct Result{std::string digits;unsigned terms;uint64_t bs_ticks,divide_ticks,format_ticks;bool guard_stable;};
__attribute__((noinline,noclone))Result compute(unsigned digits,char*out){
if(!digits)return{"",0,0,0,0,true};
const unsigned limbs=(digits+50)/4,dec=limbs*4,terms=choose_terms(dec);
_mm_lfence();const uint64_t t0=__rdtsc();QT r=binary_split(1,terms+1);
if(r.q.v.size()<=size_t(limbs)+6)abort();
_mm_lfence();const uint64_t t1=__rdtsc();
auto scaled=scaled_newton(r.t.v,r.q.v,limbs);
_mm_lfence();const uint64_t t2=__rdtsc();
iv486write(scaled,digits,out);std::string s;bool ok=true;
_mm_lfence();const uint64_t t3=__rdtsc();
return{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.
static bool MP(const Big&A,const Big&B,const Big&C,Big&o1,Big&o2){
size_t oa=A.v.size(),ob=B.v.size(),oc=C.v.size();if(oa<2||ob<2||oc<2)return 0;
size_t za=0,zb=0,zc=0;while(A.v[za]==0)++za;while(B.v[zb]==0)++zb;while(C.v[zc]==0)++zc;
size_t la=oa-za,lb=ob-zb,lc=oc-zc;
if(la<2||lb<2||lc<2)return 0;
size_t c1=la+lc-1,c2=lb+lc-1;
if(c1<512||c2<512||la*lc<=16384||lb*lc<=16384)return 0;
size_t n=hintpowfft::int_ceil2(c1);if(hintpowfft::int_ceil2(c2)!=n)return 0;
static double*F3[3]={0,0,0},*ar_Fb[3]={0,0,0};static size_t cap=0;
if(cap<n){for(int i=0;i<3;i++){_mm_free(ar_Fb[i]);ar_Fb[i]=(double*)_mm_malloc((n+384)*8,64);F3[i]=ar_Fb[i]+i*32;}cap=n;}
double*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);
size_t 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);
uint32_t*p=o1.v.data()+s1,*q=o2.v.data()+s2;
uint64_t iv801a=0,iv801b=0;size_t iv801n=c1<c2?c1:c2,iv801i=0;for(;iv801i<iv801n;iv801i++){iv801a+=((const uint64_t*)a)[iv801i];iv801b+=((const uint64_t*)b)[iv801i];p[iv801i]=iv801a%10000;iv801a/=10000;q[iv801i]=iv801b%10000;iv801b/=10000;}for(;iv801i<c1;iv801i++){iv801a+=((const uint64_t*)a)[iv801i];p[iv801i]=iv801a%10000;iv801a/=10000;}p[c1]=iv801a%10000;for(iv801i=iv801n;iv801i<c2;iv801i++){iv801b+=((const uint64_t*)b)[iv801i];q[iv801i]=iv801b%10000;iv801b/=10000;}q[c2]=iv801b%10000;
o1.neg=o2.neg=0;o1.trim();o2.trim();return 1;
}
}
void calc_e(unsigned n,char*s){if(!n)return;if(n==1){s[0]='2';return;}e_compute::compute(n-1,s);}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 1.028 s | 421 MB + 988 KB | Accepted | Score: 100 | 显示更多 |