[AtCoder] ARC 107 B – Quadruple

問題

方針

\( K \geq 0 \) として考えます。\( a + b = K + c + d \)  を満たす \( a, b, c, d \) の組み合わせを考えます。\( 2 \leq a + b \leq 2N \wedge 2 + K \leq K + c + d \leq K + 2N\) なので、

\[ 2 + K \leq a + b \leq 2N\]

の範囲で考えます。ここで、 \( a + b = n \) を満たす \( a, b \) の組み合わせの数を考えます。

\( 2 \leq n \leq N + 1 \) のとき

このとき、

\[(a, b) = (1, n – 1), (2, n – 2), \cdots , (n – 1, 1) \]

となるので、\( n – 1 \) 通りあります。

\( N + 2 \leq n \leq 2N \) のとき

このとき、

\[(a, b) = (N, n – N), (N – 1, n – N + 1), \cdots , (n – N, N) \]

となるので、\( 2N – n + 1 \) 通りあります。

\( a + b \) を固定

\( a + b = K + c + d \) において、\( a + b = n \) と固定したとき、\( c + d = n – K \) となるような \( c, d \) の組み合わせは上記同じように求められるので、\( f(n) \) を \( x + y = n \ (1 \leq x \leq N \wedge 1 \leq y \leq N)\) となるような \( x, y\) の組み合わせの個数とすると、

\[ \sum_{i = 2 + K}^{2N} f(i)f(i – K)\]

を求めれば良いです。

コード