概要
二項係数の問題。正解者が少なく、難易度評価も高めの問題です。確かに細部まで詰め切るのは一苦労ですが、ごく自然な考察に基づいて一直線に解法を組み立てることが可能です。
二項係数について何か上手くやりたいときは、たいていの場合は、計算対象を多項式についての何かだと読み替えると、ごく自然に解に至ることができます（効用には個人差があります）。
なお、（少し問題は違いますが）易しいバージョンとして、次の記事で取り扱った問題があります。本記事では、説明が重複するところは省いていきます。
以下、負べきの項も含む多項式（$Z[T,1/T]$の元など。正確にはLaurent多項式） も単に多項式と呼んでいきます。また、計算量を表すために、座標の最大値を $N$ で表します（本問題では $N = 10^6$）。
解法
この問題は、立式までは超簡単です。
問題：$\sum_{x_1,x_2,x_3,y_1,y_2,y_3}\binom{x_2-x_1+y_2-y_1}{x_2-x_1}\cdot \binom{x_3-x_2+y_3-y_2}{x_3-x_2}$ を求めよ．ただし、$x_i,y_j$は適当な区間を独立に動く（$X_1\leq x_1\leq X_2$など）．
前回記事に登場したように、二項係数を次のように解釈します。
\[\binom{n}{r} = T^{-r}(1+T)^nの定数項\]
この問題では、二項係数2つの積を扱わなければいけません。次のようにやると失敗です。
\[失敗例：\binom{n_1}{r_1} \binom{n_2}{r_2} = T^{-r_1}(1+T)^{n_1}\cdot T^{-r_2}(1+T)^{n_2} の定数項\]
これは失敗です。負べきの項も含む多項式（Lanrent多項式）を扱っているため、定数項をとる操作と積が交換できません。しかしこの解決は簡単で、2 変数多項式を用意して次のようにすればよいです。
\[\binom{n_1}{r_1} \binom{n_2}{r_2} = S^{-r_1}(1+S)^{n_1}\cdot T^{-r_2}(1+T)^{n_2} の定数項\]
この読み替えをもとに、問題を書き直していきましょう。興味のある二項係数の積を定数項に持つ多項式を作ります。
問題： $\sum_{x_1,x_2,x_3,y_1,y_2,y_3}S^{x_1-x_2}(1+S)^{x_2-x_1+y_2-y_1}T^{x_2-x_3}(1+T)^{x_3-x_2+y_3-y_2}$ の定数項を求めよ．
すると、自然と良い構造が見えてきます。記述を統一的にするために，文字の置き方も調整していきます。
$r_1 = S(1+S)^{-1}$, $r_2 = S^{-1}(1+S)T(1+T)^{-1}$, $r_3 = T^{-1}(1+T)$, $r_4 = (1+S)^{-1}$, $r_5 = (1+S)(1+T)^{-1}$, $r_6 = (1+T)$.
$x_4 = y_1$, $x_5 = y_2$, $x_6 = y_3$.
また、$L_i, R_i$も適切に設定して、$x_i$の範囲が$L_i\leq x_i < R_i$ となるようにしておきます。このような文字を使うと、問題は次の形になりました。
問題：$\sum_{x_1,x_2,x_3,x_4,x_5,x_6}r_1^{x_1}r_2^{x_2}r_3^{x_3}r_4^{x_4}r_5^{x_5}r_6^{x_6}$ の定数項を求めよ．$x_i$ は 独立に区間 $L_i\leq x_i < R_i$ を動く．
これは流石に…！
問題：$\prod_{i=1}^6\biggl(\sum_{L_i\leq x_i < R_i}r_i^{x_i}\biggr)$ の定数項を求めよ．
ほぼ機械的に式をいじった程度ですが、この問題の最も難しいところは既に超えられた気がしてきませんか？ とはいえ、まだまだ残作業も多いので、しっかり詰めていきます。等比数列の和は、$\sum_{L\leq x < R}r^x = \frac{r^{R} – r^L}{r-1}$ と計算されます。
問題：$\prod_{i=1}^6\frac{r_i^{R_i} – r_i^{L_i}}{r_i-1}$ の定数項を求めよ．
$r_i – 1$の積は文字式の計算をします。$\prod_i (r_i-1) = \frac{-(S-T)^2}{(1+S)^2(1+T)^2}$が分かります。また、$\prod_i(r_i^{R_i} – r_i^{L_i})$は展開してしまいましょう。結局、次のような問題を解けばよいと分かります：
問題：$\frac{(1+S)^2(1+T)^2}{(S-T)^2}\sum \pm r_1^{a_1}r_2^{a_2}r_3^{a_3}r_4^{a_4}r_5^{a_5}r_6^{a_6}$ の定数項を求めよ．和は64通りを適切に動く（$a_i$ に $L_i$ または $R_i$ を割り当てて、割り当て方に応じて符号 $\pm$ を決める）．
見た目上シグマ記号を使いましたが、このシグマ記号は定数個の和で、これまでよりも本質的に簡単です。さらに、$\prod r_i^{a_i}$ を適当に計算すると、次のような問題を解くことになります。
問題： $\frac{1}{(S-T)^2}\sum_{a,b,c,d}\pm S^{-a}T^{-b}(1+S)^c(1+T)^d$ の定数項を計算せよ．ただし、符号 $\pm$ および $a,b,c,d$ は適切に計算された $64$ 通りの組み合わせを動く．
$(S-T)^2$ で割るところだけが頭を悩ませますが、次の手順に沿えばOKです。
[1] $\sum_{a,b,c,d}\pm S^{-a}T^{-b}(1+S)^c(1+T)^d$ のうち、$2$次の項を全て計算する。$2$ 次の項をすべて集めて $F(S,T)$ とする。
[2] $F(S,T)/(S-T)^2$ の定数項を計算する。まず、[1] について考えましょう。$(1+S)^c(1+T)^d = \sum_{i,j}\binom{c}{i}\binom{d}{j}S^iT^j$ です。$2$ 次の項に興味を持つ場合、各 $i$ に対して興味のある $j$ は一意に定まります。よって (1) は各 $a,b,c,d$ ごとに、 $O(N)$ で行えます。
[2] について考えます。$2$ 変数多項式といえど、次数がそろってしまっているので、本質的には 1 変数多項式の問題で、 $T=1$ を代入した次の問題 [3] と等価です。 [3] $S$ の 1変数 (Laurent) 多項式 $F(S)$ が与えられる。$F(S) / (1-S)^2$ の定数項を求めよ。これにはいくつかの方法があります。
・$2$ 次多項式 $(1-S)^2$ による除算を標準的な高校数学の要領で計算する。
・形式的べき級数 $\frac{1}{1-S} = \sum_{n\geq 0} S^n$ を2回かける。係数の累積和を2回とればよい。
・形式的べき級数 $\frac{1}{(1-S)^2} = \sum_{n\geq 0} (n+1)S^n$ をかける。$F(S) = \sum_{n}a_nS^n$ としたとき、$\sum_{n\geq0} (n+1)a_{-n}$ が求めるもの。
コメント
手計算・実装ともに少し面倒な思いをするところはあれど、基本的に一直線に考察が進んで解けているように思いますが、いかがでしょうか。
計算量は、$O(N)$ で、ただし、定数倍に $64$ 倍などが乗っているのでやや重めです（TLE 制約は緩いので余裕はあります）。さらなる高速化のヒントとしては、$S^{-a}T^{-b}(1+S)^c(1+T)^d$ の計算パートで、
・実は $c, d$ として出てくる値は限定的。メモ化して同じ $c$ に対する計算を 2 回やらないようにする（MLE 回避がだるい）。
・$x_1,x_2,x_3,y_2$ を固定して $y_1,y_3$ を動かすと、$a,b$ が共通で、$c,d$ が2種ずつ出てくる。$\bigl((1+S)^{c_1} – (1+S)^{c_2}\bigr) \bigl((1+T)^{d_1} – (1+S)^{d_2}\bigr)$ の要領でまとめて計算できる。
などがあるようです。あまり掘り下げていませんが、64通りに展開してしまうのが少し損をしていて、一部分はまとめて扱うべきだったかもしれません。