AtCoder「高橋くんとカード」を分割統治法で解いた

前置き

ABC044 C（またはARC060 A）「高橋くんとカード」を分割統治法で解いてACしたのですが、解説の想定解はDPでした。

多分計算量も変わらないのですが、適当にググって出てくる記事を上から見ても私と同じ解法が見当たらなかったので記事にします（初めての競プロ記事です）。

atcoder.jp

公式解説はこちらです。 https://img.atcoder.jp/data/arc/060/editorial.pdf

解法

想定解は2つあってどちらもDPをしていますが、私は以下のように分割統治法で解きました。

まずは想定解2つ目と同様に、各 $x_i$ から $A$ を引いておきます。

ここで、 $l \lt r$ として $x_l, \cdots, x_{r-1}$ から1枚以上選んだ合計をすべて列挙した重複あり集合を $B_{l, r}$ とします。

例えば $-1, 0, 2$ に対する $B_{1, 4}$ は、 $-1, 0, 2, -1 + 0, -1 + 2, 0 + 2, -1 + 0 + 2$ となります。

$l \lt m \lt r$ として $B_{l, m}$ と $B_{m, r}$ が分かっているとすると、 $B_{l, r}$ は以下の3つを統合したものとなります。

$B_{l, m}$ （ $x_m, \cdots, x_{r - 1}$ を使わない場合）
$B_{m, r}$ （ $x_l, \cdots, x_{m - 1}$ を使わない場合）
$B_{l, m}$ のそれぞれと $B_{m, r}$ のそれぞれを足し合わせた $|B_{l, m}| \cdot |B_{m, r}|$ 個の集合（両方の範囲から使う場合）

$B_{1, N + 1}$ を二等分しながら再帰的に解くと、そこに含まれる $0$ の個数が答えになります。

実装ではunordered_mapを使って各合計値の個数をまとめています（そうしないと全探索と同じになってしまう）。

個人的にはDPより直感的な気がします。

atcoder.jp

#include <bits/stdc++.h>
using namespace std;
using um = unordered_map<int, long long>;
#define each(i, a) for (auto &&i : (a))

int main() {
  int N, A;
  cin >> N >> A;
  vector<int> x(N);
  each(i, x) cin >> i;
  each(i, x) i -= A;
  function<um(int, int)> div_con = [&](int l, int r) {
    um ret;
    if (r - l == 1)
      ret[x[l]]++;
    else {
      int m = (l + r) / 2;
      um lm = div_con(l, m), rm = div_con(m, r);
      each(p, lm) ret[p.first] += p.second;
      each(p, rm) ret[p.first] += p.second;
      each(p, lm) each(q, rm) ret[p.first + q.first] += p.second * q.second;
    }
    return ret;
  };
  cout << div_con(0, N)[0] << endl;
}