提交记录 171026


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_codex61s_agg5 convmultiplye8. 测测你的乘法卷积-1e8 Accepted 100 857.058 ms 390752 KB C++17 37.52 KB
提交时间 评测时间
2026-11-18 02:15:00 2026-11-18 02:15:08
/* References / 引用: saffah_codex_6a_agg3
 https://duck.ac/submission/170737: complete Accepted fused1/2/3/4/8/16
 unit pass, sorted generic parents, direct row-flag regions and SSE partners.
 Retain every inherited account, original URL, exact use and legal notice.
 Approach / 思路: Partition each generic vector pass by its saved child
 cursor boundaries. Before2i activates, run plain32-product groups; peel
 at most a few eight-product crossing windows with the original masks.
 With4i present, run complete2i-only groups before the4i boundary, peel
 its crossing windows, then execute unmasked2i+4i groups. Twofold-only
 rows use the analogous plain/masked/full schedule. Preserve every pair,
 scatter order, saved child cursor, deferred fringe and diagonal. All
 full helpers are explicitly inline; no generic closure calls are added.
 Experiment purpose:129 quadratic sizes and65537/99999/131073/full100M
 independent divisor-pair outputs, instrument every unmasked call against
 actual child-boundary invariants/input/64guards, then official measurement.
 */
/* References / 引用: saffah_codex_6a_agg3
 https://duck.ac/submission/170571: complete Accepted sorted parent-row
 list, monotone active prefix, fourfold SSE partner fusion/cursors/tails.
 saffah_v41f1017_agg4 https://duck.ac/submission/170554: row-invariant flag
 specialization idea, extended independently from twofold to fourfold rows.
 All inherited authors, exact URLs, used content and notices are retained.
 Own saffah_codex61s_agg5 https://duck.ac/submission/170650:
 previous generic-lambda row specialization, officially Accepted but slow.
 Approach / 思路: Emit the three specialized vector regions lexically in
 multiply itself so the owning function directly sees all row scalars,
 pointers and cursor variables, without a separate generic-lambda operator
 or its capture-object accesses. Each local child helper has literal bool
 flags and the original loop arithmetic. Additionally, Instantiate the entire32-wide/eight-wide vector phase
 for the three possible row-flag pairs: no child,2i only, or2i plus4i.
 Dispatch once per row and make both fusion flags compile-time constants
 inside each specialization. Preserve the original SSE partner products,
 masked crossing/steady-state arithmetic, scatter order, deferred cursor
 updates and every pair. Physical target block=49152.
 Experiment purpose:129 quadratic sizes and full10^8 independent divisor
 pairs with an explicit specialized-path hit/input/64guards, then official
 measurement; local speed never rejects the candidate.
 */
/* References / 引用: Each ID denotes https://duck.ac/submission/{ID}; verified official authors override historical misattributions.
saffah_cc_v41_agg1:100000.
saffah_codex61s_agg5:164808,164972,166022,166311,166337,166395,170141,170182.
saffah_codex_6a_agg3:165981,167080,167081,167082.
saffah_v41f1017_agg4:164782,164866,166996,167233,167897,170438.
170438: copied complete fourfold/odd-part-three folded engine, aligned generic starts, cursor boundaries and masked fringes.170182: incremental integer-square-root window bound idea.170141: doubled-row fusion;167897/167233/167082/167080/167081: first-writer48 stream, generic32 unroll and deferred tails/diagonals.166996/166395/166337/166311/166022/165981: inherited fused low rows and cursor methods;164972/164866/164808/164782: full-width load/store methods. No separate source license is attached.
Idea / 思路: Build the sorted list of actual generic parent divisors once, removing folded child rows from traversal itself. Advance the integer-square-root bound monotonically once per physical window and grow the active prefix of this list. Each window then visits only relevant parent cursors, without repeated64-bit i*i bounds or per-row child/modulus tests. Keep170438 original scalar/SSE child products because the wider partner experiment did not improve official timing. All row order, product coverage and cursor/tail behavior remain unchanged. Purpose: reduce the per-window scheduler overhead with full100M and boundary/arbitrary correctness checks before official measurement. */

/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/170669: complete lexical three-region multiply implementation, with all inherited notices above retained. saffah_codex_6a_agg3 https://duck.ac/submission/170611: idea of separating initial masked partner folds from steady unconditional folds; that earlier generic-lambda implementation was slow. Duck sources have no additional license notice.
Idea / 思路: In the two partner-enabled lexical regions, test once whether the starting aligned cursor is past every child cursor. If so, use a full lexical copy of the body whose partner additions are unconditional; otherwise retain the original masked boundary body. All later product indices increase, so the single row test suffices. This combines the observed efficient lexical layout with removing repeated child-start comparisons inside each32-product iteration. Purpose: reduce folded-row bookkeeping, with full100M and fallback verification before online measurement. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/170707: complete lexical steady-fold engine; https://duck.ac/submission/170526: first-writer low-row fusion idea. All inherited authors and notices above retained.
Idea / 思路: Fuse row8 into the existing row4 SSE vector before the48-output first-writer stores. Each16-output section computes two row8 products and interleaves them into the four row4 products. Mask the initial diagonal/crossing section, handle window fringes with a row8 cursor, and delete row8 from generic traversal and final tails. Purpose: eliminate row8's separate destination read-modify-write stream. Validate all100M outputs plus boundaries and fallback cases before official timing. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/170728: complete first-writer row8 fusion and lexical engine. All inherited sources above retained.
Idea / 思路: Extend the row8 first-writer vector with one row16 scalar product in its low lane for each16 output positions. Use its exact diagonal cutoff and cursor fringes, then remove row16 from generic traversal and final tails. Purpose: eliminate another sparse destination read-modify-write pass while reusing row8-to-row4 interleaving. Full100M, random, boundaries and small cases verified before official timing. */
#include<type_traits>
#include <immintrin.h>
#include <algorithm>
#include <cstdint>
#include <vector>
#include <cstring>

