I am trying to solve the problem for a long time but still didn't get any idea how to solve it. It would be great if you help me to solve it. Problem Link : https://vjudge.net/contest/332542#problem/A

Since the contest is ended that's why I share the vjudge link because I think everyone has not a light oj id and this problem is from light online judge(loj). Thanks in advance :) sorry for my poor english. :)

Hint 1Firstly, note that if $$$k \gt n$$$, then by

Pigeon Hole Principle, atleast two Rooks will be attacking, thus $$$ans = 0$$$.Hint 2Break down the problem into choosing $$$k$$$ distinct rows and $$$k$$$ distinct columns. Then you have

rows — $$$r_{1}, r_{2}, ....., r_{k}$$$ and

columns — $$$c_{1}, c_{2}, ...., c_{k}$$$.

Then, you say that, first Rook is at $$$(r_{1}, c_{1})$$$, second Rook is at $$$(r_{2},c_{2})$$$, .... and so on. In general, $$$i^{th}$$$ Rook is at $$$(r_{i}, c_{i})$$$, for each $$$i \in [1,k]$$$.

Hint 3Total ways of selecting k distinct rows is $$$C(n,k)$$$. And total ways of selecting k distinct columns is $$$C(n,k)$$$. Also, finally, we have not counted permuting the selected rows and columns. So we must multiply another $$$k!$$$.

NOTE: Not $$$(k!)^2$$$ because, permuting both rows and columns means overcounting.Thanks a lot man :) Can you explain a bit about hint-3? Using an example would be better.

Let's work through an example. Consider $$$n = 10$$$, $$$k = 3$$$.

Then, first choose three rows, let's call them $$$r_1, r_2, r_3$$$. Ofcourse, we have $$$1 \le r_1, r_2, r_3 \le 10$$$.

Similiarly, choose three columns, say $$$c_1, c_2, c_3$$$. Again, $$$1 \le c_1, c_2, c_3 \le 10$$$.

So far, number of ways are — $$$C(10,3)$$$ ( for choosing $$$3$$$ rows )

AND$$$C(10,3)$$$ ( for choosing $$$3$$$ columns ). So, for now, $$$ans = C(10,3)*C(10,3)$$$.But we see that, we have $$$6$$$ configurations ( notice $$$6 = 3!$$$ ) for placing Rooks, when we have these $$$x$$$ and $$$y$$$ co-ordinates.

These configurations are:

1) $$$(r_1,c_1)$$$,$$$(r_2,c_2)$$$,$$$(r_3,c_3)$$$.

2) $$$(r_1,c_1)$$$,$$$(r_2,c_3)$$$,$$$(r_3,c_2)$$$.

3) $$$(r_1,c_2)$$$,$$$(r_2,c_1)$$$,$$$(r_3,c_3)$$$.

4) $$$(r_1,c_2)$$$,$$$(r_2,c_3)$$$,$$$(r_3,c_1)$$$.

5) $$$(r_1,c_3)$$$,$$$(r_2,c_1)$$$,$$$(r_3,c_2)$$$.

6) $$$(r_1,c_3)$$$,$$$(r_2,c_2)$$$,$$$(r_3,c_1)$$$.

So, final answer should be $$$C(10,3)*C(10,3)*3!$$$.

In, general, we have $$$C(n,k)*C(n,k)*k!$$$.

Thanks a ton man :) understood.