前書き
想定解法より計算量が良かったというのと、$m\leq 10 ^ {18}$ とかでも解けたので。
問題
解法
(前半パートはかなり雑なので、公式解説を併せて読むことを推奨します)
作る列 $a$ に $A_{i,j}$ が含まれる場合を考える。このとき、$a$ において $A _ { i , j }$ の次は $A _ { i , j + 1}$ が置かれていなければ条件に反する。同様に、$a$ において $A _ { i , j }$ の前は $A _ { i , j - 1 }$ が置かれていなければ条件に反する。
そこで、「$x$ の後は $y$ が置かれていなければならず、また $y$ の前は必ず $x$ が置かれていなければならない」のような条件に対して $(x,y)$ の有向辺を張った有向グラフ $D$ を構築する。
まず、$D$ の連結成分であって、連結成分全体が有向パスでないものに含まれる頂点は $a$ に置くことが出来ない。これは、入次数または出次数が $2$ 以上の頂点が存在する場合はその頂点で必ず条件に反し、有向サイクルであるような場合は $a$ の長さが有限とはならないことから分かる。
$D$ の連結成分であって、連結成分全体が有向パスであるようなものに関しては、パスに現れる順番に $a$ に置けば条件に反しない。
以上より、$D$ の連結成分であって、連結成分全体が有向パスであるようなものを $P _ 1,\ldots, P _ t$ とすれば、$\displaystyle \sum_{i=1}^{a} |P _ {b _ i}| = m\;(1\leq b_i \leq t)$ を満たす列 $b$ を数え上げる問題となる。
更に言い換えると、これは $C _ i := \# \{ j \mid | P _ j | = i \}$ の母関数 $\displaystyle f(x) = \sum _ {i = 0} ^ \infty C _ i \cdot x _ i$ に対して $\displaystyle [ x ^ m ] \sum _ {i = 0} ^ \infty f(x) ^ i = [ x ^ m ] \dfrac{1}{1 - f(x)}$ を求める問題となる。ここで、$C _ 0 = 0$ であるから $\dfrac{1}{1 - f(x)}$ は問題なく定義される。
$\dfrac{1}{1 - f(x)} \bmod x ^ {m + 1}$ は $O(m \log m)$ で計算できるので、この問題を $O(n + k + \sum c _ i + m \log m)$ で解くことが出来た。
本問では $m\leq 3\times 10 ^ 5$ なのでこれで十分であるが、求めたいものは $\dfrac{1}{1 - f(x)}$ の $m $ 次の項の係数のみであるから、Bostan Mori のアルゴリズムを用いれば $O(n + k + \sum c _ i + k \log k \log m)$ で解くことも可能である。