static __attribute__((always_inline))inline __m256i root_ld256(const void*p){__m256i v;__asm__("vmovups %1,%0":"=x"(v):"m"(*(const __m256i*)p));return v;}
static __attribute__((always_inline,target("avx")))inline __m256i root_single256_li(const __m256i*p){__m256i v;__asm__("vmovdqu %1,%0":"=x"(v):"m"(*(const unsigned char(*)[32])p));return v;}
static __attribute__((always_inline,target("avx")))inline void root_single256_si(__m256i*p,__m256i v){__asm__("vmovdqu %1,%0":"=m"(*(unsigned char(*)[32])p):"x"(v));}
static __attribute__((always_inline,target("avx")))inline __m256d root_single256_ld(const double*p){__m256d v;__asm__("vmovupd %1,%0":"=x"(v):"m"(*(const unsigned char(*)[32])p));return v;}
static __attribute__((always_inline,target("avx")))inline void root_single256_sd(double*p,__m256d v){__asm__("vmovupd %1,%0":"=m"(*(unsigned char(*)[32])p):"x"(v));}
static __attribute__((always_inline,target("avx")))inline __m256 root_single256_lf(const float*p){__m256 v;__asm__("vmovups %1,%0":"=x"(v):"m"(*(const unsigned char(*)[32])p));return v;}
static __attribute__((always_inline,target("avx")))inline void root_single256_sf(float*p,__m256 v){__asm__("vmovups %1,%0":"=m"(*(unsigned char(*)[32])p):"x"(v));}
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
namespace root_fast {
using u32=unsigned;using u64=unsigned long long;
inline u32 reduce(__m256i x){__m128i y=_mm_add_epi32(_mm256_castsi256_si128(x),_mm256_extracti128_si256(x,1));y=_mm_add_epi32(y,_mm_srli_si128(y,8));y=_mm_add_epi32(y,_mm_srli_si128(y,4));return _mm_cvtsi128_si32(y);}
inline void divide(unsigned n,const unsigned*__restrict a,const unsigned*__restrict b,unsigned*__restrict c){
if(!n)return;u32 sb=0;for(unsigned j=1;j<n;++j)sb+=b[j];c[0]=a[0]*sb;
constexpr unsigned block=65536;
for(unsigned lo=1;lo<n;lo+=block){unsigned hi=std::min(n,lo+block);
for(unsigned i=1;u64(i)*i<hi;++i){
unsigned j=std::max(i,(lo+i-1)/i),last=(hi-1)/i,k=i*j;u32 sum=0,bi=b[i];
if(j==i){sum+=a[k]*bi;++j;k+=i;}
__m256i vs=_mm256_setzero_si256(),vb=_mm256_set1_epi32(bi),ix=_mm256_setr_epi32(0,i,2*i,3*i,4*i,5*i,6*i,7*i);
for(;j+7<=last;j+=8,k+=8*i){
__m256i x=_mm256_i32gather_epi32((const int*)(a+k),ix,4);
vs=_mm256_add_epi32(vs,_mm256_mullo_epi32(x,root_ld256(b+j)));
__m256i old=_mm256_loadu_si256((const __m256i*)(c+j));
_mm256_storeu_si256((__m256i*)(c+j),_mm256_add_epi32(old,_mm256_mullo_epi32(x,vb)));
}
sum+=reduce(vs);
for(;j<=last;++j,k+=i){u32 x=a[k];sum+=x*b[j];c[j]+=x*bi;}c[i]+=sum;
}
}
}
inline void floor_conv(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){
if(!n)return;std::vector<u32>prefix(n);u32 total=0;
for(unsigned i=0;i<n;++i){prefix[i]=total;total+=a[i];}
divide(n,prefix.data(),b,c);
u32 tail=0,previous=0;unsigned bound=n;
for(unsigned k=1;k<n;++k){unsigned need=(n-1)/k+1;while(bound>need)tail+=b[--bound];u32 current=c[k]+total*tail;c[k-1]=current-previous;previous=current;}
while(bound>1)tail+=b[--bound];c[n-1]=total*tail-previous;
}
inline std::vector<unsigned> primes(unsigned n){
std::vector<unsigned char> comp((n+1)/2);std::vector<unsigned> ps;
if(n>2)ps.push_back(2);
for(unsigned i=3;u64(i)*i<n;i+=2)if(!comp[i/2])for(unsigned j=i*i;j<n;j+=i*2)comp[j/2]=1;
for(unsigned i=3;i<n;i+=2)if(!comp[i/2])ps.push_back(i);return ps;
}
inline void gcd_conv(unsigned n,const unsigned*__restrict a,const unsigned*__restrict b,unsigned*__restrict c){
if(!n)return;auto ps=primes(n);std::vector<unsigned> f(b,b+n);std::memcpy(c,a,size_t(n)*4);
for(unsigned p:ps){
unsigned i=(n-1)/p;__m256i ix=_mm256_setr_epi32(0,p,2*p,3*p,4*p,5*p,6*p,7*p);
for(;i>=15;i-=8){unsigned l=i-7;
auto x=_mm256_i32gather_epi32((const int*)(c+l*p),ix,4),y=_mm256_i32gather_epi32((const int*)(f.data()+l*p),ix,4);
_mm256_storeu_si256((__m256i*)(c+l),_mm256_add_epi32(_mm256_loadu_si256((const __m256i*)(c+l)),x));
_mm256_storeu_si256((__m256i*)(f.data()+l),_mm256_add_epi32(_mm256_loadu_si256((const __m256i*)(f.data()+l)),y));
}
for(;i;--i){c[i]+=c[i*p];f[i]+=f[i*p];}
}
for(unsigned i=1;i<n;++i)c[i]*=f[i];
for(unsigned p:ps){
unsigned last=(n-1)/p,i=1;__m256i ix=_mm256_setr_epi32(0,p,2*p,3*p,4*p,5*p,6*p,7*p);
for(;i+7<=last;i+=8){auto x=_mm256_i32gather_epi32((const int*)(c+i*p),ix,4);_mm256_storeu_si256((__m256i*)(c+i),_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(c+i)),x));}
for(;i<=last;++i)c[i]-=c[i*p];
}
c[0]=a[0]*b[0];for(unsigned i=1;i<n;++i)c[i]+=a[0]*b[i]+b[0]*a[i];
}
}
namespace root_fast {
inline void lcm_conv(unsigned n,const unsigned*__restrict a,const unsigned*__restrict b,unsigned*__restrict c){
if(!n)return;auto ps=primes(n);std::vector<unsigned>f(b,b+n);std::memcpy(c,a,size_t(n)*4);
u32 sa=0,sb=0;for(unsigned i=0;i<n;++i){sa+=a[i];sb+=b[i];}
for(unsigned p:ps){unsigned last=(n-1)/p;for(unsigned i=1,k=p;i<=last;++i,k+=p){c[k]+=c[i];f[k]+=f[i];}}
for(unsigned i=1;i<n;++i)c[i]*=f[i];
for(unsigned p:ps){for(unsigned i=(n-1)/p,k=i*p;i;--i,k-=p)c[k]-=c[i];}
c[0]=a[0]*sb+b[0]*sa-a[0]*b[0];
}
#ifdef ROOT_PAIR_CHECK
static uint64_t root_pair_hits=0;
#endif
#ifdef ROOT_ROW_FLAGS_CHECK
static uint64_t root_row_flags_hits=0;
#endif
#ifdef ROOT_PHASE_CHECK
static uint64_t root_phase_hits=0;
#endif
inline void multiply(unsigned n,const unsigned*__restrict a,const unsigned*__restrict b,unsigned*__restrict c){
if(!n)return;if(n==1){c[0]=a[0]*b[0];return;}
__m256i vsa=_mm256_setzero_si256(),vsb=_mm256_setzero_si256();
u32 sa=a[0]+a[1],sb=b[0]+b[1];
const unsigned block=49152;
unsigned bound=1;while(u64(bound)*bound<n)++bound;
struct Position{unsigned j,k;};std::vector<Position>position(bound+1);
for(unsigned i=1;i<bound;++i)position[i]={i+1,i*i+i};c[1]=0;std::vector<unsigned> rows;rows.reserve(bound);for(unsigned i=5;i<bound;++i){if(i==8||i==16)continue;if(i>=10&&(i&3)==2)continue;if(i>=20&&(i&7)==4)continue;if(i==12||i==24)continue;rows.push_back(i);}unsigned imax=3,active=0;
position[2]={3,6};
const u32 a1=a[1],b1=b[1],a2=n>2?a[2]:0,b2=n>2?b[2]:0;
const bool root_sixteen=bound>16;const unsigned a16=n>16?a[16]:0,b16=n>16?b[16]:0;const bool root_eight=bound>8;const unsigned a8=n>8?a[8]:0,b8=n>8?b[8]:0;const __m128i va8=_mm_set1_epi32(a8),vb8=_mm_set1_epi32(b8);const bool root_four=bound>4;const u32 root_a4=n>4?a[4]:0,root_b4=n>4?b[4]:0;
const __m128i root_va4=_mm_set1_epi32(root_a4),root_vb4=_mm_set1_epi32(root_b4),root_zero128=_mm_setzero_si128();
const bool root_three=bound>3;const u32 a3r=n>3?a[3]:0,b3r=n>3?b[3]:0;
const __m256i va3=_mm256_set1_epi32((int)a3r),vb3=_mm256_set1_epi32((int)b3r);
const __m256i g0i=_mm256_setr_epi32(0,0,0,1,0,0,2,0),g1i=_mm256_setr_epi32(0,3,0,0,4,0,0,5);
const __m256i h0i=_mm256_setr_epi32(0,0,0,0,0,1,0,0),h1i=_mm256_setr_epi32(2,0,0,3,0,0,4,0);
const __m256i k0i=_mm256_setr_epi32(0,0,0,0,1,0,0,2),k1i=_mm256_setr_epi32(0,0,3,0,0,4,0,0);
const auto va1=_mm256_set1_epi32(a1),vb1=_mm256_set1_epi32(b1),va2=_mm256_set1_epi32(a2),vb2=_mm256_set1_epi32(b2),zero=_mm256_setzero_si256();
for(unsigned lo=1;lo<n;lo+=block){unsigned hi=std::min(n,lo+block);while(u64(imax)*imax<hi)++imax;while(active<rows.size()&&rows[active]<imax)++active;
unsigned k=position[1].k,j2=position[2].j,k2=position[2].k;
unsigned root_j4=root_four?position[4].j:0,root_k4=root_four?position[4].k:hi;unsigned root_j8=root_eight?position[8].j:0,root_k8=root_eight?position[8].k:hi;unsigned root_j16=root_sixteen?position[16].j:0,root_k16=root_sixteen?position[16].k:hi;
unsigned j3=root_three?position[3].j:0,k3=root_three?position[3].k:hi;
for(;k<hi&&(k%48);++k){u32 av=a[k],bv=b[k];sa+=av;sb+=bv;c[k]=a1*bv+b1*av;}
for(;k2<k&&k2<hi;++j2,k2+=2)c[k2]+=a2*b[j2]+b2*a[j2];
for(;root_k4<k&&root_k4<hi;++root_j4,root_k4+=4)c[root_k4]+=root_a4*b[root_j4]+root_b4*a[root_j4];for(;root_k8<k&&root_k8<hi;++root_j8,root_k8+=8)c[root_k8]+=a8*b[root_j8]+b8*a[root_j8];for(;root_k16<k&&root_k16<hi;++root_j16,root_k16+=16)c[root_k16]+=a16*b[root_j16]+b16*a[root_j16];
for(;k3<k&&k3<hi;++j3,k3+=3)c[k3]+=a3r*b[j3]+b3r*a[j3];
for(;k+47<hi;k+=48,j2+=24,k2+=48){
unsigned q=k/3;
{
auto av0=_mm256_loadu_si256((const __m256i*)(a+k)),av1=_mm256_loadu_si256((const __m256i*)(a+k+8));
auto bv0=_mm256_loadu_si256((const __m256i*)(b+k)),bv1=_mm256_loadu_si256((const __m256i*)(b+k+8));
vsa=_mm256_add_epi32(vsa,_mm256_add_epi32(av0,av1));vsb=_mm256_add_epi32(vsb,_mm256_add_epi32(bv0,bv1));
auto u0=_mm256_add_epi32(_mm256_mullo_epi32(va1,bv0),_mm256_mullo_epi32(vb1,av0));
auto u1=_mm256_add_epi32(_mm256_mullo_epi32(va1,bv1),_mm256_mullo_epi32(vb1,av1));
auto xy=_mm256_add_epi32(_mm256_mullo_epi32(va2,_mm256_loadu_si256((const __m256i*)(b+j2))),_mm256_mullo_epi32(vb2,_mm256_loadu_si256((const __m256i*)(a+j2))));
auto xl=_mm256_unpacklo_epi32(xy,zero),xh=_mm256_unpackhi_epi32(xy,zero);
auto x0=_mm256_permute2x128_si256(xl,xh,0x20),x1=_mm256_permute2x128_si256(xl,xh,0x31);
if(root_four){unsigned w=k/4;__m128i four=_mm_add_epi32(_mm_mullo_epi32(root_va4,_mm_loadu_si128((const __m128i*)(b+w))),_mm_mullo_epi32(root_vb4,_mm_loadu_si128((const __m128i*)(a+w))));if(root_eight){unsigned q=w/2;__m128i more=_mm_add_epi32(_mm_mullo_epi32(va8,_mm_loadl_epi64((const __m128i*)(b+q))),_mm_mullo_epi32(vb8,_mm_loadl_epi64((const __m128i*)(a+q))));if(k<96)more=_mm_and_si128(more,_mm_cmpgt_epi32(_mm_setr_epi32(q,q+1,0,0),_mm_set1_epi32(8)));if(root_sixteen&&q>=34){unsigned r=q/2;more=_mm_add_epi32(more,_mm_cvtsi32_si128(a16*b[r]+b16*a[r]));}four=_mm_add_epi32(four,_mm_unpacklo_epi32(more,root_zero128));}
x0=_mm256_add_epi32(x0,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(four,root_zero128)));
x1=_mm256_add_epi32(x1,_mm256_cvtepu32_epi64(_mm_unpackhi_epi32(four,root_zero128)));}
if(root_three){__m256i g=_mm256_add_epi32(_mm256_mullo_epi32(va3,_mm256_loadu_si256((const __m256i*)(b+q))),_mm256_mullo_epi32(vb3,_mm256_loadu_si256((const __m256i*)(a+q))));
x0=_mm256_add_epi32(x0,_mm256_blend_epi32(_mm256_permutevar8x32_epi32(g,g0i),zero,0xB6));
x1=_mm256_add_epi32(x1,_mm256_blend_epi32(_mm256_permutevar8x32_epi32(g,g1i),zero,0x6D));}
_mm256_storeu_si256((__m256i*)(c+k),_mm256_add_epi32(u0,x0));
_mm256_storeu_si256((__m256i*)(c+k+8),_mm256_add_epi32(u1,x1));
}
{
auto av0=_mm256_loadu_si256((const __m256i*)(a+k+16)),av1=_mm256_loadu_si256((const __m256i*)(a+k+24));
auto bv0=_mm256_loadu_si256((const __m256i*)(b+k+16)),bv1=_mm256_loadu_si256((const __m256i*)(b+k+24));
vsa=_mm256_add_epi32(vsa,_mm256_add_epi32(av0,av1));vsb=_mm256_add_epi32(vsb,_mm256_add_epi32(bv0,bv1));
auto u0=_mm256_add_epi32(_mm256_mullo_epi32(va1,bv0),_mm256_mullo_epi32(vb1,av0));
auto u1=_mm256_add_epi32(_mm256_mullo_epi32(va1,bv1),_mm256_mullo_epi32(vb1,av1));
auto xy=_mm256_add_epi32(_mm256_mullo_epi32(va2,_mm256_loadu_si256((const __m256i*)(b+j2+8))),_mm256_mullo_epi32(vb2,_mm256_loadu_si256((const __m256i*)(a+j2+8))));
auto xl=_mm256_unpacklo_epi32(xy,zero),xh=_mm256_unpackhi_epi32(xy,zero);
auto x0=_mm256_permute2x128_si256(xl,xh,0x20),x1=_mm256_permute2x128_si256(xl,xh,0x31);
if(root_four){unsigned w=k/4+4;__m128i four=_mm_add_epi32(_mm_mullo_epi32(root_va4,_mm_loadu_si128((const __m128i*)(b+w))),_mm_mullo_epi32(root_vb4,_mm_loadu_si128((const __m128i*)(a+w))));if(root_eight){unsigned q=w/2;__m128i more=_mm_add_epi32(_mm_mullo_epi32(va8,_mm_loadl_epi64((const __m128i*)(b+q))),_mm_mullo_epi32(vb8,_mm_loadl_epi64((const __m128i*)(a+q))));if(k<96)more=_mm_and_si128(more,_mm_cmpgt_epi32(_mm_setr_epi32(q,q+1,0,0),_mm_set1_epi32(8)));if(root_sixteen&&q>=34){unsigned r=q/2;more=_mm_add_epi32(more,_mm_cvtsi32_si128(a16*b[r]+b16*a[r]));}four=_mm_add_epi32(four,_mm_unpacklo_epi32(more,root_zero128));}
x0=_mm256_add_epi32(x0,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(four,root_zero128)));
x1=_mm256_add_epi32(x1,_mm256_cvtepu32_epi64(_mm_unpackhi_epi32(four,root_zero128)));}
if(root_three){__m256i g=_mm256_add_epi32(_mm256_mullo_epi32(va3,_mm256_loadu_si256((const __m256i*)(b+q+6))),_mm256_mullo_epi32(vb3,_mm256_loadu_si256((const __m256i*)(a+q+6))));
x0=_mm256_add_epi32(x0,_mm256_blend_epi32(_mm256_permutevar8x32_epi32(g,h0i),zero,0xDB));
x1=_mm256_add_epi32(x1,_mm256_blend_epi32(_mm256_permutevar8x32_epi32(g,h1i),zero,0xB6));}
_mm256_storeu_si256((__m256i*)(c+k+16),_mm256_add_epi32(u0,x0));
_mm256_storeu_si256((__m256i*)(c+k+24),_mm256_add_epi32(u1,x1));
}
{
auto av0=_mm256_loadu_si256((const __m256i*)(a+k+32)),av1=_mm256_loadu_si256((const __m256i*)(a+k+40));
auto bv0=_mm256_loadu_si256((const __m256i*)(b+k+32)),bv1=_mm256_loadu_si256((const __m256i*)(b+k+40));
vsa=_mm256_add_epi32(vsa,_mm256_add_epi32(av0,av1));vsb=_mm256_add_epi32(vsb,_mm256_add_epi32(bv0,bv1));
auto u0=_mm256_add_epi32(_mm256_mullo_epi32(va1,bv0),_mm256_mullo_epi32(vb1,av0));
auto u1=_mm256_add_epi32(_mm256_mullo_epi32(va1,bv1),_mm256_mullo_epi32(vb1,av1));
auto xy=_mm256_add_epi32(_mm256_mullo_epi32(va2,_mm256_loadu_si256((const __m256i*)(b+j2+16))),_mm256_mullo_epi32(vb2,_mm256_loadu_si256((const __m256i*)(a+j2+16))));
auto xl=_mm256_unpacklo_epi32(xy,zero),xh=_mm256_unpackhi_epi32(xy,zero);
auto x0=_mm256_permute2x128_si256(xl,xh,0x20),x1=_mm256_permute2x128_si256(xl,xh,0x31);
if(root_four){unsigned w=k/4+8;__m128i four=_mm_add_epi32(_mm_mullo_epi32(root_va4,_mm_loadu_si128((const __m128i*)(b+w))),_mm_mullo_epi32(root_vb4,_mm_loadu_si128((const __m128i*)(a+w))));if(root_eight){unsigned q=w/2;__m128i more=_mm_add_epi32(_mm_mullo_epi32(va8,_mm_loadl_epi64((const __m128i*)(b+q))),_mm_mullo_epi32(vb8,_mm_loadl_epi64((const __m128i*)(a+q))));if(k<96)more=_mm_and_si128(more,_mm_cmpgt_epi32(_mm_setr_epi32(q,q+1,0,0),_mm_set1_epi32(8)));if(root_sixteen&&q>=34){unsigned r=q/2;more=_mm_add_epi32(more,_mm_cvtsi32_si128(a16*b[r]+b16*a[r]));}four=_mm_add_epi32(four,_mm_unpacklo_epi32(more,root_zero128));}
x0=_mm256_add_epi32(x0,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(four,root_zero128)));
x1=_mm256_add_epi32(x1,_mm256_cvtepu32_epi64(_mm_unpackhi_epi32(four,root_zero128)));}
if(root_three){__m256i g=_mm256_add_epi32(_mm256_mullo_epi32(va3,_mm256_loadu_si256((const __m256i*)(b+q+11))),_mm256_mullo_epi32(vb3,_mm256_loadu_si256((const __m256i*)(a+q+11))));
x0=_mm256_add_epi32(x0,_mm256_blend_epi32(_mm256_permutevar8x32_epi32(g,k0i),zero,0x6D));
x1=_mm256_add_epi32(x1,_mm256_blend_epi32(_mm256_permutevar8x32_epi32(g,k1i),zero,0xDB));}
_mm256_storeu_si256((__m256i*)(c+k+32),_mm256_add_epi32(u0,x0));
_mm256_storeu_si256((__m256i*)(c+k+40),_mm256_add_epi32(u1,x1));
}
if(root_four){root_j4=k/4+12;root_k4=k+48;}if(root_eight){root_j8=k/8+6;root_k8=k+48;}if(root_sixteen&&k+48>272){root_j16=k/16+3;root_k16=k+48;}
j3=q+16;k3=k+48;
}
for(;k<hi;++k){u32 av=a[k],bv=b[k];sa+=av;sb+=bv;c[k]=a1*bv+b1*av;}
for(;k2<hi;++j2,k2+=2)c[k2]+=a2*b[j2]+b2*a[j2];
for(;root_k4<hi;++root_j4,root_k4+=4)c[root_k4]+=root_a4*b[root_j4]+root_b4*a[root_j4];for(;root_k8<hi;++root_j8,root_k8+=8)c[root_k8]+=a8*b[root_j8]+b8*a[root_j8];for(;root_k16<hi;++root_j16,root_k16+=16)c[root_k16]+=a16*b[root_j16]+b16*a[root_j16];
for(;k3<hi;++j3,k3+=3)c[k3]+=a3r*b[j3]+b3r*a[j3];
position[1]={k,k};position[2]={j2,k2};if(root_four)position[4]={root_j4,root_k4};if(root_eight)position[8]={root_j8,root_k8};if(root_sixteen)position[16]={root_j16,root_k16};if(root_three)position[3]={j3,k3};
for(unsigned row=0;row<active;++row){unsigned i=rows[row];
unsigned j=position[i].j,k=position[i].k;
if(k+7*i>=hi)continue;
u32 ai=a[i],bi=b[i];
auto va=_mm256_set1_epi32((int)ai),vb=_mm256_set1_epi32((int)bi);
unsigned kend=(7u*i<hi)?hi-7u*i:0u;
const bool root_pair=(i>=5&&((i&1)||i==6)&&2*i<bound);
const unsigned root_start=root_pair?position[2*i].j:0;
const __m128i root_av2=_mm_set1_epi32(root_pair?a[2*i]:0),root_bv2=_mm_set1_epi32(root_pair?b[2*i]:0);
const bool root_deep=root_pair&&(4*i<bound);
const bool root_pair4=root_pair&&4*i<bound;
const unsigned root_start4=root_pair4?position[4*i].j:0;
const __m128i root_av4=_mm_set1_epi32(root_pair4?a[4*i]:0),root_bv4=_mm_set1_epi32(root_pair4?b[4*i]:0);
{if(root_pair){while(j&7){c[k]+=ai*b[j]+bi*a[j];++j;k+=i;}}}
#ifdef ROOT_ROW_FLAGS_CHECK
++root_row_flags_hits;
#endif
if(!root_pair){auto root_double=[&](__m256i value,unsigned jj){
if constexpr(!false)return value;
unsigned half=jj/2;
if(half>=root_start){
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(more));}
else if(half+3>=root_start){
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
__m128i mask=_mm_cmpgt_epi32(_mm_setr_epi32(half,half+1,half+2,half+3),_mm_set1_epi32(root_start-1));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_and_si128(more,mask)));}
if constexpr(false){unsigned h4=jj/4;
 if(h4>=root_start4){__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
  value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(m4,root_zero128)));}
 else if(h4+1>=root_start4){__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
  __m128i k4=_mm_cmpgt_epi32(_mm_setr_epi32(h4,h4+1,0,0),_mm_set1_epi32(root_start4-1));
  value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(_mm_and_si128(m4,k4),root_zero128)));}}
