AGC046B

· · 题解

我们先不管去重。

设 f_{i,j} 表示当前有 i 行，j 列时的方案数。

转移时枚举上一步是放行还是放列：

f_{i,j}= f_{i-1,j}\times j + f_{i,j-1} \times i

但是发现会算重。

冷静分析一下，会算重的原因是，如果第 i 行染黑的位置在前 j-1 列，第 j 列染黑的位置在前 i-1 行，那么这个状态会被两个转移同时转移到，减去即可。

最终转移式即为：

f_{i,j}= f_{i-1,j}\times j + f_{i,j-1} \times i - f_{i-1,j-1}\times (i-1)\times (j-1)

注意一下边界。

总复杂度为 O(CD)。

代码：

f[x][y] = 1;
    re(i, n) {
        re(j, m) {
            if(i == x && j == y) continue;
            if(i == x) f[i][j] = 1ll * f[i][j-1] * i % mod;
            else if(j == y) f[i][j] = 1ll * f[i-1][j] * j % mod;
            else {
                f[i][j] = (1ll * f[i-1][j] * j % mod + 1ll * f[i][j-1] * i % mod) % mod;
                f[i][j] = (f[i][j] + mod - 1ll * f[i-1][j-1] * (i-1) % mod * (j-1) % mod) % mod;
            }
        }
    }