// Pure reference solution: no input generator, seed, hash or judge ABI.
#include <algorithm>
#include <cstdint>
#include <cstring>
#include <vector>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
namespace root_conv {using u32=uint32_t;using u64=uint64_t;
inline void positive_quotient(unsigned n,const unsigned* __restrict a,const unsigned* __restrict b,unsigned* __restrict c){
std::memset(c,0,size_t(n)*4);
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;}
for(;j+3<=last;j+=4,k+=4*i){
u32 x0=a[k],x1=a[k+i],x2=a[k+2*i],x3=a[k+3*i];
sum+=x0*b[j]+x1*b[j+1]+x2*b[j+2]+x3*b[j+3];
c[j]+=x0*bi;c[j+1]+=x1*bi;c[j+2]+=x2*bi;c[j+3]+=x3*bi;
}
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];}
positive_quotient(n,prefix.data(),b,c);
// D[k]=sum_{j>0} b[j]*prefix[min(k*j,n)], c[k]=D[k+1]-D[k].
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;
}
}
void convolution(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){root_conv::floor_conv(n,a,b,c);}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 13.191 ms | 7 MB + 664 KB | Accepted | Score: 100 | 显示更多 |