k値数列の転倒数

2019/04/20 実装の誤りなどを修正しました。

概要

qiita.com こちらの記事を読んで2値だけでなく一般のk値について拡張できそうだと思ったので、それと結合則の証明を書きます。

k値転倒数が成す群の演算

一般性を失わず [0, k) の値を取るとします。
すると台集合の型は (array<int, k> x, int z) となります。
x_s[i] := s 内に含まれる i の個数
z_s := s の転倒数
です。
また、演算は以下のようになります

xs+t[i] = xs[i] + xt[i] 

zs+t = zs + zt + Σ[i∈[0, k)](Σ[j∈[0, i)](xs[i] * xt[j]))

これは i>j なる (i, j) について s 内の i と t 内の j を swap する必要があることから示すことが出来ます。
転倒数と考えれば結合則は明らかですが、後述する逆元で負になったりするので式から示します。
xについては加法の結合則から明らかです。zについて、s+t+uを計算することを考えます。

zs+t+u = zs + zt + Σ[i∈[0, k)](Σ[j∈[0, i)](xs[i] * xt[j])) + zu

+ Σ[i∈[0, k)](Σ[j∈[0, i)]((xs[i] + xt[i]) * xu[j]))

分配法則で最後の項を展開し、項を並び替えます

zs+t+u = zs + zt + zu

+ Σ[i∈[0, k)](Σ[j∈[0, i)](xs[i] * xt[j]))

+ Σ[i∈[0, k)](Σ[j∈[0, i)](xs[i] * xu[j]))

+ Σ[i∈[0, k)](Σ[j∈[0, i)](xt[i] * xu[j]))

対称性があっていかにも結合則が成り立ちそうです。 省略しますが、t+uを先に計算しても同様の結果になることがわかります。

逆元

sの逆元-sを考えます。xについては

x-s[i] = -xs[i]

とすればよいです。zについては

xtemp[i] = -xs[i]

ztemp = 0

として、

z-s = -zx+temp

とすれば丁度打ち消してくれます。

計算量

ナイーブな計算では O(k²) となりますが、右側の項の累積和を取りながら計算することで O(k) となります。

実装

速度や使い勝手などは一切気にしていません

#include <array>

template <int K> class k_inv_num {
public:
  ::std::array<int, K> x;
  int z;

  k_inv_num() : x(), z(0) {}
  k_inv_num(int c) : x(), z(0) { x[c] = 1; }
};

template <int K>
k_inv_num<K> operator+(const k_inv_num<K> &s, const k_inv_num<K> &t) {
  k_inv_num<K> ret;
  for (int i = 0; i < K; ++i) {
    ret.x[i] = s.x[i] + t.x[i];
  }
  ret.z = s.z + t.z;
  int sum = 0;
  for (int i = 0; i < K; ++i) {
    ret.z += s.x[i] * sum;
    sum += t.x[i];
  }
  return ret;
}

template <int K> k_inv_num<K> operator-(const k_inv_num<K> &s) {
  k_inv_num<K> ret;
  for (int i = 0; i < K; ++i) {
    ret.x[i] = -s.x[i];
  }
  ret.z = -(ret + s).z;
  return ret;
}