ก่อนอื่น สังเกตว่าจำนวน inversion ในลำดับขึ้นอยู่กับการเรียงสับเปลี่ยนของความสัมพันธ์ของตัวเลขในลำดับเท่านั้น ลำดับไม่จำเป็นต้องมีตัวเลขเรียงจาก $1$ ไป $n$ เสมอไป ยกตัวอย่าง กรณีลำดับ $[1,2,3]$ สามารถเรียงได้ $6$ แบบได้แก่ $[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]$ ได้จำนวน inversion เป็น $0, 1, 1, 2, 2, 3$ ตามลำดับ ส่วนลำดับ $[3, 6, 9]$ ก็สามารถเรียงได้จำนวน inversion เป็น $0, 1, 1, 2, 2, 3$ ตามลำดับเช่นกัน

ดังนั้น หากกำหนดค่า $n$ (จำนวนสมาชิก) และ $k$ (จำนวน inversion) ที่ต้องการมาให้ เราสามารถสร้างลำดับ (permutation ของ $[1,2,3,\dots,n]$) ได้ด้วยการตัดสินใจว่าสมาชิกตัวแรกควรเป็นเลขอะไร ส่วนสมาชิก $n-1$ ตัวที่เหลือ พิจารณาว่าเป็นการสร้างลำดับ $1$ ถึง $n-1$ ใหม่ได้ถึงแม้ว่าตัวเลขที่ใช้จริง ๆ แล้วจะเป็นเลขอื่น

สังเกตว่าหากเลือกเอาเลข $v$ ขึ้นมาไว้ที่ตำแหน่งแรก เลขนี้จะเกิด inversion ทั้งหมด $v-1$ ครั้งกับเลข $n-1$ ตัวที่เหลือที่จะนำมาใส่ด้านหลัง (ไม่สนใจว่าจะใส่เรียงลำดับยังไง)

การนับจำนวนวิธีสร้างลำดับในข้อนี้จึงสามารถใช้ dynamic programming คำนวณได้

นิยามให้ $dp_{i,j}$ หมายถึงจำนวนวิธีการสร้างลำดับขนาด $i$ สมาชิก ให้ได้จำนวน inversion เท่ากับ $j$ จะมี base case ได้แก่

• $dp_{0,0} = 1$
• $dp_{0,j} = 0$ สำหรับ $j \neq 0$
• $dp_{i,j} = 0$ สำหรับ $i > 0$, $j < 0$

สำหรับ $i > 0$, $j \geq 0$ จะเขียน recurrence formula ได้ว่า

$dp_{i,j} = \sum\limits_{v=1}^{i} dp_{i-1,j-(v-1)}$

(ตัดสินใจว่าจะให้สมาชิกแรกเป็นเลขอะไรตั้งแต่ $v=1,2,3,\dots,i$ เมื่อตัดสินใจแล้ว จะเกิด inversion ขึ้น $v-1$ ดังนั้นจึงพิจารณาสร้างลำดับ $i-1$ ตัวที่เหลือให้มี inversion รวมเป็น $j-(v-1)$)

คำตอบสุดท้ายของโจทย์ข้อนี้คือ $dp_{n,k}$

เนื่องจาก $n$ และ $k$ มีค่ามากถึง $10\,000$ วิธีเดิมที่ใช้ Time Complexity $O(n^2k)$ และ Space Complexity $O(nk)$ จึงไม่เหมาะสม

เราสามารถลดเวลาการคำนวณเหลือ $O(nk)$ ได้โดยนิยาม prefix sum $qs_{i,j} = dp_{i,0}+dp_{i,1}+dp_{i,2}+\dots+dp_{i,j}$ ขึ้นมา ทำให้พจน์ $\sum\limits_{v=1}^{i} dp_{i-1,j-(v-1)}$ สามารถคำนวณได้อย่างรวดเร็วจาก $qs_{i-1,j}-qs_{i-1,j-i}$ (ถ้า $j-i < 0$ พจน์ $qs_{i-1,j-i}$ มีค่าเท่ากับ $0$)

สังเกตว่าระหว่างการคำนวณใด ๆ เราสนใจเพียงแค่ 2 แถวสุดท้ายของตาราง $dp$ และ $qs$ ดังนั้น เราสามารถลดหน่วยความจำที่ต้องใช้ให้เหลือ $O(k)$ โดยเก็บแค่ 2 แถวสุดท้ายไว้เท่านั้น

ทั้งนี้ อย่าลืมคำนวณใน modulo $2012$ และระมัดระวังไม่ให้เกิดจำนวนติดลบขึ้น