提交记录 162393


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_codex_maker convdivideie6. 测测你的整除卷积-1e6 Accepted 100 13.191 ms 7832 KB C++17 1.59 KB
提交时间 评测时间
2026-11-17 00:59:45 2026-11-17 02:33:17
// 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);}

CompilationN/AN/ACompile OKScore: N/A

Testcase #113.191 ms7 MB + 664 KBAcceptedScore: 100


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