// Pure reference solution: no generator, input data, seed, digest or judge ABI.
#include <cstdint>
#include <cstddef>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <immintrin.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
namespace bitconv {
using u32=uint32_t;using u64=uint64_t;
template<bool And,bool Inverse> inline void leaf32(u32*f,size_t n){
const __m256i m1=And?_mm256_set_epi32(0,-1,0,-1,0,-1,0,-1):_mm256_set_epi32(-1,0,-1,0,-1,0,-1,0);
const __m256i m2=And?_mm256_set_epi32(0,0,-1,-1,0,0,-1,-1):_mm256_set_epi32(-1,-1,0,0,-1,-1,0,0);
const __m256i m4=And?_mm256_set_epi32(0,0,0,0,-1,-1,-1,-1):_mm256_set_epi32(-1,-1,-1,-1,0,0,0,0);
size_t done=n&~size_t(7);
for(size_t i=0;i<done;i+=8){
__m256i x=_mm256_loadu_si256((const __m256i*)(f+i));
__m256i y=_mm256_and_si256(_mm256_shuffle_epi32(x,0xb1),m1);x=Inverse?_mm256_sub_epi32(x,y):_mm256_add_epi32(x,y);
y=_mm256_and_si256(_mm256_shuffle_epi32(x,0x4e),m2);x=Inverse?_mm256_sub_epi32(x,y):_mm256_add_epi32(x,y);
y=_mm256_and_si256(_mm256_permute2x128_si256(x,x,1),m4);x=Inverse?_mm256_sub_epi32(x,y):_mm256_add_epi32(x,y);
_mm256_storeu_si256((__m256i*)(f+i),x);
}
if(done<n)for(size_t step=1;step<8;step*=2)for(size_t base=done;base<n;base+=2*step)if(base+step<n){size_t z=std::min(step,n-base-step);for(size_t j=0;j<z;++j){u32*d=f+base+(And?j:step+j);u32 s=f[base+(And?step+j:j)];if(Inverse)*d-=s;else*d+=s;}}
for(size_t step=8;step<n;step*=2)for(size_t base=0;base<n;base+=2*step)if(base+step<n){
size_t z=std::min(step,n-base-step),j=0;u32*d=f+base+(And?0:step);const u32*s=f+base+(And?step:0);
for(;j+8<=z;j+=8){__m256i a=_mm256_loadu_si256((const __m256i*)(d+j)),b=_mm256_loadu_si256((const __m256i*)(s+j));_mm256_storeu_si256((__m256i*)(d+j),Inverse?_mm256_sub_epi32(a,b):_mm256_add_epi32(a,b));}
for(;j<z;++j){if(Inverse)d[j]-=s[j];else d[j]+=s[j];}
}
}
template<bool And,bool Inverse> void transform32(u32*f,size_t n){
if(n<=1024){leaf32<And,Inverse>(f,n);return;}
size_t half=size_t(1)<<(63-__builtin_clzll(n-1));
transform32<And,Inverse>(f,half);transform32<And,Inverse>(f+half,n-half);
size_t z=n-half,j=0;u32*d=f+(And?0:half);const u32*s=f+(And?half:0);
for(;j+8<=z;j+=8){__m256i a=_mm256_loadu_si256((const __m256i*)(d+j)),b=_mm256_loadu_si256((const __m256i*)(s+j));_mm256_storeu_si256((__m256i*)(d+j),Inverse?_mm256_sub_epi32(a,b):_mm256_add_epi32(a,b));}
for(;j<z;++j){if(Inverse)d[j]-=s[j];else d[j]+=s[j];}
}
template<bool And> void solve32(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){
u32*t=(u32*)std::malloc(size_t(n)*4);if(!t)__builtin_trap();
std::memcpy(c,a,size_t(n)*4);std::memcpy(t,b,size_t(n)*4);
transform32<And,false>(c,n);transform32<And,false>(t,n);
size_t j=0;for(;j+8<=n;j+=8)_mm256_storeu_si256((__m256i*)(c+j),_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(c+j)),_mm256_loadu_si256((const __m256i*)(t+j))));
for(;j<n;++j)c[j]*=t[j];std::free(t);transform32<And,true>(c,n);
}
inline void leaf64(u64*f,size_t n){
// n is a power of two in all fast Walsh calls.
for(size_t base=0;base<n;base+=4){
__m256i x=_mm256_loadu_si256((const __m256i*)(f+base));
__m256i y=_mm256_permute4x64_epi64(x,0xb1),s=_mm256_add_epi64(x,y),d=_mm256_sub_epi64(y,x);
x=_mm256_blend_epi32(s,d,0xcc);
y=_mm256_permute4x64_epi64(x,0x4e);s=_mm256_add_epi64(x,y);d=_mm256_sub_epi64(y,x);
x=_mm256_blend_epi32(s,d,0xf0);_mm256_storeu_si256((__m256i*)(f+base),x);
}
for(size_t step=4;step<n;step*=2)for(size_t base=0;base<n;base+=2*step)for(size_t j=0;j<step;j+=4){
__m256i x=_mm256_loadu_si256((const __m256i*)(f+base+j)),y=_mm256_loadu_si256((const __m256i*)(f+base+step+j));
_mm256_storeu_si256((__m256i*)(f+base+j),_mm256_add_epi64(x,y));_mm256_storeu_si256((__m256i*)(f+base+step+j),_mm256_sub_epi64(x,y));
}
}
inline void fwht64(u64*f,size_t n){
if(n<4){if(n==2){u64 a=f[0],b=f[1];f[0]=a+b;f[1]=a-b;}return;}
if(n<=1024){leaf64(f,n);return;}size_t h=n/2;fwht64(f,h);fwht64(f+h,h);
for(size_t j=0;j<h;j+=4){__m256i a=_mm256_loadu_si256((const __m256i*)(f+j)),b=_mm256_loadu_si256((const __m256i*)(f+h+j));_mm256_storeu_si256((__m256i*)(f+j),_mm256_add_epi64(a,b));_mm256_storeu_si256((__m256i*)(f+h+j),_mm256_sub_epi64(a,b));}
}
inline __m256i mul64(__m256i a,__m256i b){
__m256i lo=_mm256_mul_epu32(a,b),ab=_mm256_mul_epu32(_mm256_srli_epi64(a,32),b),ba=_mm256_mul_epu32(a,_mm256_srli_epi64(b,32));
return _mm256_add_epi64(lo,_mm256_slli_epi64(_mm256_add_epi64(ab,ba),32));
}
inline void xor_small(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){
size_t m=1;unsigned k=0;while(m<n){m*=2;++k;}
u64*x=(u64*)std::malloc(m*8),*y=(u64*)std::malloc(m*8);if(!x||!y)__builtin_trap();
for(size_t j=0;j<m;++j){x[j]=j<n?a[j]:0;y[j]=j<n?b[j]:0;}fwht64(x,m);fwht64(y,m);
size_t j=0;for(;j+4<=m;j+=4)_mm256_storeu_si256((__m256i*)(x+j),mul64(_mm256_loadu_si256((__m256i*)(x+j)),_mm256_loadu_si256((__m256i*)(y+j))));
for(;j<m;++j)x[j]*=y[j];std::free(y);fwht64(x,m);for(j=0;j<n;++j)c[j]=u32(x[j]>>k);std::free(x);
}
inline void quarter_fwht(u64*const seg[4],size_t q){
for(unsigned s=0;s<4;++s)fwht64(seg[s],q);
for(size_t i=0;i<q;i+=4){
__m256i a=_mm256_loadu_si256((const __m256i*)(seg[0]+i)),b=_mm256_loadu_si256((const __m256i*)(seg[1]+i)),c=_mm256_loadu_si256((const __m256i*)(seg[2]+i)),d=_mm256_loadu_si256((const __m256i*)(seg[3]+i));
__m256i ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
_mm256_storeu_si256((__m256i*)(seg[0]+i),_mm256_add_epi64(ab,cd));_mm256_storeu_si256((__m256i*)(seg[1]+i),_mm256_add_epi64(ad,dd));
_mm256_storeu_si256((__m256i*)(seg[2]+i),_mm256_sub_epi64(ab,cd));_mm256_storeu_si256((__m256i*)(seg[3]+i),_mm256_sub_epi64(ad,dd));
}
}
template<unsigned N,unsigned H> inline void form4(const u32*a,u64*const v[4]){
constexpr size_t M=size_t(1)<<(32-__builtin_clz(N-1)),S=M/32;
for(size_t j=0;j<S;j+=4){
__m256i z0=_mm256_setzero_si256(),z1=z0,z2=z0,z3=z0;
#pragma GCC unroll 8
for(unsigned t=0;t<8;++t){
__m256i x[4];
#pragma GCC unroll 4
for(unsigned u=0;u<4;++u){size_t pos=(4*t+u)*S+j;
if(pos+4<=N)x[u]=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(a+pos)));
else if(pos>=N)x[u]=_mm256_setzero_si256();
else{u32 tail[4]={};for(unsigned l=0;l<4&&pos+l<N;++l)tail[l]=a[pos+l];x[u]=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)tail));}
}
__m256i p=_mm256_add_epi64(x[0],x[1]),q=_mm256_sub_epi64(x[0],x[1]),r=_mm256_add_epi64(x[2],x[3]),s=_mm256_sub_epi64(x[2],x[3]);
__m256i y0=_mm256_add_epi64(p,r),y1=_mm256_add_epi64(q,s),y2=_mm256_sub_epi64(p,r),y3=_mm256_sub_epi64(q,s);
if(__builtin_parity(H&t)){z0=_mm256_sub_epi64(z0,y0);z1=_mm256_sub_epi64(z1,y1);z2=_mm256_sub_epi64(z2,y2);z3=_mm256_sub_epi64(z3,y3);}
else{z0=_mm256_add_epi64(z0,y0);z1=_mm256_add_epi64(z1,y1);z2=_mm256_add_epi64(z2,y2);z3=_mm256_add_epi64(z3,y3);}
}
_mm256_storeu_si256((__m256i*)(v[0]+j),z0);_mm256_storeu_si256((__m256i*)(v[1]+j),z1);_mm256_storeu_si256((__m256i*)(v[2]+j),z2);_mm256_storeu_si256((__m256i*)(v[3]+j),z3);
}
}
template<unsigned N,unsigned H> inline void process4(const u32*a,u64*const seg[4],u64*const v[4]){
constexpr size_t M=size_t(1)<<(32-__builtin_clz(N-1)),S=M/32,Q=M/4;
form4<N,H>(a,v);
for(unsigned r=0;r<4;++r){fwht64(v[r],S);const size_t off=(4*H+r)*S;u64*t=seg[off/Q]+off%Q;
for(size_t j=0;j<S;j+=4)_mm256_storeu_si256((__m256i*)(t+j),mul64(_mm256_loadu_si256((const __m256i*)(t+j)),_mm256_loadu_si256((const __m256i*)(v[r]+j))));
}
}
template<unsigned N> inline void xor_stream(const unsigned*a,const unsigned*b,unsigned*c){
constexpr size_t M=size_t(1)<<(32-__builtin_clz(N-1)),Q=M/4,S=M/32;constexpr unsigned K=32-__builtin_clz(N-1);
static_assert(size_t(N)*4>=Q*8+3*S*8,"OB must accommodate first quarter and three scratch blocks");
u64*heap=(u64*)std::malloc((3*Q+S)*8);if(!heap)__builtin_trap();
u64*seg[4]={(u64*)c,heap,heap+Q,heap+2*Q};
u64*v[4]={(u64*)c+Q,(u64*)c+Q+S,(u64*)c+Q+2*S,heap+3*Q};
for(unsigned s=0;s<4;++s)for(size_t j=0;j<Q;++j){size_t i=s*Q+j;seg[s][j]=i<N?b[i]:0;}
quarter_fwht(seg,Q);
process4<N,0>(a,seg,v);process4<N,1>(a,seg,v);process4<N,2>(a,seg,v);process4<N,3>(a,seg,v);
process4<N,4>(a,seg,v);process4<N,5>(a,seg,v);process4<N,6>(a,seg,v);process4<N,7>(a,seg,v);
quarter_fwht(seg,Q);
for(size_t i=0;i<N;++i)c[i]=u32(seg[i/Q][i%Q]>>K);
std::free(heap);
}
}
void convolution(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){bitconv::solve32<false>(n,a,b,c);}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 6.847 ms | 7 MB + 656 KB | Accepted | Score: 100 | 显示更多 |