結果

問題 No.1901 bitwise xor convolution (characteristic 2)
ユーザー Taiki0715
提出日時 2026-04-10 22:23:35
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 225 ms / 4,000 ms
コード長 7,608 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,725 ms
コンパイル使用メモリ 230,860 KB
実行使用メモリ 54,656 KB
最終ジャッジ日時 2026-04-10 22:23:42
合計ジャッジ時間 6,625 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function 'mint mint::operator*(const mint&) const':
main.cpp:275:30: warning: narrowing conversion of '_mm_extract_epi64(m, 0)' from 'long long int' to 'mint::ull' {aka 'long long unsigned int'} [-Wnarrowing]
  275 |     return {_mm_extract_epi64(m,0)};
      |             ~~~~~~~~~~~~~~~~~^~~~~

ソースコード

diff #
raw source code 

#include<stdio.h>
#include<string.h>
#include<string>
#include<cstdlib>
#include<type_traits>
namespace fastio{
static constexpr u_int32_t buf_size=1<<17;
char ibuf[buf_size];
char obuf[buf_size];
u_int32_t pil=0,pir=0,por=0;
struct Pre{
  char t[40000];
  constexpr Pre(){
    for(int i=0;i<10000;i++){
      int n=i;
      for(int j=3;j>=0;j--){
        t[i*4+j]='0'+n%10;
        n/=10;
      }
    }
  }
}constexpr pre;
inline void load(){
  if(pir-pil<=pil)memcpy(ibuf,ibuf+pil,pir-pil);
  else memmove(ibuf,ibuf+pil,pir-pil);
  pir=pir-pil+fread(ibuf+pir-pil,1,buf_size-pir+pil,stdin);
  pil=0;
}
inline void flush(){
  fwrite(obuf,1,por,stdout);
  por=0;
}
inline void rd(char&c){c=ibuf[pil++];}
inline void rd(std::string&s){
  char c;
  s.clear();
  if(pil==pir)load();
  rd(c);
  if(pil==pir)load();
  while(!std::isspace(c)){
    s+=c;
    rd(c);
    if(pil==pir)load();
  }
}
inline void rd(__int128_t&x){
  if(pil+50>pir)load();
  char c;
  do rd(c); while(c<'-');
  bool neg=false;
  if(c=='-'){
    neg=true;
    rd(c);
  }
  x=0;
  while(c>='0'){
    x=x*10+(c&15);
    rd(c);
  }
  if(neg)x=-x;
}
template<typename T>
inline void rd(T&x){
  if(pil+32>pir)load();
  char c;
  do rd(c); while(c<'-');
  bool neg=false;
  if constexpr(std::is_signed_v<T>){
    if(c=='-'){
      neg=true;
      rd(c);
    }
  }
  x=0;
  while(c>='0'){
    x=x*10+(c&15);
    rd(c);
  }
  if constexpr(std::is_signed_v<T>){
    if(neg)x=-x;
  }
}
inline void wt(char x){obuf[por++]=x;}
template<typename T,std::enable_if_t<std::is_integral_v<T>,std::nullptr_t> =nullptr>
inline void wt(T x){
  if(por+32>buf_size)flush();
  if(x==0){
    wt('0');
    return;
  }
  if constexpr(std::is_signed_v<T>){
    if(x<0){
      wt('-');
      x=-x;
    }
  }
  if(x>=10000000000000000){
    u_int32_t r1=x%100000000;
    u_int64_t q1=x/100000000;
    u_int32_t r2=q1%100000000;
    u_int32_t q2=q1/100000000;
    u_int32_t n1=r1%10000,n2=r1/10000,n3=r2%10000,n4=r2/10000;
    if(x>=1000000000000000000){
      if constexpr(std::is_unsigned_v<T>){
        if(x>=10000000000000000000ull){
          obuf[por++]='1';
        }
      }
      memcpy(obuf+por,pre.t+(q2<<2)+1,3);
      memcpy(obuf+por+3,pre.t+(n4<<2),4);
      memcpy(obuf+por+7,pre.t+(n3<<2),4);
      memcpy(obuf+por+11,pre.t+(n2<<2),4);
      memcpy(obuf+por+15,pre.t+(n1<<2),4);
      por+=19;
    }
    else if(x>=100000000000000000){
      u_int32_t q3=(q2*205)>>11;
      u_int32_t r3=q2-q3*10;
      obuf[por]='0'+q3;
      obuf[por+1]='0'+r3;
      memcpy(obuf+por+2,pre.t+(n4<<2),4);
      memcpy(obuf+por+6,pre.t+(n3<<2),4);
      memcpy(obuf+por+10,pre.t+(n2<<2),4);
      memcpy(obuf+por+14,pre.t+(n1<<2),4);
      por+=18;
    }
    else{
      obuf[por]='0'+q2;
      memcpy(obuf+por+1,pre.t+(n4<<2),4);
      memcpy(obuf+por+5,pre.t+(n3<<2),4);
      memcpy(obuf+por+9,pre.t+(n2<<2),4);
      memcpy(obuf+por+13,pre.t+(n1<<2),4);
      por+=17;
    }
  }
  else{
    static char buf[12];
    int i=8;
    while(x>=10000){
      memcpy(buf+i,pre.t+((x%10000)<<2),4);
      x/=10000;
      i-=4;
    }
    if(x<100){
      if(x<10)obuf[por++]='0'+x;
      else{
        obuf[por]='0'+x/10;
        obuf[por+1]='0'+x%10;
        por+=2;
      }
    }
    else{
      if(x<1000){
        memcpy(obuf+por,pre.t+(x<<2)+1,3);
        por+=3;
      }
      else{
        memcpy(obuf+por,pre.t+(x<<2),4);
        por+=4;
      }
    }
    memcpy(obuf+por,buf+i+4,8-i);
    por+=8-i;
  }
}
inline void wt(const std::string&s){
  int sz=s.size();
  if(por+sz>buf_size)flush();
  memcpy(obuf+por,s.c_str(),sz);
  por+=sz;
}
inline void wt(__int128_t x){
  if(por+50>buf_size)flush();
  if(x==0){
    wt('0');
    return;
  }
  if(x<0){
    wt('-');
    x=-x;
  }
  static constexpr __int128_t b=10000000000000000000ull;
  if(x>=b){
    wt<unsigned long long>(x/b);
    unsigned long long y=x%b;
    memcpy(obuf+por,pre.t+((y/10000000000000000)<<2)+1,3);
    memcpy(obuf+por+3,pre.t+((y/1000000000000%10000)<<2),4);
    memcpy(obuf+por+7,pre.t+((y/100000000%10000)<<2),4);
    memcpy(obuf+por+11,pre.t+((y/10000%10000)<<2),4);
    memcpy(obuf+por+15,pre.t+((y%10000)<<2),4);
    por+=19;
  }
  else wt<unsigned long long>(x);
}
struct Dummy{
  Dummy(){std::atexit(flush);}
}dummy;
}
using fastio::rd;
using fastio::wt;
#include<vector>
#include<cassert>
#include<limits>
#include<concepts>
template<typename T>
constexpr std::enable_if_t<std::numeric_limits<T>::digits<=32,int>msb(T n){return n==0?-1:31-__builtin_clz(n);}
template<typename T>
constexpr std::enable_if_t<(std::numeric_limits<T>::digits>32),int>msb(T n){return n==0?-1:63-__builtin_clzll(n);}

