JZOJ4779 【GDOI2017模拟9.14】鞍点（OICamp 2016 Day 5 T1） 计数问题

题目大意

现在满足要求的带权矩阵定义为至少有一个鞍点的矩阵。鞍点定义为在同一行和同一列都是严格最大的格点。
先在要求你求出大小为 N∗M 的矩阵，元素都是属于 [1,k] 的情况下，有多少符合要求的矩阵，最后答案模 l 。

N,M≤2000
k≤10
l≤109

解题思路

这种计数问题的关键就是设出不会算重算漏的状态。我们可以设状态 f(i,j) 表示当前鞍点数至少为 i ，鞍点的值最大为 j 的矩阵有多少个（转移时）。

那么我们考虑 f 的转移，我们观察下图：

绿色部分为已已经放好的部分 f(i,j) ，那么我们考虑新增 x 个权值为 j+1 的鞍点，那么很显然方案数就是 (N−ix)∗(M−ix)∗x! 再乘上除鞍点的部分，即 jx∗(N−i)+x∗(M−i)−x2−x 。
那么最后的转移方程就是：
f(i+x,j+1)=f(i+x,j+1)+f(i,j)∗(N−ix)∗(M−ix)∗x!∗jx∗(N−i)+x∗(M−i)−x2−x
最后对于每个已经更新完的 f(i,j) 在算上白色部分的情况，因为对这里没有限制所以 f(i,j)=f(i,j)∗k(N−i)∗(M−i) ，这里的定义就和之前的有点偏差，所以要容斥一下求答案。最后的答案就是 ∑min(N,M)i=0(−1)(i+1)f(i,k)

容斥原理:当 n=1 时， ∑ni=1(ni)∗(−1)(i+1)=1 ，
当 n>1 时， ∑ni=1(ni)∗(−1)(i+1)=0 （易证，用杨辉三角消一下项）

程序

//YxuanwKeith
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 2005;

int N, M, K, Mo, Min, Max, C[MAXN][MAXN], Fac[MAXN * MAXN], F[MAXN][11], Pow[11][MAXN * MAXN];

void Prepare() {
    C[0][0] = 1;
for (int i = 1; i <= Max; i ++) {
        C[i][0] = 1;
for (int j = 1; j <= Max; j ++)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % Mo;
    }
    Fac[0] = 1;
for (int i = 1; i <= N * M; i ++) Fac[i] = 1ll * Fac[i - 1] * i % Mo;
    Pow[0][0] = 1;
for (int i = 1; i <= K; i ++) {
        Pow[i][0] = 1;
for (int j = 1; j <= N * M; j ++) Pow[i][j] = 1ll * Pow[i][j - 1] * i % Mo; 
    }
}

void Solve() {
    F[0][0] = 1;
for (int i = 0; i <= Min; i ++) 
for (int j = 0; j < K; j ++) {
if (F[i][j] == 0) continue;
for (int x = 0; x <= Min - i; x ++) 
                F[i + x][j + 1] = (1ll * F[i + x][j + 1] + 1ll * F[i][j] * C[N - i][x] % Mo * C[M - i][x] % Mo * Fac[x] % Mo * Pow[j][x * (N - i) + x * (M - i) - x * x - x] % Mo) % Mo;
        }
int Ans = 0;    
for (int i = 1; i <= Min; i ++) 
        Ans = ((Ans + ((i & 1) ? 1ll : -1ll) * F[i][K] % Mo * Pow[K][(N - i) * (M - i)] % Mo) + Mo) % Mo;
printf("%d\n", Ans);
}

int main() {
scanf("%d%d%d%d", &N, &M, &K, &Mo);
    Min = min(N, M), Max = max(N, M);
    Prepare();
    Solve();
}