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. :)
Firstly, note that if $$$k \gt n$$$, then by Pigeon Hole Principle, atleast two Rooks will be attacking, thus $$$ans = 0$$$.
Break 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]$$$.
Total 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!$$$.