return value;
};
{unsigned kend32=(31u*i<hi)?hi-31u*i:0u;
for(;k<kend32;j+=32,k+=32*i){
auto v0=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
v0=root_double(v0,j);
auto v1=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+8)),_mm256_mullo_epi32(vb,root_ld256(a+j+8)));
v1=root_double(v1,j+8);
auto v2=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+16)),_mm256_mullo_epi32(vb,root_ld256(a+j+16)));
v2=root_double(v2,j+16);
auto v3=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+24)),_mm256_mullo_epi32(vb,root_ld256(a+j+24)));
v3=root_double(v3,j+24);
alignas(32)u32 v[8];
_mm256_store_si256((__m256i*)v,v0);c[k]+=v[0];c[k+1*i]+=v[1];c[k+2*i]+=v[2];c[k+3*i]+=v[3];c[k+4*i]+=v[4];c[k+5*i]+=v[5];c[k+6*i]+=v[6];c[k+7*i]+=v[7];
_mm256_store_si256((__m256i*)v,v1);c[k+8*i]+=v[0];c[k+9*i]+=v[1];c[k+10*i]+=v[2];c[k+11*i]+=v[3];c[k+12*i]+=v[4];c[k+13*i]+=v[5];c[k+14*i]+=v[6];c[k+15*i]+=v[7];
_mm256_store_si256((__m256i*)v,v2);c[k+16*i]+=v[0];c[k+17*i]+=v[1];c[k+18*i]+=v[2];c[k+19*i]+=v[3];c[k+20*i]+=v[4];c[k+21*i]+=v[5];c[k+22*i]+=v[6];c[k+23*i]+=v[7];
_mm256_store_si256((__m256i*)v,v3);c[k+24*i]+=v[0];c[k+25*i]+=v[1];c[k+26*i]+=v[2];c[k+27*i]+=v[3];c[k+28*i]+=v[4];c[k+29*i]+=v[5];c[k+30*i]+=v[6];c[k+31*i]+=v[7];
}
for(;k<kend;j+=8,k+=8*i){
auto vxy=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
vxy=root_double(vxy,j);
alignas(32)u32 v[8];_mm256_store_si256((__m256i*)v,vxy);c[k]+=v[0];c[k+i]+=v[1];c[k+2*i]+=v[2];c[k+3*i]+=v[3];c[k+4*i]+=v[4];c[k+5*i]+=v[5];c[k+6*i]+=v[6];c[k+7*i]+=v[7];
}}
}else if(root_pair4){const unsigned root_cut2=2u*root_start;const unsigned root_cut4=4u*root_start4;unsigned root_k32=(31u*i<hi)?hi-31u*i:0u;
auto root_masked=[&](__m256i value,unsigned jj){
if constexpr(!true)return value;
unsigned half=jj/2;
if(half>=root_start){
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(more));}
else if(half+3>=root_start){
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
__m128i mask=_mm_cmpgt_epi32(_mm_setr_epi32(half,half+1,half+2,half+3),_mm_set1_epi32(root_start-1));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_and_si128(more,mask)));}
if constexpr(true){unsigned h4=jj/4;
 if(h4>=root_start4){__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
  value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(m4,root_zero128)));}
 else if(h4+1>=root_start4){__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
  __m128i k4=_mm_cmpgt_epi32(_mm_setr_epi32(h4,h4+1,0,0),_mm_set1_epi32(root_start4-1));
  value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(_mm_and_si128(m4,k4),root_zero128)));}}
