提交记录 162386


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_codex_maker convdividee7. 测测你的除法卷积-1e7 Accepted 100 115.282 ms 39072 KB C++17 4.83 KB
提交时间 评测时间
2026-11-17 00:59:27 2026-11-17 02:33:11
// Begin public solver header: kernel.hpp
#include <algorithm>
#include <cstdint>
#include <cstring>
#include <vector>
#include <immintrin.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
namespace conv_arith {
using u32=uint32_t;using u64=uint64_t;
inline std::vector<u32> primes(unsigned n) {
 std::vector<unsigned char> composite((n+1)/2,0);std::vector<u32>p;
 if(n>2)p.push_back(2);
 for(unsigned k=3;u64(k)*k<n;k+=2)if(!composite[k/2])
  for(u64 j=u64(k)*k;j<n;j+=2*k)composite[j/2]=1;
 for(unsigned k=3;k<n;k+=2)if(!composite[k/2])p.push_back(k);
 return p;
}
inline void multiply(unsigned n,const unsigned*__restrict a,const unsigned*__restrict b,unsigned*__restrict c){
 std::memset(c,0,size_t(n)*4);if(!n)return;
 u32 sa=0,sb=0;for(unsigned i=0;i<n;++i){sa+=a[i];sb+=b[i];}
 c[0]=a[0]*sb+b[0]*sa-a[0]*b[0];
 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 first=std::max(i,(lo+i-1)/i),last=(hi-1)/i;
   const u32 ai=a[i],bi=b[i];unsigned j=first,k=i*j;
   if(j==i){c[k]+=ai*bi;++j;k+=i;}
   for(;j+3<=last;j+=4,k+=4*i){
    c[k]+=ai*b[j]+bi*a[j];c[k+i]+=ai*b[j+1]+bi*a[j+1];
    c[k+2*i]+=ai*b[j+2]+bi*a[j+2];c[k+3*i]+=ai*b[j+3]+bi*a[j+3];
   }
   for(;j<=last;++j,k+=i)c[k]+=ai*b[j]+bi*a[j];
  }
 }
}
inline void divide(unsigned n,const unsigned*__restrict a,const unsigned*__restrict b,unsigned*__restrict c){
 if(!n)return;std::memset(c,0,size_t(n)*4);u32 sb=0;for(unsigned j=1;j<n;++j)sb+=b[j];c[0]=a[0]*sb;
 // Transpose the blocked positive Dirichlet convolution: the product-index
 // window stays in cache, while each large quotient interval is contiguous.
 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 std::vector<int8_t> mobius(unsigned n){
 // Every composite below 1e8 has a least prime factor below 1e4.
 // Only odd least factors are stored, in 16 bits; this temporary is freed
 // before convolution scratch is allocated.
 std::vector<uint16_t>least((n+1)/2,0);std::vector<int8_t>mu(n,0);if(n>1)mu[1]=1;if(n>2)mu[2]=-1;
 for(unsigned p=3;u64(p)*p<n;p+=2)if(!least[p/2])for(unsigned j=p*p;j<n;j+=2*p)if(!least[j/2])least[j/2]=uint16_t(p);
 for(unsigned i=3;i<n;i+=2){unsigned p=least[i/2];int v=-1;if(p){unsigned q=i/p;v=(q==p||least[q/2]==p)?0:-mu[q];}mu[i]=int8_t(v);if(i<(n+1)/2)mu[2*i]=int8_t(-v);}
 return mu;
}
inline void gcd_conv(unsigned n,const unsigned*__restrict a,const unsigned*__restrict b,unsigned*__restrict c){
 if(!n)return;auto mu=mobius(n);std::vector<u32>f(n,0);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 sa=0,sb=0;
   if(j==i){sa+=a[k];sb+=b[k];++j;k+=i;}
   for(;j<=last;++j,k+=i){sa+=a[k];sb+=b[k];c[j]+=a[k];f[j]+=b[k];}c[i]+=sa;f[i]+=sb;
  }
 }
 for(unsigned i=1;i<n;++i)f[i]*=c[i];std::memset(c,0,size_t(n)*4);
 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;int mi=mu[i];
   if(j==i){sum+=u32(mi)*f[k];++j;k+=i;}
   for(;j<=last;++j,k+=i){u32 x=f[k];sum+=u32(mu[j])*x;c[j]+=u32(mi)*x;}c[i]+=sum;
  }
 }
 c[0]=a[0]*b[0];for(unsigned i=1;i<n;++i)c[i]+=a[0]*b[i]+b[0]*a[i];
}
inline void lcm_conv(unsigned n,const unsigned*__restrict a,const unsigned*__restrict b,unsigned*__restrict c){
 if(!n)return;auto mu=mobius(n);std::vector<u32>f(n,0);std::memset(c,0,size_t(n)*4);
 u32 sa=0,sb=0;for(unsigned i=0;i<n;++i){sa+=a[i];sb+=b[i];}
 constexpr unsigned block=32768;
 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 ai=a[i],bi=b[i];
   if(j==i){c[k]+=ai;f[k]+=bi;++j;k+=i;}
   for(;j<=last;++j,k+=i){c[k]+=ai+a[j];f[k]+=bi+b[j];}
  }
 }
 for(unsigned i=1;i<n;++i)f[i]*=c[i];std::memset(c,0,size_t(n)*4);
 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 fi=f[i];int mi=mu[i];
   if(j==i){c[k]+=u32(mi)*fi;++j;k+=i;}
   for(;j<=last;++j,k+=i)c[k]+=u32(mi)*f[j]+u32(mu[j])*fi;
  }
 }
 c[0]=a[0]*sb+b[0]*sa-a[0]*b[0];
}
}
// End public solver header: kernel.hpp
void convolution(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){conv_arith::divide(n,a,b,c);}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1115.282 ms38 MB + 160 KBAcceptedScore: 100


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