template<typename T>
constexpr std::enable_if_t<std::numeric_limits<T>::digits<=32,int>lsb(T n){return n==0?-1:__builtin_ctz(n);}
template<typename T>
constexpr std::enable_if_t<(std::numeric_limits<T>::digits>32),int>lsb(T n){return n==0?-1:__builtin_ctzll(n);}

template<typename T>
constexpr std::enable_if_t<std::is_integral_v<T>,T>floor_pow2(T n){return n==0?0:T(1)<<msb(n);}

template<typename T>
constexpr std::enable_if_t<std::is_integral_v<T>,T>ceil_pow2(T n){return n<=1?1:T(1)<<(msb(n-1)+1);}

template<std::integral T>
constexpr T safe_div(T a,T b){return a/b-(a%b&&(a^b)<0);}
template<std::integral T>
constexpr T safe_ceil(T a,T b){return a/b+(a%b&&(a^b)>0);}
template<typename T>
std::vector<T>arbitrary_xor_convolution(std::vector<T>f,std::vector<T>g){
  assert(f.size()==g.size());
  int n=f.size();
  int lg=msb(n);
  assert(1<<lg==n);
  for(int i=0;i<lg;i++)for(int j=0;j<n;j++)if(j>>i&1){
    f[j^(1<<i)]=f[j^(1<<i)]-f[j];
    g[j^(1<<i)]=g[j^(1<<i)]-g[j];
  }
  std::vector<std::vector<T>>a(n,std::vector<T>(lg+1)),b(n,std::vector<T>(lg+1));
  for(int i=0;i<n;i++){
    a[i][std::popcount<unsigned>(i)]=f[i];
    b[i][std::popcount<unsigned>(i)]=g[i];
  }
  for(int i=0;i<lg;i++)for(int j=0;j<n;j++)if(j>>i&1){
    for(int k=0;k<=lg;k++){
      a[j][k]=a[j][k]+a[j^(1<<i)][k];
      b[j][k]=b[j][k]+b[j^(1<<i)][k];
    }
  }
  std::vector<T>h(lg*2+1);
  for(int i=0;i<n;i++){
    std::fill(h.begin(),h.end(),T());
    for(int j=0;j<=lg;j++)for(int k=0;k<=lg;k++)h[j+k]=h[j+k]+a[i][j]*b[i][k];
    for(int j=lg*2-1;j>=0;j--)h[j]=h[j]+h[j+1]+h[j+1];
    std::copy(h.begin(),h.begin()+lg+1,a[i].begin());
  }
  for(int i=0;i<lg;i++)for(int j=0;j<n;j++)if(j>>i&1){
    for(int k=0;k<=lg;k++){
      a[j][k]=a[j][k]-a[j^(1<<i)][k];
    }
  }
  for(int i=0;i<n;i++)f[i]=a[i][std::popcount<unsigned>(i)];
  for(int i=0;i<lg;i++)for(int j=0;j<n;j++)if(j>>i&1)f[j^(1<<i)]=f[j^(1<<i)]+f[j];
  return f;
}
#include<immintrin.h>
struct mint{
  using ull=unsigned long long;
  ull x;
  mint operator+(const mint&rhs)const{
    return {x^rhs.x};
  }
  mint operator-(const mint&rhs)const{
    return {x^rhs.x};
  }
  __attribute__((target("pclmul,sse4.2")))
  mint operator*(const mint&rhs)const{
    __m128i m=_mm_clmulepi64_si128(_mm_set_epi64x(0,x),_mm_set_epi64x(0,rhs.x),0);
    return {_mm_extract_epi64(m,0)};
  }
};
int main(){
  int n;
  rd(n);
  std::vector<mint>a(1<<n),b(1<<n);
  char c;
  for(int i=0;i<(1<<n);i++){
    for(int j=0;j<32;j++){
      rd(c);
      if(c=='1')a[i].x|=1ull<<j;
      rd(c);
    }
    if(fastio::pil+100>fastio::pir)fastio::load();
  }
  for(int i=0;i<(1<<n);i++){
    for(int j=0;j<32;j++){
      rd(c);
      if(c=='1')b[i].x|=1ull<<j;
      rd(c);
    }
    if(fastio::pil+100>fastio::pir)fastio::load();
  }
  a=arbitrary_xor_convolution(a,b);
  for(int i=0;i<(1<<n);i++){
    for(int j=0;j<63;j++){
      if(a[i].x>>j&1)wt('1');
      else wt('0');
      wt(" \n"[j+1==63]);
    }
    if(fastio::por+130>fastio::buf_size)fastio::flush();
  }
}
0