return value;
};
auto root_full2=[&](__m256i value,unsigned jj) __attribute__((always_inline)){
#ifdef ROOT_PHASE_CHECK
 if(jj<2*root_start||(root_pair4&&jj+4>=4*root_start4))__builtin_trap();++root_phase_hits;
#endif
 unsigned half=jj/2;__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
 return _mm256_add_epi32(value,_mm256_cvtepu32_epi64(more));};
auto root_full4=[&](__m256i value,unsigned jj) __attribute__((always_inline)){
#ifdef ROOT_PHASE_CHECK
 if(jj<2*root_start||jj<4*root_start4)__builtin_trap();++root_phase_hits;
#endif
 unsigned half=jj/2;__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(more));
 unsigned h4=jj/4;__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));return _mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(m4,root_zero128)));};
for(;k<root_k32&&j+30<root_cut2&&j+28<root_cut4;j+=32,k+=32*i){
auto v0=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));

auto v1=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+8)),_mm256_mullo_epi32(vb,root_ld256(a+j+8)));

auto v2=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+16)),_mm256_mullo_epi32(vb,root_ld256(a+j+16)));

auto v3=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+24)),_mm256_mullo_epi32(vb,root_ld256(a+j+24)));

alignas(32)u32 v[8];
_mm256_store_si256((__m256i*)v,v0);c[k]+=v[0];c[k+1*i]+=v[1];c[k+2*i]+=v[2];c[k+3*i]+=v[3];c[k+4*i]+=v[4];c[k+5*i]+=v[5];c[k+6*i]+=v[6];c[k+7*i]+=v[7];
_mm256_store_si256((__m256i*)v,v1);c[k+8*i]+=v[0];c[k+9*i]+=v[1];c[k+10*i]+=v[2];c[k+11*i]+=v[3];c[k+12*i]+=v[4];c[k+13*i]+=v[5];c[k+14*i]+=v[6];c[k+15*i]+=v[7];
_mm256_store_si256((__m256i*)v,v2);c[k+16*i]+=v[0];c[k+17*i]+=v[1];c[k+18*i]+=v[2];c[k+19*i]+=v[3];c[k+20*i]+=v[4];c[k+21*i]+=v[5];c[k+22*i]+=v[6];c[k+23*i]+=v[7];
_mm256_store_si256((__m256i*)v,v3);c[k+24*i]+=v[0];c[k+25*i]+=v[1];c[k+26*i]+=v[2];c[k+27*i]+=v[3];c[k+28*i]+=v[4];c[k+29*i]+=v[5];c[k+30*i]+=v[6];c[k+31*i]+=v[7];
}
for(;k<kend&&j<root_cut2;j+=8,k+=8*i){
auto vxy=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
vxy=root_masked(vxy,j);
alignas(32)u32 v[8];_mm256_store_si256((__m256i*)v,vxy);c[k]+=v[0];c[k+i]+=v[1];c[k+2*i]+=v[2];c[k+3*i]+=v[3];c[k+4*i]+=v[4];c[k+5*i]+=v[5];c[k+6*i]+=v[6];c[k+7*i]+=v[7];
}
for(;k<root_k32&&j+28<root_cut4;j+=32,k+=32*i){
auto v0=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
v0=root_full2(v0,j);
auto v1=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+8)),_mm256_mullo_epi32(vb,root_ld256(a+j+8)));
v1=root_full2(v1,j+8);
auto v2=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+16)),_mm256_mullo_epi32(vb,root_ld256(a+j+16)));
v2=root_full2(v2,j+16);
auto v3=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+24)),_mm256_mullo_epi32(vb,root_ld256(a+j+24)));
v3=root_full2(v3,j+24);
alignas(32)u32 v[8];
_mm256_store_si256((__m256i*)v,v0);c[k]+=v[0];c[k+1*i]+=v[1];c[k+2*i]+=v[2];c[k+3*i]+=v[3];c[k+4*i]+=v[4];c[k+5*i]+=v[5];c[k+6*i]+=v[6];c[k+7*i]+=v[7];
_mm256_store_si256((__m256i*)v,v1);c[k+8*i]+=v[0];c[k+9*i]+=v[1];c[k+10*i]+=v[2];c[k+11*i]+=v[3];c[k+12*i]+=v[4];c[k+13*i]+=v[5];c[k+14*i]+=v[6];c[k+15*i]+=v[7];
_mm256_store_si256((__m256i*)v,v2);c[k+16*i]+=v[0];c[k+17*i]+=v[1];c[k+18*i]+=v[2];c[k+19*i]+=v[3];c[k+20*i]+=v[4];c[k+21*i]+=v[5];c[k+22*i]+=v[6];c[k+23*i]+=v[7];
_mm256_store_si256((__m256i*)v,v3);c[k+24*i]+=v[0];c[k+25*i]+=v[1];c[k+26*i]+=v[2];c[k+27*i]+=v[3];c[k+28*i]+=v[4];c[k+29*i]+=v[5];c[k+30*i]+=v[6];c[k+31*i]+=v[7];
}
for(;k<kend&&j<root_cut4;j+=8,k+=8*i){
auto vxy=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
vxy=root_masked(vxy,j);
alignas(32)u32 v[8];_mm256_store_si256((__m256i*)v,vxy);c[k]+=v[0];c[k+i]+=v[1];c[k+2*i]+=v[2];c[k+3*i]+=v[3];c[k+4*i]+=v[4];c[k+5*i]+=v[5];c[k+6*i]+=v[6];c[k+7*i]+=v[7];
}
{unsigned kend32=(31u*i<hi)?hi-31u*i:0u;
for(;k<kend32;j+=32,k+=32*i){
auto v0=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
v0=root_full4(v0,j);
auto v1=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+8)),_mm256_mullo_epi32(vb,root_ld256(a+j+8)));
v1=root_full4(v1,j+8);
auto v2=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+16)),_mm256_mullo_epi32(vb,root_ld256(a+j+16)));
v2=root_full4(v2,j+16);
auto v3=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+24)),_mm256_mullo_epi32(vb,root_ld256(a+j+24)));
v3=root_full4(v3,j+24);
alignas(32)u32 v[8];
_mm256_store_si256((__m256i*)v,v0);c[k]+=v[0];c[k+1*i]+=v[1];c[k+2*i]+=v[2];c[k+3*i]+=v[3];c[k+4*i]+=v[4];c[k+5*i]+=v[5];c[k+6*i]+=v[6];c[k+7*i]+=v[7];
_mm256_store_si256((__m256i*)v,v1);c[k+8*i]+=v[0];c[k+9*i]+=v[1];c[k+10*i]+=v[2];c[k+11*i]+=v[3];c[k+12*i]+=v[4];c[k+13*i]+=v[5];c[k+14*i]+=v[6];c[k+15*i]+=v[7];
_mm256_store_si256((__m256i*)v,v2);c[k+16*i]+=v[0];c[k+17*i]+=v[1];c[k+18*i]+=v[2];c[k+19*i]+=v[3];c[k+20*i]+=v[4];c[k+21*i]+=v[5];c[k+22*i]+=v[6];c[k+23*i]+=v[7];
_mm256_store_si256((__m256i*)v,v3);c[k+24*i]+=v[0];c[k+25*i]+=v[1];c[k+26*i]+=v[2];c[k+27*i]+=v[3];c[k+28*i]+=v[4];c[k+29*i]+=v[5];c[k+30*i]+=v[6];c[k+31*i]+=v[7];
}
for(;k<kend;j+=8,k+=8*i){
auto vxy=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
vxy=root_full4(vxy,j);
alignas(32)u32 v[8];_mm256_store_si256((__m256i*)v,vxy);c[k]+=v[0];c[k+i]+=v[1];c[k+2*i]+=v[2];c[k+3*i]+=v[3];c[k+4*i]+=v[4];c[k+5*i]+=v[5];c[k+6*i]+=v[6];c[k+7*i]+=v[7];
}}
}else{const unsigned root_cut2=2u*root_start;unsigned root_k32=(31u*i<hi)?hi-31u*i:0u;
auto root_masked=[&](__m256i value,unsigned jj){
if constexpr(!true)return value;
unsigned half=jj/2;
if(half>=root_start){
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(more));}
else if(half+3>=root_start){
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
__m128i mask=_mm_cmpgt_epi32(_mm_setr_epi32(half,half+1,half+2,half+3),_mm_set1_epi32(root_start-1));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_and_si128(more,mask)));}
if constexpr(false){unsigned h4=jj/4;
 if(h4>=root_start4){__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
  value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(m4,root_zero128)));}
 else if(h4+1>=root_start4){__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
  __m128i k4=_mm_cmpgt_epi32(_mm_setr_epi32(h4,h4+1,0,0),_mm_set1_epi32(root_start4-1));
  value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(_mm_and_si128(m4,k4),root_zero128)));}}
