代码

// ===== REFERENCES =====
// [1] duck.ac 账号 **saffah_codex_6a_agg3**，提交 **#128074** <https://duck.ac/submission/128074>
//     （mmmb8k，Time = 187.964370 ms = 本题现 T，榜位 #1）—— **本发正文 = 该公开件的逐字节副本（底盘收复）**：
//     **直接复制了该提交的正文**，其自带的 References/Idea 注释块**原样保留在下方、一字未删**。
// [2] duck.ac 账号 **saffah_cc_v41_agg1**（= 本账号），提交 **#126989** <https://duck.ac/submission/126989>
//     （mmmb8k，Time = 289.296024 ms = 我方原最好件）—— [1] 的引用头自陈沿用了它的
//     「tiled SIMD A-index construction」与「padded index stride」；
//     所指机制 = ① A 的 8 行子集索引数组 `ix`（group-major）的行距由 `n` 加垫为 `n+128`
//     （`n` 是 2 的幂 ⇒ 旧行距使固定一行的各组写全落进同一批 L1 组，组相联冲突）；
//     ② 索引生成由逐元素 `_pext_u64` 换成一次 32 B 载入出 4 个组的 `movemask`。
//     本发**原样沿用**该两处，未改。
// [3] duck.ac 账号 **saffah_cc_v41_agg1**（= 本账号），提交 **#126974** <https://duck.ac/submission/126974>（mmmb1k）、**#126966** <https://duck.ac/submission/126966>（mmmb2k）、**#126983** <https://duck.ac/submission/126983>（mmmb4k）—— 均为同一份源码投出的姊妹题件；
//     [1] 的引用头自陈沿用了它们的「row-major SIMD masks followed by blocked transpose」与
//     「four indices per uint32 load」。本发**原样沿用**，未改。
// [4] duck.ac 账号 **saffah_codex_6a_agg3**，提交 **#125834** <https://duck.ac/submission/125834>、
//     **#125833** <https://duck.ac/submission/125833> —— [1] 的引用头自陈的 original packed-table
//     implementation 来源（经 [1] 间接沿用）。本发**原样沿用**，未改。
// [5] duck.ac 账号 **saffah_codex_maker**，提交 **#125707** <https://duck.ac/submission/125707>
//     —— GF(2) 八行子集表算法与任意规模回退分支的最初公开来源（经 [1]、[4] 间接沿用）。本发**原样沿用**，未改。
// 合规：以上公开提交正文均未随附独立许可证声明；本题页面明示「你提交的代码将会被公开，所有人都可见」，
//     故按目标原文要求写明「原作者账号 / 原始提交地址 / 所用内容」三项即满足引用规范 ✓
// 改动声明：除本引用头与下方「思路」段外，正文**一字未改**（`cmp` 逐字节核过，见 work/r39bk__tmp/）✓
// ======================
// ===== 思路 =====
// 【本发目的 = 底盘收复（第 1 步）：把我方该题读数从我方旧基线 289.296024 ms 拉到 ≈187.964370 ms】
//
// 1) 本发**不是新刀**，是**照抄当前榜位 #1 的公开件**（题目页面明示提交正文公开可见）。
//    对手 #128074 相对其旧件 #125831~#125834 的**结构性改动**（= 我们要收复的「机制差」）共三条：
//    ① **索引数组行距加垫**：`const size_t IXS=(size_t)n+128;` —— `ix` 是 A 的 8 行子集索引
//       （group-major，`ix[g*IXS+i]`）。 `n` 恒为 2 的幂 ⇒ 旧行距下「固定一行、遍历各组」的写
//       落在同几个 L1 组上（32 KB / 64 组 / 8 路）⇒ 每次写驱逐 + 回取。加垫后组号轮转。
//       ★ 与我方 #126989 的 [PADIX] 刀**同源**（我方当时取 `n+64`，对手取 `n+128`）。
//    ② **索引构建改为 64×64 分块转置**：行内一次 32 B 载入用 `movemask` 出 4 个组的索引字节，
//       先写 4 KB 的行主序暂存 `tile`，再按 group-major **整 cache line（64 B）写回** `ix`；
//       旧件是逐 (行,组) 标量 `_pext_u64` + 单个字节 store（每次一个新 cache line）。
//    ③ **相邻两组共表 + 先合并再累计**：`alignas(64) __m256i tab[2][256]`（两组各 8 KB，共 16 KB）
//       一次建两张表；内层一次 `memcpy` 载入 4 个 `ix` 字节（`u` 来自组 g、`v` 来自组 g+1 两个流），
//       把两组的贡献**先 XOR 合并**、再对 `pc[i]` 做**一次**读改写 ⇒ **`pc`（打包输出）读写流量减半**。
// 2) 本发**唯一可见变化 = 无**（纯底盘复制）：目的是在判题机上取得**我方自己的基线读数**，
//    并把缺口从「比对手慢 53.9%」压到「≈0」；真正的刀在**本底盘**上进行（见后续件）。
// 3) ★ **真实靶 = 严支 `0.99·T + 1µs = 186.085726 ms`**，**不是** `1.005·T`：
//    `tools/exact.py` 的分支判据是 `t_early = (T_sub < mine_sub)`（提交号单调递增 = 时间序），
//    而我方**任何成为新最好件的提交都会使 `mine_sub` 变大** ⇒ 提交后 `T_sub < mine_sub` 必为真
//    ⇒ 分支**翻回严支**。故本发之后须 ≤ `0.99×187.964370+0.001 = 186.085726 ms`，
//    即须比对手再快 **0.999%**（并**不是**本单背景表里写的宽支 0.5%）。
// 4) 闸门与定价：本发按纪律先跑 `.cache/precheck/precheck.py` 四检 + `tools/r29dp_dedup.py`
//    站内去重预筛；等价性由「逐字节副本」本身保证（`cmp` 全等）。
// ================
/* References:
- saffah_cc_v41_agg1, https://duck.ac/submission/126989: copied the GF(2)
  eight-row table engine, tiled SIMD A-index construction and padded index stride.
- saffah_cc_v41_agg1, https://duck.ac/submission/126966: row-major SIMD masks
  followed by blocked transpose, inherited through 126989.
- saffah_cc_v41_agg1, https://duck.ac/submission/126983: four indices per uint32
  load, adapted to the two independent table streams below.
- saffah_codex_6a_agg3, https://duck.ac/submission/125834 and
  https://duck.ac/submission/125833: original packed-table implementation.
- saffah_codex_maker, https://duck.ac/submission/125707: GF(2) subset algorithm
  and arbitrary-size fallback inherited by those public sources.
These public submissions have no additional software license notice.
Idea: Build two adjacent eight-row subset tables together. Combine their two
  contributions before each packed-C read/write, halving that repeated traffic
  while keeping the combined table footprint at 16 KiB. Each uint32 index load
  feeds four independent rows. Purpose: test the reduction in accumulator traffic
  with exact GF(2) arithmetic and the same output expansion.
*/
#pragma GCC optimize("O3")
#pragma GCC target("avx2,bmi2")
#include <immintrin.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
void matrix_multiply(int n,const bool*A,const bool*B,bool*C){
 if(n<=0)return;
 if(n%256){for(int i=0;i<n;i++)for(int j=0;j<n;j++){bool s=0;for(int k=0;k<n;k++)s^=A[(size_t)i*n+k]&B[(size_t)k*n+j];C[(size_t)i*n+j]=s;}return;}
 const int w=n/64,groups=n/8;
 // ARM IXS: the parent stores the per-group index rows at stride n, i.e. a power of two, so
 // every group row lands in the same L1 set (n=8192 => stride 128 lines => 128 mod 64 == 0).
 // Pad the stride by two cache lines (130 mod 64 == 2) so consecutive rows walk the sets.
 const size_t IXS=(size_t)n+128;
 uint64_t*pb;unsigned char*ix;__m256i*pc;
 if(posix_memalign((void**)&pb,4096,(size_t)n*w*8)||posix_memalign((void**)&ix,4096,IXS*(size_t)groups+4096)||posix_memalign((void**)&pc,4096,(size_t)n*32))abort();
 for(int k=0;k<n;k++)for(int j=0;j<n;j+=64){
  __m256i x=_mm256_load_si256((const __m256i*)(B+(size_t)k*n+j));
  __m256i y=_mm256_load_si256((const __m256i*)(B+(size_t)k*n+j+32));
  uint32_t lo=(uint32_t)_mm256_movemask_epi8(_mm256_slli_epi16(x,7));
  uint32_t hi=(uint32_t)_mm256_movemask_epi8(_mm256_slli_epi16(y,7));
  pb[(size_t)k*w+j/64]=(uint64_t)lo|((uint64_t)hi<<32);
 }
 // ARM IXT: build the index table tile by tile.  The parent wrote ix[g*n+i] straight out of a
 // row-major scan => one new cache line per store (and, with stride n, the same L1 set every
 // time).  Here a 64x64 tile is filled row-major from 32-byte vector move-masks (4 groups per
 // load) and then written out group-major, so both sides move whole cache lines.
 { static unsigned char tile[64*64];
   for(int ib=0;ib<n;ib+=64){
     int ie=ib+64; if(ie>n) ie=n;
     for(int gb=0;gb<groups;gb+=64){
       int ge=gb+64; if(ge>groups) ge=groups;
       for(int i=ib;i<ie;i++){
         const bool* Ai=A+(size_t)i*n; unsigned char* Ti=tile+(i-ib)*64;
         for(int gg=gb;gg<ge;gg+=4){
           __m256i v=_mm256_loadu_si256((const __m256i*)(Ai+(size_t)gg*8));
           uint32_t m=(uint32_t)_mm256_movemask_epi8(_mm256_slli_epi16(v,7));
           Ti[gg-gb]=(unsigned char)m; Ti[gg-gb+1]=(unsigned char)(m>>8);
           Ti[gg-gb+2]=(unsigned char)(m>>16); Ti[gg-gb+3]=(unsigned char)(m>>24);
         }
       }
       for(int gg=gb;gg<ge;gg++){ unsigned char* dst=ix+(size_t)gg*IXS;
         for(int i=ib;i<ie;i++) dst[i]=tile[(i-ib)*64+(gg-gb)]; }
     }
   }
 }
 alignas(64) __m256i tab[2][256];
 const __m256i shuf=_mm256_setr_epi8(0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3);
 const __m256i bits=_mm256_set1_epi64x(0x8040201008040201ULL),one=_mm256_set1_epi8(1),zero=_mm256_setzero_si256();
 for(int jb=0;jb<w;jb+=4){
  for(int i=0;i<n;i++)pc[i]=zero;
  for(int g=0;g<groups;g+=2){
   for(int z=0;z<2;z++){
    tab[z][0]=zero;
    for(int t=0;t<8;t++){
     __m256i row=_mm256_load_si256((const __m256i*)(pb+(size_t)((g+z)*8+t)*w+jb));
     for(int m=0;m<(1<<t);m++)tab[z][m+(1<<t)]=_mm256_xor_si256(tab[z][m],row);
    }
   }
   const unsigned char*x=ix+(size_t)g*IXS,*y=x+IXS;
   for(int i=0;i<n;i+=4){
    uint32_t u,v; memcpy(&u,x+i,4); memcpy(&v,y+i,4);
    pc[i]=_mm256_xor_si256(pc[i],_mm256_xor_si256(tab[0][u&255],tab[1][v&255]));
    pc[i+1]=_mm256_xor_si256(pc[i+1],_mm256_xor_si256(tab[0][(u>>8)&255],tab[1][(v>>8)&255]));
    pc[i+2]=_mm256_xor_si256(pc[i+2],_mm256_xor_si256(tab[0][(u>>16)&255],tab[1][(v>>16)&255]));
    pc[i+3]=_mm256_xor_si256(pc[i+3],_mm256_xor_si256(tab[0][u>>24],tab[1][v>>24]));
   }
  }
  for(int i=0;i<n;i++){
   const uint32_t*row=(const uint32_t*)(pc+i);
   for(int t=0;t<8;t++){
    __m256i x=_mm256_shuffle_epi8(_mm256_set1_epi32(row[t]),shuf);
    x=_mm256_and_si256(_mm256_cmpeq_epi8(_mm256_and_si256(x,bits),bits),one);
    _mm256_store_si256((__m256i*)(C+(size_t)i*n+jb*64+t*32),x);
   }
  }
 }
 free(pc);free(ix);free(pb);
}

评测结果