Place $R$ coins in a grid so that every row and column have at least one coin I found an interesting problem in spoj:
In how many ways can $R$ coins be placed on an $N * M$ grid such that each row and each column have atleast $1$ coin ?
First idea came to my mind is, solve it for $\max(N,M)$ coins so that every row and column gets at least $1$ coin and than put rest of the coins in any cell. But this will generate many duplicate results. I wonder if this is solvable by inclusion-exclusion!
Thanks for helping.
Link to problem
 A: This is stated as a computational combinatorics problem since it's spoj, and sometimes these kinds of questions have a direct formula you can figure out and then code up, and other times you may actually have to utilize some non-trivial computation to help.  If you want to try for the more computational approach for this problem, you can do a recursion-based approach where you first place coins in the first row, and note it doesn't matter which places you put the coins; you still wind up with the same recursive smaller case that only depends on how many spaces you put coins in in the first row.  In general for a given row you're going to put coins in, you only need to keep track of how many coins you have left to place, and how many columns still have not received a coin.  So your recursion only involves two parameters (three including the row number), and you can set up the recursion using memoization or direct dynamic programming to help make sure it runs fast enough.  Also note you could get some really big answers even for rather small boards, so when you compute recursive cases and then multiply by appropriate coefficients and add to get the current answer, all computations should be done modulo the integer 1000000007 they want the final answer to be modulo by.  Since that is so close to 2^32, you'll either need native 64-bit integer arithmetic, or implement your own simple 64-bit arithmetic using 2 32-bit fields to represent a 64-bit integer field.  Also note during your recursion, if the number of coins remaining to be placed becomes greater than the total number of spaces in your rows you haven't placed coins in yet, then you can just return "0" and not recurse further because there is no solution; similarly if the number of coins remaining ever becomes smaller than the number of columns that still have not received a coin, you can similarly return "0" and not recurse.  And obviously, when you reach the final row, you have to place all the remaining coins you have left, making sure that you put a coin in every column that has not yet received a coin.
