// Pure reference, no production input, generator, seed, digest or judge ABI.
#include <cstdint>
#include <cstring>
#include <algorithm>
#include <immintrin.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
namespace mod_blocked {
using u32=uint32_t;using u64=uint64_t;
template<unsigned QBegin=1> inline void solve(unsigned n,const unsigned* __restrict a,const unsigned* __restrict b,unsigned* __restrict c){
u32 suffix=0;for(unsigned k=n;k--;){c[k]=a[k]*suffix;suffix+=b[k];}
if(n<64){for(unsigned j=1;j<n;++j)for(unsigned i=QBegin*j;i<n;++i)c[i%j]+=a[i]*b[j];return;}
constexpr unsigned J=64,T=32;
for(unsigned j=1;j<n&&j<=J;++j){const __m256i bj=_mm256_set1_epi32(b[j]);for(unsigned start=QBegin*j;start<n;start+=j){unsigned cnt=std::min(j,n-start),k=0;for(;k+8<=cnt;k+=8){__m256i v=_mm256_loadu_si256((const __m256i*)(c+k)),x=_mm256_loadu_si256((const __m256i*)(a+start+k));_mm256_storeu_si256((__m256i*)(c+k),_mm256_add_epi32(v,_mm256_mullo_epi32(x,bj)));}for(;k<cnt;++k)c[k]+=a[start+k]*b[j];}}
for(unsigned k0=0;2*k0<n;k0+=T){const unsigned count=std::min(T,n-k0);__m256i z[4];for(unsigned r=0;r<4;++r)z[r]=_mm256_loadu_si256((const __m256i*)(c+k0+8*r));
const unsigned first=std::max(J+1,k0+1),end_full=std::max(J+1,k0+T);unsigned qmax=(n-1-k0)/first;
for(unsigned q=QBegin;q<=qmax;++q){unsigned last=(n-1-k0)/q,full_last=n>=k0+T?(n-k0-T)/q:0;unsigned j=first;
for(;j<=last&&j<end_full;++j){__m256i bj=_mm256_set1_epi32(b[j]);const unsigned start=q*j+k0;
for(unsigned r=0;r<4;++r){const __m256i idx=_mm256_setr_epi32(k0+8*r,k0+8*r+1,k0+8*r+2,k0+8*r+3,k0+8*r+4,k0+8*r+5,k0+8*r+6,k0+8*r+7);__m256i mask=_mm256_and_si256(_mm256_cmpgt_epi32(_mm256_set1_epi32(j),idx),_mm256_cmpgt_epi32(_mm256_set1_epi32(n-q*j),idx));__m256i x=_mm256_maskload_epi32((const int*)(a+start+8*r),mask);z[r]=_mm256_add_epi32(z[r],_mm256_mullo_epi32(x,bj));}
}
for(;j<=full_last;++j){__m256i bj=_mm256_set1_epi32(b[j]);const unsigned*x=a+q*j+k0;
for(unsigned r=0;r<4;++r)z[r]=_mm256_add_epi32(z[r],_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x+8*r)),bj));
}
for(;j<=last;++j){__m256i bj=_mm256_set1_epi32(b[j]);const unsigned start=q*j+k0;
for(unsigned r=0;r<4;++r){const __m256i idx=_mm256_setr_epi32(k0+8*r,k0+8*r+1,k0+8*r+2,k0+8*r+3,k0+8*r+4,k0+8*r+5,k0+8*r+6,k0+8*r+7);__m256i mask=_mm256_and_si256(_mm256_cmpgt_epi32(_mm256_set1_epi32(j),idx),_mm256_cmpgt_epi32(_mm256_set1_epi32(n-q*j),idx));__m256i x=_mm256_maskload_epi32((const int*)(a+start+8*r),mask);z[r]=_mm256_add_epi32(z[r],_mm256_mullo_epi32(x,bj));}
}
}
for(unsigned r=0;r<4;++r)_mm256_storeu_si256((__m256i*)(c+k0+8*r),z[r]);
}
}
}
void convolution(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){mod_blocked::solve(n,a,b,c);}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 366.982 ms | 400 KB | Accepted | Score: 100 | 显示更多 |