TopCoder SRM 679 (Div. 1) Hard. BagAndCards

解法

a=count[i], b=count[j], G を good number 全体を表す集合としたとき、ans[i][j] は次の値になる。

$$ a_0 \sum_{0 + j \in G} b_j + a_1 \sum_{1 + j \in G} b_j + \cdots +a_{m - 1} \sum_{m - 1 + j \in G} b_j $$

これはあらかじめ $ \sum_{i + j \in G} b_j $ の値を求めておけば O(m) で計算できる。

全体としては O(n² m) で TL が 8 sec なので余裕。

---

畳み込みを用いても計算できる。剰余環上での畳み込みは NTT を用いて O(m log m) でできるが、定数が重いのでおそらく間に合わない。

TopCoder SRM 679 (Div. 1) Hard. BagAndCards

これが想定解だったとしたら流石に Easy。 本番は Greed で自動生成されたサンプルケースがバグってるのに気づかなくて、無限に時間が吸い取られてしまった。 もう怖くて Greed 使えない。