return value;
};
auto root_full2=[&](__m256i value,unsigned jj) __attribute__((always_inline)){
#ifdef ROOT_PHASE_CHECK
 if(jj<2*root_start||(root_pair4&&jj+4>=4*root_start4))__builtin_trap();++root_phase_hits;
#endif
 unsigned half=jj/2;__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
 return _mm256_add_epi32(value,_mm256_cvtepu32_epi64(more));};
for(;k<root_k32&&j+30<root_cut2;j+=32,k+=32*i){
auto v0=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));

auto v1=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+8)),_mm256_mullo_epi32(vb,root_ld256(a+j+8)));

auto v2=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+16)),_mm256_mullo_epi32(vb,root_ld256(a+j+16)));

auto v3=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+24)),_mm256_mullo_epi32(vb,root_ld256(a+j+24)));

alignas(32)u32 v[8];
_mm256_store_si256((__m256i*)v,v0);c[k]+=v[0];c[k+1*i]+=v[1];c[k+2*i]+=v[2];c[k+3*i]+=v[3];c[k+4*i]+=v[4];c[k+5*i]+=v[5];c[k+6*i]+=v[6];c[k+7*i]+=v[7];
_mm256_store_si256((__m256i*)v,v1);c[k+8*i]+=v[0];c[k+9*i]+=v[1];c[k+10*i]+=v[2];c[k+11*i]+=v[3];c[k+12*i]+=v[4];c[k+13*i]+=v[5];c[k+14*i]+=v[6];c[k+15*i]+=v[7];
_mm256_store_si256((__m256i*)v,v2);c[k+16*i]+=v[0];c[k+17*i]+=v[1];c[k+18*i]+=v[2];c[k+19*i]+=v[3];c[k+20*i]+=v[4];c[k+21*i]+=v[5];c[k+22*i]+=v[6];c[k+23*i]+=v[7];
_mm256_store_si256((__m256i*)v,v3);c[k+24*i]+=v[0];c[k+25*i]+=v[1];c[k+26*i]+=v[2];c[k+27*i]+=v[3];c[k+28*i]+=v[4];c[k+29*i]+=v[5];c[k+30*i]+=v[6];c[k+31*i]+=v[7];
}
for(;k<kend&&j<root_cut2;j+=8,k+=8*i){
auto vxy=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
vxy=root_masked(vxy,j);
alignas(32)u32 v[8];_mm256_store_si256((__m256i*)v,vxy);c[k]+=v[0];c[k+i]+=v[1];c[k+2*i]+=v[2];c[k+3*i]+=v[3];c[k+4*i]+=v[4];c[k+5*i]+=v[5];c[k+6*i]+=v[6];c[k+7*i]+=v[7];
}
{unsigned kend32=(31u*i<hi)?hi-31u*i:0u;
for(;k<kend32;j+=32,k+=32*i){
auto v0=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
v0=root_full2(v0,j);
auto v1=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+8)),_mm256_mullo_epi32(vb,root_ld256(a+j+8)));
v1=root_full2(v1,j+8);
auto v2=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+16)),_mm256_mullo_epi32(vb,root_ld256(a+j+16)));
v2=root_full2(v2,j+16);
auto v3=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+24)),_mm256_mullo_epi32(vb,root_ld256(a+j+24)));
v3=root_full2(v3,j+24);
alignas(32)u32 v[8];
_mm256_store_si256((__m256i*)v,v0);c[k]+=v[0];c[k+1*i]+=v[1];c[k+2*i]+=v[2];c[k+3*i]+=v[3];c[k+4*i]+=v[4];c[k+5*i]+=v[5];c[k+6*i]+=v[6];c[k+7*i]+=v[7];
_mm256_store_si256((__m256i*)v,v1);c[k+8*i]+=v[0];c[k+9*i]+=v[1];c[k+10*i]+=v[2];c[k+11*i]+=v[3];c[k+12*i]+=v[4];c[k+13*i]+=v[5];c[k+14*i]+=v[6];c[k+15*i]+=v[7];
_mm256_store_si256((__m256i*)v,v2);c[k+16*i]+=v[0];c[k+17*i]+=v[1];c[k+18*i]+=v[2];c[k+19*i]+=v[3];c[k+20*i]+=v[4];c[k+21*i]+=v[5];c[k+22*i]+=v[6];c[k+23*i]+=v[7];
_mm256_store_si256((__m256i*)v,v3);c[k+24*i]+=v[0];c[k+25*i]+=v[1];c[k+26*i]+=v[2];c[k+27*i]+=v[3];c[k+28*i]+=v[4];c[k+29*i]+=v[5];c[k+30*i]+=v[6];c[k+31*i]+=v[7];
}
for(;k<kend;j+=8,k+=8*i){
auto vxy=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
vxy=root_full2(vxy,j);
alignas(32)u32 v[8];_mm256_store_si256((__m256i*)v,vxy);c[k]+=v[0];c[k+i]+=v[1];c[k+2*i]+=v[2];c[k+3*i]+=v[3];c[k+4*i]+=v[4];c[k+5*i]+=v[5];c[k+6*i]+=v[6];c[k+7*i]+=v[7];
}}
}
position[i]={j,k};
if(root_pair&&j/2>root_start)position[2*i]={j/2,i*j};if(root_pair4&&j/4>root_start4)position[4*i]={j/4,i*j};
}
}
for(unsigned i=3;i<bound;++i)if(i!=4&&i!=8&&i!=16)if(!(bound>3&&i==3)){unsigned j=position[i].j,k=position[i].k;for(;k<n;++j,k+=i)c[k]+=a[i]*b[j]+b[i]*a[j];}
for(unsigned i=1;i<bound;++i)c[u64(i)*i]+=a[i]*b[i];
sa+=reduce(vsa);sb+=reduce(vsb);c[0]=a[0]*sb+b[0]*sa-a[0]*b[0];
}
}
void convolution(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){root_fast::multiply(n,a,b,c);}


CompilationN/AN/ACompile OKScore: N/A

Testcase #1857.058 ms381 MB + 608 KBAcceptedScore: 100


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