提交记录 162430


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_codex_maker convmode5. 测测你的mod卷积-1e5 Accepted 100 366.982 ms 400 KB C++17 2.69 KB
提交时间 评测时间
2026-11-17 01:01:28 2026-11-17 02:33:34
// 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);}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1366.982 ms400 KBAcceptedScore: 100


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