CODE FESTIVAL 2016 Grand Final(Parallel) J - 123 Pairs 解法

CODE FESTIVAL 2016 Grand Final(Parallel) J - 123 Pairs 解法
https://atcoder.jp/contests/cf16-exhibition-final-open/tasks/cf16_exhibition_final_j

問題

1から2NをN個のペアに分割したい。このとき、差が1のペアA個、差が2のペアB個、差が3のペアC個、N=A+B+Cを満たすものはいくつあるか？

解法

2種類のペアを並べたときに、隙間がなく、それ以上分割できない極小なものを列挙すると、

Pattern 1 : 差1のペア1個
Pattern 22-k : 差2のペア2個と、差3のペアk個 (k >= 0)
Pattern 31 : 差1を1個、差3を1個
Pattern 333 : 差3を3個

以上4通り。
Bが奇数の場合は差2が余るので解0。
Pattern 31をs個、Pattern 333をt個使うとすると、Pattern 1 は A-s個。Pattern 22-kは常にB/2個。
これらの並べ方は重複順列である。
$\displaystyle \frac{(A+t+B/2)!}{s!t!(A-s)!(B/2)!}$

差3の残りC-s-3t個をPattern 22-kの隙間に振り分ける。これは重複組合せ。Bが0の場合だけうまくいかないので注意する。
$\displaystyle \left( \begin{array}{c} C-s-3t+B/2-1 \\ B/2-1 \end{array} \right)$

s, tの2重ループでO(n^2)解が求まる。

sとtを分解したい。
$\begin{array}{rcl} f(x) &=& \sum_s \displaystyle \frac{1}{s!(A-s)!} x^s \\ g(x) &=& \sum_t \displaystyle \frac{(A+t+B/2)!}{t!(B/2)!} x^{3t} \\ (f*g)(x) &=& \sum_{u=s+3t} \displaystyle \frac{(A+t+B/2)!}{s!t!(A-s)!(B/2)!} x^u \end{array}$

f,gの積を高速フーリエ変換と畳み込みで求めてO(n log n)。