problem link - https://atcoder.jp/contests/agc046/tasks/agc046_b
In the recurrence relation dp[i][j] = j * dp[i-1][j] + i * dp[i][j-1] - (i-1) *(j-1) * dp[i-1][j-1], I am not able to understand the overcounting part (term which is subtracted)
'Extension' problem from atcoder
@yuvi2701,
It’s a fairly difficult problem, you can skip it as a beginner, and visit it later sometime.
Anyhow, recurrence is just inclusion-exclusion.
j*dp[i-1][j] = number of ways to color when last row added.
i*dp[i][j-1] = number of ways to color when last column added.
(i-1)*(j-1)*dp[i-1][j-1] = number of ways s.t at least one of two chosen color after adding a row and a column was in position (i,j).