Loading [Contrib]/a11y/accessibility-menu.js
$\newcommand{\O}{\mathrm{O}}$ My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

Fast Walsh Hadamard Transform

コードについての説明

高速 Walsh-Hadamrd 変換. 高速フーリエ変換の亜種で FFT が $c[k] = \underset{i+j=k}{\mathrm{sum}} a[i] \times b[j]$ を満たす $c$ を求めるのに対し, $c[k] = \underset{i \oplus j=k}{\mathrm{sum}} a[i] \times b[j]$ を満たす $c$ を求めるアルゴリズム(xor-convolution).
xor 以外にも係数行列を少し変えれば and, or についても求めることが可能である.

時間計算量: $\O (n \log n)$

コード

  1. #define MOD 1000000007
  2.  
  3. inline int add(int x, int y)
  4. {
  5.     return (x + y)%MOD;
  6. }
  7.  
  8. inline int sub(int x, int y)
  9. {
  10.     return (x+MOD-y)%MOD;
  11. }
  12.  
  13. inline int mul(int x, int y)
  14. {
  15.     return (long long)x*y%MOD;
  16. }
  17.  
  18. inline int mod_pow(int a, int b)
  19. {
  20.     int res = 1;
  21.     while(b){
  22.         if(b & 1){
  23.             res = mul(res, a);
  24.         }
  25.         a = mul(a, a);
  26.         b >>= 1;
  27.     }
  28.     return res;
  29. }
  30.  
  31. // xor convolution
  32. void fwht(vector<int>& poly, bool rev=false){
  33.     int n = (int)poly.size();
  34.     for(int i = 1; i < n; i *= 2){
  35.         for(int j = 0; j < i; j++){
  36.             for(int k = 0; k < n; k += i*2){
  37.                 int u = poly[j+k], v = poly[j+k+i];
  38.                 poly[j+k] = add(u, v);
  39.                 poly[j+k+i] = sub(u, v);
  40.             }
  41.         }
  42.     }
  43.     if(rev){
  44.         int inv = mod_pow(n, MOD-2);
  45.         for(int i = 0; i < n; i++){
  46.             poly[i] = mul(poly[i], inv);
  47.         }
  48.     }
  49. }
  50.  
  51. // or convolution
  52. // void fwht(vector<int>& poly, bool rev=false){
  53. //     int n = (int)poly.size();
  54. //     for(int i = 1; i < n; i *= 2){
  55. //         for(int j = 0; j < i; j++){
  56. //             for(int k = 0; k < n; k += i*2){
  57. //                 if(rev){
  58. //                     poly[j+k+i] = sub(poly[j+k+i], poly[j+k]);
  59. //                 }else{
  60. //                     poly[j+k+i] = add(poly[j+k+i], poly[j+k]);
  61. //                 }
  62. //             }
  63. //         }
  64. //     }
  65. // }
  66.  
  67. // and convolution
  68. // void fwht(vector<int>& poly, bool rev=false){
  69. //     int n = (int)poly.size();
  70. //     for(int i = 1; i < n; i *= 2){
  71. //         for(int j = 0; j < i; j++){
  72. //             for(int k = 0; k < n; k += i*2){
  73. //                 int u = poly[j+k], v = poly[j+k+i];
  74. //                 if(rev){
  75. //                     poly[j+k] = sub(v, u);
  76. //                     poly[j+k+i] = u;
  77. //                 }else{
  78. //                     poly[j+k] = v;
  79. //                     poly[j+k+i] = add(u, v);
  80. //                 }
  81. //             }
  82. //         }
  83. //     }
  84. // }
  85.  
  86. vector<int> mul(vector<int> a, vector<int> b){
  87.     int sm = (int)a.size() + (int)b.size() - 1, size_ = 1;
  88.     while(size_ < sm) size_ *= 2;
  89.     a.resize(size_, 0), b.resize(size_, 0);
  90.     fwht(a), fwht(b);
  91.     for(int i = 0; i < size_; i++){
  92.         a[i] = mul(a[i], b[i]);
  93.     }
  94.     fwht(a, true);
  95.     a.resize(sm);
  96.     return a;
  97. }

verify 用の問題

yosupo さんの library checker : Bitwise Xor Convolution 提出コード (xor convolution の verify)
yosupo さんの library checker : Bitwise And Convolution 提出コード (and convolution の verify)