AmbiguousExpr

クラス · 曖昧式の全順序評価 (AmbiguousExpr)

template <class T = long long>
struct AmbiguousExpr;

概要

曖昧な二項演算式の「全評価順序で得られる値の集合」

すべての演算子は二項で、任意の結合順序 (全 parenthesization) を許す。 入力中の括弧 () は固定のグループ化として扱い、その内側も再帰的に 全順序を試す。op(c, f) で演算子を登録する。f は無効な演算 （$0$ 除算など）に対し std::nullopt を返すとその経路を捨てる。 値の集合を返すので、size() で「あり得る結果の通り数」が得られる (AOJ 2255 など)。オペランド数を $k$ とすると区間 DP で $O(k^2)$ 個の部分区間 $\times$ 集合サイズの二乗で評価する。

計算量

• オペランド数を $k$、各区間の値集合の最大サイズを $S$ として $O(k^3S^2\log S)$

メンバ関数

メンバ型