# physics0523's Hard Work #4 halc視点

未履修が最終問題しかなかった。

## [Two Histograms](https://atcoder.jp/contests/agc035/tasks/agc035_f)

<details>
<summary>ネタバレ防止用</summary>
はじめに、うまくいかなかった考察を供養しておく。

* $0$ と $0$ の位置によって新たな $0$ が、$2$ と $2$ の位置によって新たな $2$ が決まる。また、$2$ の前に $0$ があってはいけないことがわかる。このように自明な条件をすべて満たしたものが実はすべて条件を満たすのではないか？
* 大嘘。$N=3,M=3$ で、$((0,1,0),(1,1,1),(0,1,0))$ には自明に不可能な場所はないが実現不可。
* $0$ や $2$ を置くと、いくつかの部分について候補が削れ、さらにそこを決めるとさらに候補が削れ…、のようなことができるが、これをDP的に高速化できないか？
* まとめられる状態が見つからなかった。

結局、以下に気付いて実験できるかがすべてだと思う。

* $2$ つのヒストグラムのうち、ある一方からもう一方に自明に移せるパターンをすべて排除すると、それらから得られるグリッドはすべて違うのではないか？

この予想を試してみると、正しそうなことがわかるので信じて実装する。

いくらかの組み合わせ的解釈により、

$$f(p)=[x^p]\left(\sum_{k=0}^{N}\frac{(N+1-k)x^k}{k!}\right)^M$$

とすると、答えは

$$\sum_{k=1}^{N}\frac{f(k)N!}{(N-k)!}$$

となる。

これは、多項式のpowの計算がボトルネックとなって $O(N\log N)$ である。

私は多項式ライブラリを持っていなかったので、Library Checkerで[vwxyzさんのpow](https://judge.yosupo.jp/submission/136499)を窃盗した。

</details>